408654: GYM103256 D Sightseeing with Friends

For summer vacations $$$n$$$ friends chose to go to a popular sightseeing place at the top of a hill. Once they had reached their destination, they decided to take a photo of all of them in a line. For this they asked a tourist to help them on taking the photo. The tourist nervously agreed, since he doesn't know how to use the camera properly. Not wanting to mess up, the tourist took $$$m$$$ photos of the group of friends, where in each one of them only a continuous sequence of friends is visible in the photo. This means that for the $$$i$$$-th photo, only the friends indexed from $$$l_i$$$ to $$$r_i$$$ (indexing starting from the left) can be seen in the photo.

The group of friends didn't know about this issue until they returned from the trip. Now $$$q$$$ pairs of friends want to see if from all of the photos that were taken, both of the friends appear in at least one of them. This means that if while taking the photo, the friends were standing at the $$$u$$$-th and $$$v$$$-th position respectively, they want to see if there is a photo $$$p$$$ where $$$l_p \leq u,v \leq r_p$$$.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \leq n, m, q \leq 10^6$$$) $$$-$$$ number of friends, number of photos and the number of pairs of friends.

Each of the following $$$m$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) $$$-$$$, the range of friends in the $$$i$$$-th photo.

Each of the following $$$q$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$ and $$$u \neq v$$$) $$$-$$$, the pairs of friends.

The output should contain the answer for each of the $$$q$$$ queries in order. Print Yes (case insensitive) if the respective pair of friends appears in at least one photo. Otherwise print No (case insensitive).

As input/output can reach huge size, we recommend to use fast input/output methods. For example, prefer to use scanf/printf in C++ instead of cin/cout.

6 4 3
2 5
1 2
3 6
4 5
1 3
4 5
4 6

No
Yes
Yes

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

No
Yes
No
Yes
Yes
No

In the first example, the tourist took $$$4$$$ photos:

1. In the first photo appear friends 2, 3, 4, and 5.
2. In the second photo appear friends 1 and 2.
3. In the third photo appear friends 3, 4, 5 and 6.
4. In the fourth photo appear friends 4 and 5.

There are $$$3$$$ pair of friends:

1. The first pair is formed by friends 1 and 3. They don't appear together in any photo, so the answer is no.
2. The first pair is formed by friends 4 and 5. They appear together in the first, third and fourth photos, so the answer is yes.
3. The first pair is formed by friends 4 and 6. They appear together in the first and third photos, so the answer is yes.