Masala #0972

Xotira 64 MB Vaqt 1000 ms

Archa do`konida

Archasiz yangi yil bayramini tassavur qilib bo`lmasa kerak. Albatta, Asilbek ham shunday fikrda. Bundan tashqari uning fikricha archalar qancha ko`p bo`lsa shuncha yaxshi!

Ma'lum bir do`konda jami $N$ ta archalar bor. $i$-archaning narxi $a[i]$ $(dollar).

Asilbek sizga quyidagi so`rovdan $Q$ marta beradi:

$Y$ va $X$ butun sonlari kiritiladi. X $(dollar) dan ko`p pul ishlatmagan holda kamida Y ta archa xarid qilishning nechta turli xil usuli mavjud?

Sizing vazifangiz barcha so`rovlarga javob berishdir.

Ikki xarid bir xil hisoblanadi, agarda ikki xaridda ham sotib olingan archalar to`plami ustma-ust tushsa. Aks holda ular har xil.

Kiruvchi ma'lumotlar:

Birinchi qatorda yagona butun son - $N(1 \leq N \leq 50)$ kiritiladi.

Ikkinchi qatorda $N$ ta butun son - $a$ massiv elementlari $(1 \leq a[i] \leq 1000)$ kiritiladi.

Uchinchi qatorda yagona butun son - $Q(1 \leq Q \leq 5*10^5)$ so`rovlar soni kiritiladi.

Keyingi $Q$ ta qatorning har birida ikkitadan butun son - navbatdagi so`rov uchun $Y,X(1 \leq Y \leq 100, 1 \leq X \leq 2000)$ sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir so`rov uchun yangi qatorda, turli xil xaridlar usulini chop eting.

Misollar

#	input.txt	output.txt
1	3 1 2 3 7 1 1 1 2 2 2 3 3 3 6 1 10 7 12	1 2 0 0 1 7 0
2	5 300 400 100 50 177 5 3 800 6 1000 2 300 3 1200 4 977	11 0 3 16 5

Izoh:

1-test:

2-so`rov uchun xaridlar: [1], [2].

4-so`rov uchun xarid: [1,2,3].

6-so`rov uchun xaridlar: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

7-so`rov uchun xaridlar mavjud emas.

2-test:

3-so`rov uchun xaridlar: [3,4], [3,5], [4,5].

5-so`rov uchun xaridlar: [1,2,3,4], [1,2,3,5], [1,2,4,5], [1,3,4,5], [2,3,4,5].