Masala #0972

Xotira 64 MB Vaqt 1000 ms
14

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].