Get Smaller Items

Each closed-range order contributes all item values in its range to a multiset; an item covered by different orders is counted repeatedly. For each query value, count the elements of the multiset strictly smaller than it.

输入格式

The first line contains n m q (each 1..100000); the second line contains n item values; each of the next m lines contains l r (0≤l≤r<n); the last line contains q query values. Item values and query values are all in 1..10⁹.

输出格式

Output q integers in query order.

样例 1

输入：

5 3 2
1 2 5 4 5
0 1
0 2
1 2
2 4

输出：

2 5

样例 2

输入：

1 1 2
1
0 0
1 2

输出：

0 1

样例 3

输入：

2 2 2
5 5
0 1
1 1
5 6

输出：

0 3

样例说明

Example 1: in the multiset, 1 occurs 2 times, 2 occurs 3 times and 5 occurs 2 times, so 2 elements are smaller than 2 and 5 are smaller than 4. Example 2: the only element 1 is not smaller than 1 but is smaller than 2, so output 0 1. Example 3: the two orders contribute three 5s in total, so 0 are smaller than 5 and 3 are smaller than 6.