{"raw_statement":[{"iden":"problem statement","content":"We have an $H\\times W$ grid. Initially, the squares are unpainted.\nYou will paint these squares. There are $C$ colors available, numbered $1, 2, \\ldots, C$.\nThe painting process will be given as $Q$ queries. The $i$\\-th query contains integers $t_i, n_i, c_i$, which represents the following action.\n\n*   If $t_i = 1$: paint all squares in the $n_i$\\-th **row** with Color $c_i$.\n*   If $t_i = 2$: paint all squares in the $n_i$\\-th **column** with Color $c_i$.\n\nPainting a square with Color $c$ makes the color of that square Color $c$, regardless of its previous state.\nFind the number of squares painted in each of Color $1, 2, \\ldots, C$ after the whole process."},{"iden":"constraints","content":"*   $2\\leq H\\leq 10^9$\n*   $2\\leq W\\leq 10^9$\n*   $1\\leq C\\leq 3\\times 10^5$\n*   $1\\leq Q\\leq 3\\times 10^5$\n*   $t_i\\in {1,2}$\n*   $1\\leq n_i\\leq H$ if $t_i = 1$\n*   $1\\leq n_i\\leq W$ if $t_i = 2$\n*   $1\\leq c_i\\leq C$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$ $C$ $Q$\n$t_1$ $n_1$ $c_1$\n$\\vdots$\n$t_Q$ $n_Q$ $c_Q$"},{"iden":"sample input 1","content":"4 5 6 5\n1 1 6\n1 3 3\n2 2 4\n2 4 2\n1 1 2"},{"iden":"sample output 1","content":"0 8 3 3 0 0\n\nThe process changes the colors of the squares as follows. Here, `.` denotes an unpainted square.\n\n.....   66666   66666   64666   64626   22222\n.....   .....   .....   .4...   .4.2.   .4.2.\n.....   .....   33333   34333   34323   34323\n.....   .....   .....   .4...   .4.2.   .4.2."},{"iden":"sample input 2","content":"1000000000 1000000000 3 5\n1 1 2\n1 2 2\n1 3 2\n1 4 2\n1 5 2"},{"iden":"sample output 2","content":"0 5000000000 0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}