Бұл есептің тіркемесі бар. Оны бөлшектердің қозғалысын модельдеу және визуализациялау үшін пайдалана аласыз.

VegiCat $n$ жол мен $n$ бағаннан тұратын тордағы бөлшектерді бақылайды. Төменгі сол жақ ұяшықтың координаталары $(1, 1)$. Көлденең координата солдан оңға қарай, ал тік координата төменнен жоғары қарай өседі. Әрбір бөлшектің көлденең бағыты (солға немесе оңға) және тік бағыты (жоғары немесе төмен) бар. Әр қадамның басында әрбір бөлшек өз бағыттарын келесідей реттейді:

• Егер оның көлденең бағытындағы келесі ұяшық тордан тыс болса, көлденең бағыты қарама-қарсыға өзгереді.
• Егер оның тік бағытындағы келесі ұяшық тордан тыс болса, тік бағыты қарама-қарсыға өзгереді.

Осы реттеулерден кейін $(x, y)$ ұяшығындағы бөлшек екі туынды бөлшек түзеді:

• Көлденең бағыты солға болса $(x - 1, y)$ ұяшығында, ал оңға болса $(x + 1, y)$ ұяшығында біреу;
• Тік бағыты төмен болса $(x, y - 1)$ ұяшығында, ал жоғары болса $(x, y + 1)$ ұяшығында біреу.

Екі туынды бөлшек те аталық бөлшектің көлденең және тік бағыттарын мұраға алады. Содан кейін аталық бөлшек жойылады.

Бағыттарына қарамастан, бірнеше бөлшек бір уақытта бір ұяшықта орналаса алады. Олар өзара әрекеттеспейді және бір-бірінің бағытын өзгертпейді.

$0$ уақыт мезетінде $(x_0, y_0)$ ұяшығында келесі бағыт жұптары бар төрт бөлшек орналасқан:

• Оңға және жоғары;
• Солға және жоғары;
• Оңға және төмен;
• Солға және төмен.

Әр қадамда барлық бөлшектер бір мезгілде өз бағыттарын реттеп, содан кейін жоғарыда сипатталғандай бөлінеді.

Сізге $q$ сұраныс берілген. Әрбір сұраныста бүтін $A, B, C$ сандары мен $t$ уақыт мезеті беріледі. Әрбір сұраныс үшін $Ax + By + C = 0$ теңдеуін қанағаттандыратын және $t$ уақыт мезетінде кемінде бір бөлшегі бар тор ұяшықтарының $(x, y)$ санын табыңыз.

Кіріс деректер

Бірінші жолда тесттер санын білдіретін бүтін $T$ ($1 \le T \le 10^5$) саны берілген. Одан кейін тесттердің сипаттамасы беріледі.

Әрбір тесттің бірінші жолында төрт бүтін сан $n, x_0, y_0, q$ ($2 \le n \le 10^9$, $1 \le x_0, y_0 \le n$, $1 \le q \le 10^5$) берілген. Тор $n$ жол мен $n$ бағаннан тұрады. Бастапқы ұяшық — $(x_0, y_0)$, ал сұраныстар саны — $q$.

Келесі $q$ жолдың әрқайсысында төрт бүтін сан $A, B, C$ және $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$) берілген. Бұл $t$ уақыт мезетіндегі $Ax + By + C = 0$ түзуіне арналған сұранысты сипаттайды. $A$ мен $B$ бір мезгілде $0$-ге тең болмайтынына кепілдік беріледі.

Барлық тесттер бойынша $q$ мәндерінің қосындысы $10^5$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір сұраныс үшін жеке жолға бір бүтін сан шығарыңыз: $t$ уақыт мезетінде $Ax + By + C = 0$ шартын қанағаттандыратын және кемінде бір бөлшегі бар $(x, y)$ тор ұяшықтарының саны.

Мысалдар

Кіріс деректер 1

1
6 5 5 4
2 -1 -5 0
1 -1 0 1
11 45 14 2
1 0 -5 3

Шығыс деректер 1

1
0
0
3

Ескертпе

Төмендегі суретте мысалдағы бөлшектердің эволюциясы мен сұралған түзулер көрсетілген, мұндағы сұр ұяшықтар түзу өтетін бүтін координаталы нүктелері бар ұяшықтарды білдіреді, ал барлық бөліну бағыттары заңдылық тексерісінен өткен. Үшінші сұраныс қарастырылып отырған тордан тым алыс болғандықтан, үшінші сұраныстың түзуі бұл жерде көрсетілмеген.

Бір ұяшықтағы бағыт жұптары бірдей бөлшектер бір таңба ретінде салынған; еселіктері түсіріліп тасталған.