Problem: Inna loves sweets very much. That's why she decided to play a game called "Sweet Matrix".

Inna sees an n × m matrix and k candies. We'll index the matrix rows from 1 to n and the matrix columns from 1 to m. We'll represent the cell in the i-th row and j-th column as (i, j). Two cells (i, j) and (p, q) of the matrix are adjacent if |i - p| + |j - q| = 1. A path is a sequence of the matrix cells where each pair of neighbouring cells in the sequence is adjacent. We'll call the number of cells in the sequence the path's length.

Each cell of the matrix can have at most one candy. Initiallly, all the cells are empty. Inna is trying to place each of the k candies in the matrix one by one. For each candy Inna chooses cell (i, j) that will contains the candy, and also chooses the path that starts in cell (1, 1) and ends in cell (i, j) and doesn't contain any candies. After that Inna moves the candy along the path from cell (1, 1) to cell (i, j), where the candy stays forever. If at some moment Inna can't choose a path for the candy, she loses. If Inna can place all the candies in the matrix in the described manner, then her penalty equals the sum of lengths of all the paths she has used.

Help Inna to minimize the penalty in the game.

Input

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 50, 1 ≤ k ≤ n·m).

Output

In the first line print an integer — Inna's minimum penalty in the game.

In the next k lines print the description of the path for each candy. The description of the path of the candy that is placed i-th should follow on the i-th line. The description of a path is a sequence of cells. Each cell must be written in the format (i, j), where i is the number of the row and j is the number of the column. You are allowed to print extra whitespaces in the line. If there are multiple optimal solutions, print any of them.

Please follow the output format strictly! If your program passes the first pretest, then the output format is correct.

Examples

Input

4 4 4


Output

8
(1,1) (2,1) (2,2)
(1,1) (1,2)
(1,1) (2,1)
(1,1)

Note

Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8.

Note that Inna couldn't use cell (1, 1) to place, for instance, the third candy as in this case she couldn't have made the path for the fourth candy.

Solution (in JAVA):

Solution:
/**
 * Created with IntelliJ IDEA.
 * User: den
 * Date: 2/11/14
 * Time: 6:28 PM
 * To change this template use File | Settings | File Templates.
 */


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

public class TaskD extends Thread {
    class Pair {
        int id;
        int x;
        int y;

        public String toString() {
            return "(" + x + "," + y + ")";
        }

        public Pair(int _id, int _x, int _y) {
            id = _id;
            x = _x;
            y = _y;
        }

        public Pair(int _id) {
            id = _id;
        }
    }

    private void solve() throws IOException {
        int n = _int();
        int m = _int();
        int k = _int();

        int[][] a = new int[n + 1][m + 1];
        ArrayList<Pair> ans = new ArrayList<Pair>();
        Queue<Pair> q = new LinkedList<Pair>();
        int fine = 0;
        Pair[] all = new Pair[2501];
        int[] prev = new int[2501];
        for (int i = 0; i < 2501; i++)
            all[i] = new Pair(i);

        all[0].x = 1;
        all[0].y = 1;
        prev[0] = -1;
        q.add(all[0]);
        a[1][1] = 1;
        int next = 1;

        while (k > 0) {
            Pair current = q.remove();
            fine += current.x + current.y - 1;

            if (current.x < n && a[current.x + 1][current.y] == 0) {
                all[next].x = current.x + 1;
                all[next].y = current.y;
                prev[next] = current.id;
                a[all[next].x][all[next].y] = 1;
                q.add(all[next++]);
            }

            if (current.y < m && a[current.x][current.y + 1] == 0) {
                all[next].x = current.x;
                all[next].y = current.y + 1;
                prev[next] = current.id;
                a[all[next].x][all[next].y] = 1;
                q.add(all[next++]);
            }

            ans.add(current);
            k--;
        }


        out.println(fine);
        while (ans.size() > 0) {
            Pair c = ans.remove(ans.size() - 1);
            StringBuilder st = new StringBuilder(c.toString());
            int parent = prev[c.id];
            while (parent > -1) {
                st.insert(0, all[parent].toString() + " ");
                parent = prev[parent];
            }
            out.println(st.toString());
        }

    }

    public int[] move(int n, int m, int x, int y) {
        int[] next = new int[2];
        if (x + 1 < n) {
            // go down
            next[0] = x + 1;
            next[1] = y;
            return next;
        } else {
            // go right
            next[0] = x;
            next[1] = y + 1;
            return next;
        }
    }

    public void run() {
        try {
            solve();
        } catch (Exception e) {
            System.out.println("System exiting....");
            e.printStackTrace();
            System.exit(888);
        } finally {
            out.flush();
            out.close();
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        new TaskD().run();
    }

    public TaskD() throws FileNotFoundException {
        //in = new BufferedReader(new FileReader("A-large.in"));
        //out = new PrintWriter(new File("A-large.out"));
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        setPriority(Thread.MAX_PRIORITY);
    }

    private BufferedReader in;
    private PrintWriter out;
    private StringTokenizer st;

    private int _int() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private double _double() throws IOException {
        return Double.parseDouble(nextToken());
    }

    private long _long() throws IOException {
        return Long.parseLong(nextToken());
    }

    private char[] _chars() throws IOException {
        return nextToken().toCharArray();
    }

    private String nextToken() throws IOException {
        if (st == null || !st.hasMoreElements())
            st = new StringTokenizer(in.readLine(), " \t\r\n");
        return st.nextToken();
    }
}