Masala #0175

Xotira 64 MB Vaqt 2000 ms
14
Muallif: Sirojiddin

Dasturchi Shermat

Shermat robotni \(OX\) o'qi bo'yicha harakatlantiradigan dastur tuzdi va qanchadir vaqt o’tgach robot harakatlangan nuqtalarning koordinatalarini ekranga chiqardi. Lekin Shermat har doimgidek nimanidir esdan chiqargandi. Bu safar u probellarni esdan chiqaribdi. Endi robot jami \(k\) ta nuqtaga borgani va robot borgan ixtiyoriy ikkita qo'shni nuqtalar orasidagi masofa \([l,r]\) oraliqda bo’lishini (har bir \(i \space (1 ≤ i < k)\) uchun \(l ≤ |x_i - x_i+1| ≤ r\)) hisobga olib, sizdan hozirgi ma’lumotlarni necha xil usulda tiklash mumkinligini so'ramoqda.

Yodda tuting. Nuqtani koordinatasi nomanfiy butun son bo'lib, oldida nollar bo'lmasligi lozim (0 sonini o'zidan tashqari).


Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun \(t\) soni - testlar soni beriladi \((1 ≤ t ≤ 100)\). Keyingi \(t\) ta qatorda Shermat ekranga chiqargan nuqtalarni bildiruvchi \(x\) soni, shuningdek, \(l\), \(r\), va \(k\) sonlari beriladi. \((1 ≤ x ≤ 10^{18}, 0 ≤ l, r ≤ 10^{18}, 1 ≤ k ≤ 18)\).

 


Chiquvchi ma'lumotlar:

Har bir test uchun javobni alohida qatorda chiqaring.


Misollar
# input.txt output.txt
1
4
248 16 45 2
248 16 46 2
4444 1 5 2
10010 0 100000 2
1
2
0
2