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 their age, from youngest to oldest. The database is flooded with the following type of queries: How many people between the ages [a, b] are interested in thing c? It can no longer keep up with the queries and Maija is tasked to write some 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 pre-processed 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 𝑖-th of the next q lines contains three integers l_i, r_𝑖, 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