Problem: Iahub wants to enhance his multitasking abilities. In order to do this, he wants to sort n arrays simultaneously, each array consisting of m integers.

Iahub can choose a pair of distinct indices i and j (1 ≤ i, j ≤ m, i ≠ j). Then in each array the values at positions i and j are swapped only if the value at position i is strictly greater than the value at position j.

Iahub wants to find an array of pairs of distinct indices that, chosen in order, sort all of the n arrays in ascending or descending order (the particular order is given in input). The size of the array can be at most <image> (at most <image> pairs). Help Iahub, find any suitable array.

Input

The first line contains three integers n (1 ≤ n ≤ 1000), m (1 ≤ m ≤ 100) and k. Integer k is 0 if the arrays must be sorted in ascending order, and 1 if the arrays must be sorted in descending order. Each line i of the next n lines contains m integers separated by a space, representing the i-th array. For each element x of the array i, 1 ≤ x ≤ 106 holds.

Output

On the first line of the output print an integer p, the size of the array (p can be at most <image>). Each of the next p lines must contain two distinct integers i and j (1 ≤ i, j ≤ m, i ≠ j), representing the chosen indices.

If there are multiple correct answers, you can print any.

Examples

Input

2 5 0
1 3 2 5 4
1 4 3 2 5


Output

3
2 4
2 3
4 5


Input

3 2 1
1 2
2 3
3 4


Output

1
2 1

Note

Consider the first sample. After the first operation, the arrays become [1, 3, 2, 5, 4] and [1, 2, 3, 4, 5]. After the second operation, the arrays become [1, 2, 3, 5, 4] and [1, 2, 3, 4, 5]. After the third operation they become [1, 2, 3, 4, 5] and [1, 2, 3, 4, 5].

Solution (in JAVA):

Solution:

import java.util.*;
import java.io.*;

public class Main implements Runnable {

    /// Find the end for all and check whether any two max have diff end.
    /// Yes 2*max
    /// No = 2*max-1;
    ///382D-problem - Ksenia and Pawns
    class Pair {

        int x, y;
    }

    public void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        int[][] arrays = new int[n][m + 1];
        boolean sl = nextInt() == 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                arrays[i][j] = nextInt();
            }
        }
        int cnt = 0;
        StringBuffer sb = new StringBuffer("");
        if (sl) {
            for (int i = 1; i <= m; i++) {
                for (int j = i + 1; j <= m; j++) {
                    boolean had = false;
                    for (int k = 0; k < n; k++) {
                        if (arrays[k][i] > arrays[k][j]) {
                            had = true;
                            int t = arrays[k][i];
                            arrays[k][i] = arrays[k][j];
                            arrays[k][j] = t;
                        }
                    }
                    if (had) {
                        sb.append(i + " " + j + "\n");
                        cnt++;
                    }
                }
            }
        } else {
            for (int i = 1; i <= m; i++) {
                for (int j = i + 1; j <= m; j++) {
                    boolean had = false;
                    for (int k = 0; k < n; k++) {
                        if (arrays[k][i] < arrays[k][j]) {
                            had = true;
                            int t = arrays[k][i];
                            arrays[k][i] = arrays[k][j];
                            arrays[k][j] = t;
                        }
                    }
                    if (had) {
                        sb.append(j + " " + i + "\n");
                        cnt++;
                    }
                }
            }
        }
        System.out.println(cnt + "\n" + sb);
    }

    String[] check(String in) {
        String[] ret = new String[2];
        Arrays.fill(ret, "");
        int i = 0;
        for (i = 0; i < in.length(); i++) {
            if (in.charAt(i) == '|') {
                break;
            }
            ret[0] += in.charAt(i);
        }
        i++;
        for (; i < in.length(); i++) {
            //if(in.charAt(i)=='|')break;
            ret[1] += in.charAt(i);
        }
        return ret;
    }

    int answer(int[] a, int[] b) {
        int n = a.length;
        b = b.clone();
        a = a.clone();
        for (int i = 0; i < n; i++) {
            if (b[i] >= 0) {
                merge(a, i, b[i]);
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] < 0) {
                cnt++;
            }
        }
        return cnt;
    }

    void merge(int[] arr, int a, int b) {
        a = get(arr, a);
        b = get(arr, b);
        if (a != b) {
            if (arr[a] > arr[b]) {
                int t = a;
                a = b;
                b = t;
            }
            arr[a] += arr[b];
            arr[b] = a;
        }
    }

    int get(int[] arr, int a) {
        if (arr[a] < 0) {
            return a;
        }
        return arr[a] = get(arr, arr[a]);
    }

    void shuffle(int[] a) {
        int N = a.length;
        for (int i = 0; i < N / 2; i++) {
            int j = (int) (Math.random() * N);
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    void print(Object... obj) {
        for (Object o : obj) {
            System.out.println(o);
        }
    }

    void print(int[] a) {
        System.out.println();
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    void print(int[][] arr) {
        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    void print(boolean[][] arr) {
        System.out.println();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    boolean nextPermutation(int[] arr) {
        int f = -1;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i + 1] > arr[i]) {
                f = i;
                break;
            }
        }
        if (f == -1) {
            return false;
        }
        int s = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] > arr[f]) {
                s = i;
                break;
            }
        }
        int d = arr[f];
        arr[f] = arr[s];
        arr[s] = d;

        f++;
        int l = arr.length - 1;
        while (f < l) {
            d = arr[f];
            arr[f] = arr[l];
            arr[l] = d;
            f++;
            l--;
        }
        return true;
    }

    //-----------------------------------------------------------
    public static void main(String[] args) {
        new Main().run();
    }

    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            tok = null;
            solve();
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    public String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    BufferedReader in;
    StringTokenizer tok;
}

class Student {

    int idx;
    int level;
    int cost;

    public Student(int i, int l) {
        idx = i;
        level = l;
    }

    public String toString() {
        return idx + " " + level + " " + cost;
    }
    public static final Comparator<Student> byLevel = new Comparator<Student>() {
        public int compare(Student a, Student b) {
            if (a.level != b.level) {
                return b.level - a.level;
            }
            if (a.cost != b.cost) {
                return a.cost - b.cost;
            }
            return a.idx - b.idx;
        }
    };
    public static final Comparator<Student> byCost = new Comparator<Student>() {
        public int compare(Student a, Student b) {
            if (a.cost != b.cost) {
                return a.cost - b.cost;
            }
            if (a.level != b.level) {
                return b.level - a.level;
            }
            return a.idx - b.idx;
        }
    };
}

class Bug implements Comparable<Bug> {

    int idx;
    int level;

    public Bug(int idx, int level) {
        this.idx = idx;
        this.level = level;
    }

    public int compareTo(Bug other) {
        if (level != other.level) {
            return other.level - level;
        }
        return idx - other.idx;
    }

    public String toString() {
        return idx + " " + level;
    }
}