{"raw_statement":[{"iden":"problem statement","content":"There are $N$ cities numbered $1$ through $N$, and $M$ buses that go between these cities. The $i$\\-th bus $(1 \\leq i \\leq M)$ departs from City $A_i$ at time $S_i+0.5$ and arrive at City $B_i$ at time $T_i+0.5$.\nTakahashi will travel between these $N$ cities. When he is in City $p$ at time $t$, he will do the following.\n\n1.  If there is a bus that departs from City $p$ not earlier than time $t$, take the bus that departs the earliest among those buses to get to another city.\n2.  If there is no such bus, do nothing and stay in City $p$.\n\nTakahashi repeats doing the above until there is no bus to take. It is guaranteed that all $M$ buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible.\nHere is your task: process $Q$ queries, the $i$\\-th $(1 \\leq i \\leq Q)$ of which is as follows.\n\n*   If Takahashi begins his travel in City $Y_i$ at time $X_i$, in which city or on which bus will he be at time $Z_i$?"},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq A_i,B_i \\leq N\\ (1 \\leq i \\leq M)$\n*   $A_i \\neq B_i\\ (1 \\leq i \\leq M)$\n*   $1 \\leq S_i \\lt T_i \\leq 10^9\\ (1 \\leq i \\leq M)$\n*   $S_i \\neq S_j\\ (i \\neq j)$\n*   $1 \\leq X_i \\lt Z_i \\leq 10^9\\ (1 \\leq i \\leq Q)$\n*   $1 \\leq Y_i \\leq N\\ (1 \\leq i \\leq Q)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$A_1$ $B_1$ $S_1$ $T_1$\n$A_2$ $B_2$ $S_2$ $T_2$\n$\\hspace{1.8cm}\\vdots$\n$A_M$ $B_M$ $S_M$ $T_M$\n$X_1$ $Y_1$ $Z_1$\n$X_2$ $Y_2$ $Z_2$\n$\\hspace{1.2cm}\\vdots$\n$X_Q$ $Y_Q$ $Z_Q$"},{"iden":"sample input 1","content":"3 2 3\n1 2 1 3\n2 3 3 5\n1 1 5\n2 2 3\n1 3 2"},{"iden":"sample output 1","content":"2 3\n2\n3\n\nIn the first query, Takahashi will travel as follows.\n\n1.  Start in City $1$ at time $1$.\n2.  Take the bus that departs from City $1$ at time $1.5$ and arrives at City $2$ at time $3.5$.\n3.  Take the bus that departs from City $2$ at time $3.5$ and arrives at City $3$ at time $5.5$.\n4.  Since no bus departs from City $3$ at time $5.5$ or later, stay in City $3$ (forever).\n\nAt time $5$, he will be on the bus that departs from City $2$ and arrives at City $3$. Thus, as specified in the Output section, we should print $2$ and $3$ with a space between them."},{"iden":"sample input 2","content":"8 10 10\n4 3 329982133 872113932\n6 8 101082040 756263297\n4 7 515073851 793074419\n8 7 899017043 941751547\n5 7 295510441 597348810\n7 2 688716395 890599546\n6 1 414221915 748470452\n6 4 810915860 904512496\n3 1 497469654 973509612\n4 1 307142272 872178157\n374358788 4 509276232\n243448834 6 585993193\n156350864 4 682491610\n131643541 8 836902943\n152874385 6 495945159\n382276121 1 481368090\n552433623 2 884584430\n580376205 2 639442239\n108790644 7 879874292\n883275610 1 994982498"},{"iden":"sample output 2","content":"4\n6 1\n4 1\n8\n6 1\n1\n2\n2\n7 2\n1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}