{"problem":{"name":"Akari","description":{"content":"We have a grid with $H$ rows and $W$ columns. Let square $(i, j)$ be the square at the $i$\\-th row and $j$\\-th column in this grid.   There are $N$ bulbs and $M$ blocks on this grid. The $i$\\-th bulb ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc182_e"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $H$ rows and $W$ columns. Let square $(i, j)$ be the square at the $i$\\-th row and $j$\\-th column in this grid.  \nThere are $N$ bulbs and $M$ blocks on this grid. The $i$\\-th bulb is at square $(A_i, B_i)$, and the $i$\\-th block is at square $(C_i, D_i)$. There is at most one object - a bulb or a block - at each square.  \nEvery bulb emits beams of light in four directions - up, down, left, and right - that extend until reaching a square with a block, illuminating the squares on the way. A square with a bulb is also considered to be illuminated. Among the squares without a block, find the number of squares illuminated by the bulbs.\n\n## Constraints\n\n*   $1 \\le H, W \\le 1500$\n*   $1 \\le N \\le 5 \\times 10^5$\n*   $1 \\le M \\le 10^5$\n*   $1 \\le A_i \\le H$\n*   $1 \\le B_i \\le W$\n*   $1 \\le C_i \\le H$\n*   $1 \\le D_i \\le W$\n*   $(A_i, B_i) \\neq (A_j, B_j)\\ \\ (i \\neq j)$\n*   $(C_i, D_i) \\neq (C_j, D_j)\\ \\ (i \\neq j)$\n*   $(A_i, B_i) \\neq (C_j, D_j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$A_3$ $B_3$\n$\\hspace{15pt} \\vdots$\n$A_N$ $B_N$\n$C_1$ $D_1$\n$C_2$ $D_2$\n$C_3$ $D_3$\n$\\hspace{15pt} \\vdots$\n$C_M$ $D_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc182_e","tags":[],"sample_group":[["3 3 2 1\n1 1\n2 3\n2 2","7\n\nAmong the squares without a block, all but square $(3, 2)$ are illuminated."],["4 4 3 3\n1 2\n1 3\n3 4\n2 3\n2 4\n3 2","8\n\nAmong the squares without a block, the following eight are illuminated:\n\n*   Square $(1, 1)$\n*   Square $(1, 2)$\n*   Square $(1, 3)$\n*   Square $(1, 4)$\n*   Square $(2, 2)$\n*   Square $(3, 3)$\n*   Square $(3, 4)$\n*   Square $(4, 4)$"],["5 5 5 1\n1 1\n2 2\n3 3\n4 4\n5 5\n4 2","24\n\nIn this case, all the squares without a block are illuminated."]],"created_at":"2026-03-03 11:01:14"}}