{"problem":{"name":"Colorful Lines","description":{"content":"We have an $H\\times W$ grid. Initially, the squares are unpainted. You will paint these squares. There are $C$ colors available, numbered $1, 2, \\ldots, C$. The painting process will be given as $Q$ q","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc130_b"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc130_b","tags":[],"sample_group":[["4 5 6 5\n1 1 6\n1 3 3\n2 2 4\n2 4 2\n1 1 2","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."],["1000000000 1000000000 3 5\n1 1 2\n1 2 2\n1 3 2\n1 4 2\n1 5 2","0 5000000000 0"]],"created_at":"2026-03-03 11:01:13"}}