Daniel and sszcdjr are playing a game. The game is played on a sequence of length . Initially, all elements in are equal to . They will do the following operations times on it:

* Daniel selects one segment ();
* Then, sszcdjr chooses a real number such that \bf{uniformly at random};
* For all , set .

However, sszcdjr thinks it is unfair for him. So he adds a rule: for any two segments and (), one of the following condition must holds:

* The two segments are completely disjoint. More formally, either or ;
* One of the two segments are inside another. More formally, either or .

Note that two segments can be exactly the same.

Let be the maximum number in after the operations. zxx is crazy about probabilities, so he gives you queries. In each query, he gives you two numbers , , and asks you the probability that . You just need to tell him the answer modulo .

The first line of input contains three integers , ,  (,  ) --- the length of the sequence, the number of operations and the number of queries.

Then  lines follow, the -th line contains two integers ,  () --- the segment in the -th operation.

In the following  lines, each line contains two integers ,  () --- the two numbers piggy give you in the query are equal to  and  .

For each query print an integer --- the probability that , modulo . 

Formally, let . It can be shown that the answer can be expressed as an irreducible fraction , where  and  are integers and . Output the integer equal to . In other words, output such an integer  that  and .

6 3 5
1 6
2 3
4 5
0 1000000
1000000 2000000
200000 800000
0 1500000
114 514

332748118
665496236
143747187
540715692
586651392