Þetta dæmi er með viðhengi. Þú getur notað það til að herma eftir og sjónræna hreyfingar agnanna.

VegiCat fylgist með ögnum á grind með $n$ röðum og $n$ dálkum. Neðsti reiturinn til vinstri hefur hnit $(1, 1)$. Lárétta hnitið vex frá vinstri til hægri og lóðrétta hnitið vex neðan frá og upp. Hver ögn hefur lárétta stefnu (vinstri eða hægri) og lóðrétta stefnu (upp eða niður). Í upphafi hvers skrefs lagar hver ögn stefnur sínar sem hér segir:

• Láréttri stefnu hennar er snúið við ef næsti reitur í þeirri stefnu er utan grindarinnar.
• Lóðréttri stefnu hennar er snúið við ef næsti reitur í þeirri stefnu er utan grindarinnar.

Eftir þessar lagfæringar býr ögn í $(x, y)$ til tvær afkvæmaagnir:

• Eina í $(x - 1, y)$ ef lárétt stefna hennar er vinstri, eða í $(x + 1, y)$ ef hún er hægri;
• Eina í $(x, y - 1)$ ef lóðrétt stefna hennar er niður, eða í $(x, y + 1)$ ef hún er upp.

Báðar afkvæmaagnirnar erfa lárétta og lóðrétta stefnu foreldrisins. Foreldrið hverfur síðan.

Margar agnir geta verið í sama reit á sama tíma, óháð stefnum þeirra. Þær hafa engin áhrif hver á aðra og breyta ekki stefnum hver annarrar.

Á tíma $0$ eru fjórar agnir í $(x_0, y_0)$ með eftirfarandi stefnupör:

• Hægri og upp;
• Vinstri og upp;
• Hægri og niður;
• Vinstri og niður.

Í hverju skrefi laga allar agnir stefnur sínar samtímis og skipta sér svo eins og lýst er hér að ofan.

Þér eru gefnar $q$ fyrirspurnir. Hver fyrirspurn gefur heiltölur $A, B, C$ og tíma $t$. Fyrir hverja fyrirspurn skal finna fjölda reita á grindinni $(x, y)$ sem uppfylla $Ax + By + C = 0$ og innihalda að minnsta kosti eina ögn á tíma $t$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^5$), fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.

Fyrsta línan í hverju prófunartilfelli inniheldur fjórar heiltölur $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$). Grindin hefur $n$ raðir og $n$ dálka. Upphafsreiturinn er $(x_0, y_0)$, og það eru $q$ fyrirspurnir.

Hver af næstu $q$ línum inniheldur fjórar heiltölur $A, B, C$ og $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Þetta lýsir fyrirspurn fyrir línuna $Ax + By + C = 0$ á tíma $t$. Tryggt er að $A$ og $B$ séu ekki bæði $0$ samtímis.

Tryggt er að summa $q$ yfir öll prófunartilfelli fari ekki yfir $10^5$.

Úttak

Fyrir hverja fyrirspurn skal prenta eina heiltölu á einni línu: fjölda reita $(x, y)$ á grindinni sem uppfylla $Ax + By + C = 0$ og innihalda að minnsta kosti eina ögn á tíma $t$.

Dæmi

Inntak 1

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

Úttak 1

1
0
0
3

Athugasemd

Myndin hér að neðan sýnir þróun agnanna í dæminu ásamt beinu línunum sem spurt er um, þar sem gráu reitirnir tákna reitina sem innihalda heiltölupunkta sem línan fer í gegnum, og allar skiptingarstefnur hafa gengist undir lögmætislagfæringar. Þar sem þriðja fyrirspurnin er of langt frá grindinni sem um ræðir er línunni úr þriðju fyrirspurninni sleppt hér.

Agnir í sama reit með sama stefnupar eru teiknaðar sem eitt tákn; margfeldni er sleppt.