{"problem":{"name":"AtCoder Express 2","description":{"content":"In Takahashi Kingdom, there is a east-west railroad and $N$ cities along it, numbered $1$, $2$, $3$, ..., $N$ from west to east. A company called _AtCoder Express_ possesses $M$ trains, and the train ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc106_d"},"statements":[{"statement_type":"Markdown","content":"In Takahashi Kingdom, there is a east-west railroad and $N$ cities along it, numbered $1$, $2$, $3$, ..., $N$ from west to east. A company called _AtCoder Express_ possesses $M$ trains, and the train $i$ runs from City $L_i$ to City $R_i$ (it is possible that $L_i = R_i$). Takahashi the king is interested in the following $Q$ matters:\n\n*   The number of the trains that runs **strictly within** the section from City $p_i$ to City $q_i$, that is, the number of trains $j$ such that $p_i \\leq L_j$ and $R_j \\leq q_i$.\n\nAlthough he is genius, this is too much data to process by himself. Find the answer for each of these $Q$ queries to help him.\n\n## Constraints\n\n*   $N$ is an integer between $1$ and $500$ (inclusive).\n*   $M$ is an integer between $1$ and $200 \\ 000$ (inclusive).\n*   $Q$ is an integer between $1$ and $100 \\ 000$ (inclusive).\n*   $1 \\leq L_i \\leq R_i \\leq N$ $(1 \\leq i \\leq M)$\n*   $1 \\leq p_i \\leq q_i \\leq N$ $(1 \\leq i \\leq Q)$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$:$\n$L_M$ $R_M$\n$p_1$ $q_1$\n$p_2$ $q_2$\n$:$\n$p_Q$ $q_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc106_d","tags":[],"sample_group":[["2 3 1\n1 1\n1 2\n2 2\n1 2","3\n\nAs all the trains runs within the section from City $1$ to City $2$, the answer to the only query is $3$."],["10 3 2\n1 5\n2 8\n7 10\n1 7\n3 10","1\n1\n\nThe first query is on the section from City $1$ to $7$. There is only one train that runs strictly within that section: Train $1$. The second query is on the section from City $3$ to $10$. There is only one train that runs strictly within that section: Train $3$."],["10 10 10\n1 6\n2 9\n4 5\n4 7\n4 7\n5 8\n6 6\n6 7\n7 9\n10 10\n1 8\n1 9\n1 10\n2 8\n2 9\n2 10\n3 8\n3 9\n3 10\n1 10","7\n9\n10\n6\n8\n9\n6\n7\n8\n10"]],"created_at":"2026-03-03 11:01:13"}}