Description

Misaka Mikoto gives you a sequence $[a_1, \dots, a_n]$ of length $n$ and $m$ intervals $[l_1, r_1], \dots, [l_m, r_m]$.

There are $q$ queries in the form $L, R, k$. For each query, compute:

Input Format

The first line contains three positive integers $n, m, q$.

The second line contains $n$ positive integers $a_1, \ldots, a_n$.

The next $m$ lines each contain two positive integers $l_i, r_i$.

The next $q$ lines each contain three positive integers $L, R, k$, representing the queries.

Output Format

Output $q$ lines. The $i$-th line should contain the answer to the $i$-th query.

1 1 1
1
1 1
1 1 1

1

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

1
3
1
2
2
2
3
0

15 15 15
11 14 1 5 5 5 5 4 10 2 5 1 4 5 4
10 14
2 7
7 12
6 10
4 5
5 11
3 15
3 7
3 8
1 6
8 11
14 14
5 8
8 12
4 5
8 15 2
12 13 5
8 12 5
7 12 11
7 12 10
2 11 11
10 10 10
5 13 11
11 14 11
2 4 4
13 14 1
4 8 11
7 12 5
3 5 11
10 15 11

1
3
4
1
1
1
0
1
0
1
1
0
6
0
1

20 20 20
12 1 20 1 1 11 11 1 11 12 11 17 12 1 11 12 20 12 17 17
4 7
6 7
10 20
17 19
2 4
6 6
17 19
10 12
14 15
12 13
7 19
8 16
8 11
4 6
16 18
3 8
16 20
4 5
7 10
6 19
6 8 20
2 6 12
1 3 17
4 5 12
13 14 12
2 8 11
7 11 12
3 4 20
12 15 20
19 19 1
4 4 1
1 8 1
7 15 20
2 8 17
8 16 12
4 12 1
12 17 1
4 9 11
2 7 1
1 15 17

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

Hint

This problem uses bundled tests.

• Subtask 1 (5 points): $n, m, q \le 500$.
• Subtask 2 (5 points): $n, m, q \le 5000$.
• Subtask 3 (5 points): At most 100 distinct elements in sequence $a$.
• Subtask 4 (5 points): Each element in $a$ appears at most 10 times.
• Subtask 5 (20 points): $n, m, q \le 5 \times 10^4$.
• Subtask 6 (20 points): $n, m, q \le 10^5$.
• Subtask 7 (40 points): No additional constraints.

For $100\%$ data: $1 \le n, m, q \le 2 \times 10^5$, $1 \le a_i, k \le n$, $1 \le l_i \le r_i \le n$, $1 \le L \le R \le m$.

Translated by DeepSeek R1