Masala #1156

Xotira 256 MB Vaqt 3000 ms

Robolandiya poyezdlari

Robolandiya mamlakatida \(N\) ta shahar mavjud. Har bir shahar ketma-ket joylashgan va har biri tartib bilan raqamlangan. Bundan tashqari, ushbu shaharlar orasida qatnovchi \(M\) ta poyezd bor. \(i-\)poyezd \(L_i\) - \(R_i\) shaharlari orasida qatnaydi \((1 \le L_i \le R_i \le N)\).

Robolandiya qiroli ushbu poyezdlarga qiziqib qoldi va endi u vazirlaridan so'ramoqda: ″\(p_i\) va \(q_i\) shaharlari orasida qatnovchi nechta poyezd bor?″.

Sizning vazifangiz quyidagi shartni qanoatlantiruvchi poyezdlar sonini topishdir.

\(p_i \le L_j \le R_j \le q_i\).

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida uchta butun son - N, M, Q - shaharlar, poyezdlar va so'rovlar soni \((1 \le N \le 500, 1 \le M , Q \le 2*10^6)\).

Keyingi M ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(L_i\) va \(R_i\) mavjud.

Keyingi Q ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(p_i\) va \(q_i\) mavjud.

Chiquvchi ma'lumotlar:

Chiqish faylining Q ta qatorida, har bir so'rov uchun ushbu oraliqda harakatlanuvchi poyezdlar sonini chop eting.

Misollar

#	input.txt	output.txt
1	2 3 1 1 1 1 2 2 2 1 2	3
2	5 10 5 3 4 1 4 1 2 1 1 2 5 2 5 1 2 1 3 3 5 3 4 1 2 1 1 5 5 1 5 2 4	3 1 0 10 2