Detta problem har en bilaga. Du kan använda den för att simulera och visualisera partiklarnas rörelser.

VegiCat observerar partiklar på ett rutnät med $n$ rader och $n$ kolumner. Den nedre vänstra rutan har koordinaterna $(1, 1)$. Den horisontella koordinaten ökar från vänster till höger, och den vertikala koordinaten ökar nerifrån och upp. Varje partikel har en horisontell riktning (vänster eller höger) och en vertikal riktning (upp eller ner). I början av varje steg justerar varje partikel sina riktningar enligt följande:

• Dess horisontella riktning vänds om nästa ruta i den riktningen ligger utanför rutnätet.
• Dess vertikala riktning vänds om nästa ruta i den riktningen ligger utanför rutnätet.

Efter dessa justeringar producerar en partikel på $(x, y)$ två barnpartiklar:

• En på $(x - 1, y)$ om dess horisontella riktning är vänster, eller på $(x + 1, y)$ om den är höger;
• En på $(x, y - 1)$ om dess vertikala riktning är ner, eller på $(x, y + 1)$ om den är upp.

Båda barnpartiklarna ärver förälderns horisontella och vertikala riktningar. Föräldern försvinner sedan.

Flera partiklar kan befinna sig i samma ruta samtidigt, oavsett sina riktningar. De interagerar inte och ändrar inte varandras riktningar.

Vid tidpunkten $0$ finns det fyra partiklar på $(x_0, y_0)$, med följande riktningspar:

• Höger och upp;
• Vänster och upp;
• Höger och ner;
• Vänster och ner.

I varje steg justerar alla partiklar samtidigt sina riktningar och delar sig sedan enligt beskrivningen ovan.

Du får $q$ frågor. Varje fråga ger heltalen $A, B, C$ och en tidpunkt $t$. För varje fråga, bestäm antalet rutor i rutnätet $(x, y)$ som uppfyller $Ax + By + C = 0$ och innehåller minst en partikel vid tidpunkten $t$.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^5$), antalet testfall. Beskrivningen av testfallen följer.

Den första raden i varje testfall innehåller fyra heltal $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$). Rutnätet har $n$ rader och $n$ kolumner. Startrutan är $(x_0, y_0)$, och det finns $q$ frågor.

Var och en av de följande $q$ raderna innehåller fyra heltal $A, B, C$ och $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Detta beskriver en fråga för linjen $Ax + By + C = 0$ vid tidpunkten $t$. Det garanteras att $A$ och $B$ inte båda är $0$ samtidigt.

Det garanteras att summan av $q$ över alla testfall inte överstiger $10^5$.

Utdata

För varje fråga, skriv ut ett heltal på en rad: antalet rutor $(x, y)$ i rutnätet som uppfyller $Ax + By + C = 0$ och innehåller minst en partikel vid tidpunkten $t$.

Exempel

Indata 1

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

Utdata 1

1
0
0
3

Kommentar

Figuren nedan visar partikelutvecklingen i exemplet samt de efterfrågade räta linjerna, där de grå rutorna representerar rutorna med heltalskoordinater som linjen passerar igenom, och alla delningsriktningar har genomgått giltighetsjusteringar. Eftersom den tredje frågan ligger för långt bort från det betraktade rutnätet utelämnas linjen för den tredje frågan här.

Partiklar i samma ruta med samma riktningspar ritas som en enda symbol; multipliciteter utelämnas.