Problem Description

In the Kingdom of Takahashi, there are $ N $ towns numbered from $ 1 $ to $ N $.

There are $ K $ types of ethnic groups living in the Kingdom of Takahashi, and the $ i $-th ethnic group lives in town $ S_i $.

The ethnic groups in the Kingdom of Takahashi have a culture called "National Migration" where they change their living town once every hundred years. Normally, all ethnic groups conduct the "National Migration" at the same time. However, to prevent congestion, the following movement restrictions are set each day for $ D $ days:

• On the $ i $-th day, movement between towns with numbers from $ L_i $ to $ R_i $ is allowed. Movement to other towns is prohibited.

Each ethnic group adheres to these movement restrictions and moves to their destination town via several towns.

The destination of the $ i $-th ethnic group is town $ T_i $. Each ethnic group wants to arrive at their destination as soon as possible.

For each ethnic group, determine the earliest day they can arrive at their destination.

It is guaranteed that every ethnic group can reach their destination within $ D $ days.

Input Format

The input is given from the standard input in the following format:

$ N $ $ D $ $ K $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ : $ L_D $ $ R_D $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ : $ S_K $ $ T_K $

• The first line contains the number of towns in the Kingdom of Takahashi $N(1\ ≦\ N\ ≦\ 10^9)$, the number of days for the migration $D(1\ ≦\ D\ ≦\ 10^4)$, and the number of ethnic groups living in the Kingdom of Takahashi $K(1\ ≦\ K\ ≦\ 100)$, separated by spaces.
• The next $ D $ lines, where the $ i $-th line contains two integers $L_i,\ R_i(1\ ≦\ L_i\ ≦\ R_i\ ≦\ N)$ representing the movement restrictions for the $ i $-th day, separated by spaces.
• The next $ K $ lines, where the $ i $-th line contains two integers $S_i(\ 1\ ≦\ S_i\ ≦\ N)$ and $T_i\ (1\ ≦\ T_i\ ≦\ N)$ representing the initial town and the destination town of the $ i $-th ethnic group, separated by spaces. It holds that $S_i\ ≠\ T_i$.
• It is guaranteed that every ethnic group can reach their destination within $ D $ days.

Output Format

The output consists of $ K $ lines. The $ i $-th line should contain the earliest day the $ i $-th ethnic group can arrive at their destination. Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

10 10 3
1 5
3 6
7 10
5 8
4 4
1 4
2 9
1 3
1 1
4 5
1 6
2 7
10 1

Sample Output #1

2
4
8

Sample Input #2

10 10 4
1 2
2 4
3 6
4 8
5 10
9 10
7 8
5 6
3 5
1 3
10 1
3 8
2 4
1 3

Sample Output #2

10
4
2
2

Sample Input #3

314159265 10 1
1 10000
500 12031
1414 113232
111111 777777
666661 23423423
12345678 123456789
111111111 314159265
112334 235235235
1 223445
314 1592
1 314159265

Sample Output #3

7

Notes/Hints

Sample Explanation 1

The first ethnic group can arrive at their destination in 2 days by moving as follows, which is the earliest possible:
- Move from town $ 1 $ to town $ 4 $ on the first day.
- Move from town $ 4 $ to town $ 6 $ on the second day.

The second ethnic group can arrive at their destination in 4 days by moving as follows, which is the earliest possible:
- Move from town $ 2 $ to town $ 5 $ on the first day.
- Move from town $ 5 $ to town $ 7 $ on the fourth day.

The third ethnic group can arrive at their destination in 8 days by moving as follows, which is the earliest possible:
- Move from town $ 10 $ to town $ 9 $ on the third day.
- Move from town $ 9 $ to town $ 3 $ on the seventh day.
- Move from town $ 3 $ to town $ 1 $ on the eighth day.

见题面 Input 部分

见题面 Output 部分