Maija works at a software company that sells its customers' information to other companies on demand. The company's database contains information about the customers' interests and is sorted by age, from youngest to oldest. The database is flooded with queries of the following form: how many people between ages [a, b] are interested in thing c? It can no longer keep up with the queries, and Maija is tasked with writing specialized software to solve this issue.

The database contains n people numbered 1, 2, \dots, n and k things people are interested in. The i-th youngest person is interested in thing a_i. There are also q preprocessed queries of the form l\ r\ x: how many people between the l-th youngest and r-th youngest (inclusive) are interested in thing x?

Input

The first line contains three integers n, k, and q. The second line contains n integers a_1,\,a_2,\dots,\,a_n. The i-th of the next q lines contains three integers l_i, r_i, and x_i.

Output

Print the answers to the queries, each on their own line.

Constraints

• 1 \leq n, k, q \leq 10^5
• 1 \leq a_i \leq k
• 1 \leq l \leq r \leq n
• 1 \leq x \leq k

Example 1

Input:

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

Output:

1
0
2
1
0

Example 2

Input:

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

Output:

2
0
2
0
3
3
2
2
5