Problem: You are given a matrix n × m, initially filled with zeroes. We define a_{i, j} as the element in the i-th row and the j-th column of the matrix.

Two cells of the matrix are connected if they share a side, and the elements in these cells are equal. Two cells of the matrix belong to the same connected component if there exists a sequence s_1, s_2, ..., s_k such that s_1 is the first cell, s_k is the second cell, and for every i ∈ [1, k - 1], s_i and s_{i + 1} are connected.

You are given q queries of the form x_i y_i c_i (i ∈ [1, q]). For every such query, you have to do the following:

  1. replace the element a_{x, y} with c; 
  2. count the number of connected components in the matrix. 



There is one additional constraint: for every i ∈ [1, q - 1], c_i ≤ c_{i + 1}.

Input

The first line contains three integers n, m and q (1 ≤ n, m ≤ 300, 1 ≤ q ≤ 2 ⋅ 10^6) — the number of rows, the number of columns and the number of queries, respectively.

Then q lines follow, each representing a query. The i-th line contains three integers x_i, y_i and c_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ m, 1 ≤ c_i ≤ max(1000, ⌈ (2 ⋅ 10^6)/(nm) ⌉)). For every i ∈ [1, q - 1], c_i ≤ c_{i + 1}.

Output

Print q integers, the i-th of them should be equal to the number of components in the matrix after the first i queries are performed.

Example

Input


3 2 10
2 1 1
1 2 1
2 2 1
1 1 2
3 1 2
1 2 2
2 2 2
2 1 2
3 2 4
2 1 5


Output


2
4
3
3
4
4
4
2
2
4

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class NumberOfComponents {
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out, false);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int q = scanner.nextInt();
        int[][] ops = new int[4][q];
        int[][] revops = new int[q][4];
        for(int i = 0; i < q; i++) {
            ops[0][i] = scanner.nextInt()-1;
            ops[1][i] = scanner.nextInt()-1;
            ops[2][i] = scanner.nextInt();
            ops[3][i] = i;
        }
        int ub  = Math.max(1005,( 2 * 1_000_000 + n * m - 1)/(n*m) + 5);
        int[] ans = new int[q];
        ArrayList<int[]>[] prep = new ArrayList[ub];
        int[][] grid = new int[n][m];
        int[] dr = {1, 0, -1, 0};
        int[] dc = {0, 1, 0, -1};
        DSU dsu = new DSU(n * m);
        int prevCol = ops[2][0];
        int startCol = 0;
//        out.println("BEFORE FORWARDS: " + Arrays.toString(ans));
        int revv = 0;
        for(int i = 0; i <q; i++) {
            int x = ops[0][i];
            int y = ops[1][i];
            int c = ops[2][i];
            int prev = grid[x][y];
            if (prev == c) continue;
            //reset dsu on color change
            if (prevCol != c) {
//                out.println("Changing colors from " + prevCol + " to " + c);
//                out.println("BEFORE FORWARDS: " + Arrays.toString(ans));
                prevCol = c;
                while(startCol < i) {
                    dsu.reset(ops[0][startCol] * m + ops[1][startCol]);
                    startCol++;
                }
            }
            grid[x][y] = c;
            revops[i][0] = x;
            revops[i][1] = y;
            revops[i][2] = prev;
            revops[i][3] = i;
            revv++;
            int p = 1;
            //go forwards
            for(int j = 0; j < dr.length; j++) {
                int nr = x + dr[j];
                int nc = y + dc[j];
                if (nr < 0 || nc < 0 || nr >= n || nc >= m|| grid[nr][nc]!=grid[x][y]) { continue; }
                if(dsu.union(x * m + y, nr * m + nc)) {
                    p--;
                }
            }
            ans[ops[3][i]]+=p;
        }
        while(startCol < q) {
            dsu.reset(ops[0][startCol] * m + ops[1][startCol]);
            startCol++;
        }
        //this shouldn't be too bad
        for(int i = 0; i < ub; i++) { prep[i] = new ArrayList<>(); }
        for(int i= 0; i < n; i++) for(int j = 0; j < m; j++) {
            prep[grid[i][j]].add(new int[] {i,j});
        }
        Arrays.sort(revops, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[2] == o2[2]) {
                    return o2[3] - o1[3];
                }
                return o2[2] - o1[2];
            }
        });
        startCol = 0;
        prevCol = revops[0][2];
        for(int[] gg: grid) Arrays.fill(gg, -1);
        for(int[] op: prep[prevCol]) {
            int xx = op[0];
            int yy = op[1];
            grid[xx][yy] = prevCol;
            for (int j = 0; j < dr.length; j++) {
                int nr = xx + dr[j];
                int nc = yy + dc[j];
                if (nr < 0 || nc < 0 || nr >= n || nc >= m || grid[nr][nc]!=grid[xx][yy]) {
                    continue;
                }
                dsu.union(xx * m + yy, nr * m + nc);
            }
        }
//        out.println("BEFORE BACKWARDS: "  + prevCol + " "  + Arrays.toString(ans));
        for(int i = 0; i < revv; i++) {
            //now do backwards
            int x = revops[i][0];
            int y = revops[i][1];
            int c = revops[i][2];
            if (c != prevCol) {
//                out.println("Changing colors from " + prevCol + " to " + c);
//                out.println("BEFORE BACKWARDS: " + c + " " + Arrays.toString(ans));
                while(startCol < i) {
                    dsu.reset(revops[startCol][0]*m + revops[startCol][1]);
                    startCol++;
                }
                for(int[] op: prep[prevCol]) {
                    dsu.reset(op[0] * m + op[1]);
                }
                prevCol = c;
                for(int[] op: prep[c]) {
                    int xx = op[0];
                    int yy = op[1];
                    grid[xx][yy] = c;
                    for (int j = 0; j < dr.length; j++) {
                        int nr = xx + dr[j];
                        int nc = yy + dc[j];
                        if (nr < 0 || nc < 0 || nr >= n || nc >= m || grid[nr][nc]!=grid[xx][yy]) {
                            continue;
                        }
                        dsu.union(xx * m + yy, nr * m + nc);
                    }
                }
            }
            grid[x][y] =c;
            int p = 1;
            for (int j = 0; j < dr.length; j++) {
                int nr = x + dr[j];
                int nc = y + dc[j];
                if (nr < 0 || nc < 0 || nr >= n || nc >= m || grid[nr][nc]!=grid[x][y]) {
                    continue;
                }
                if (dsu.union(x * m + y, nr * m + nc)) {
                    p--;
                }
            }
            ans[revops[i][3]] -= p;
        }
        ans[0]++;
//        out.println(Arrays.toString(ans));
        for(int i = 0; i <q ; i++) {
            if (i > 0) ans[i] += ans[i-1];
            out.println(ans[i]);
        }
        out.flush();
    }
    static class DSU {
        int[] rank, parent;
        public DSU(int ss) {
            rank = new int[ss];
            parent = new int[ss];
            for(int i = 0; i < ss; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }
        int find(int a) {
            int p = a;
            while(parent[a]!=a) a = parent[a];
            while(parent[p]!=a) {
                int t = parent[p];
                parent[p] = a;
                p = t;
            }
            return a;
        }
        void reset(int a) {
            parent[a] = a;
            rank[a] = 1;
        }
        boolean union(int a, int b) {
            int pa = find(a);
            int pb = find(b);
            if (pa == pb) return false;
            if (rank[pa] <= rank[pb]) {
                rank[pb] += rank[pa];
                parent[pa] = pb;
            }else {
                rank[pa] += rank[pb];
                parent[pb] = pa;
            }
            return true;
        }
    }
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}