题目背景

もしも もう一度 あなたに会えるなら

如果 能够再次与您相遇

たった一言伝えたい ありがとう ありがとう

我只想告诉您一句话 谢谢您 谢谢您

—— KOKIA「ありがとう…」

题目描述

Misaka Mikoto 给你一个长度为 $n$ 的序列 $[a_1, \dots, a_n]$ 和 $m$ 个区间 $[l_1,r_1], \dots, [l_m,r_m]$。

Misaka Mikoto 有 $q$ 次询问 $L, R, k$，对于每一次询问，请你求出：

输入格式

第一行包含三个正整数 $n, m, q$。

接下来一行，$n$ 个正整数 $a_1, \ldots, a_n$。

接下来 $m$ 行，第 $i$ 行包含两个正整数 $l_i, r_i$。

接下来 $q$ 行，每行有三个正整数 $L, R, k$，依次表示每次询问。

输出格式

输出共 $q$ 行。第 $i$ 行一个整数，表示第 $i$ 次询问的答案。

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

提示

本题采用捆绑测试。

• Subtask 1（5 分）：$n,m,q\le 500$。
• Subtask 2（5 分）：$n,m,q\le 5000$。
• Subtask 3（5 分）：序列 $a$ 中至多有 $100$ 种元素。
• Subtask 4（5 分）：序列 $a$ 中每种元素至多出现 $10$ 次。
• Subtask 5（20 分）：$n,m,q\le 5\times 10^4$。
• Subtask 6（20 分）：$n,m,q\le 10^5$。
• Subtask 7（40 分）：无特殊限制。

对于 $100\%$ 数据，$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$。