Dette problemet har et vedlegg. Du kan bruke det til å simulere og visualisere partiklenes bevegelser.

VegiCat observerer partikler på et rutenett med $n$ rader og $n$ kolonner. Cellen nederst til venstre har koordinater $(1, 1)$. Den horisontale koordinaten øker fra venstre mot høyre, og den vertikale koordinaten øker nedenfra og opp. Hver partikkel har en horisontal retning (venstre eller høyre) og en vertikal retning (opp eller ned). På begynnelsen av hvert steg justerer hver partikkel retningene sine som følger:

• Dens horisontale retning snus hvis neste celle i den retningen er utenfor rutenettet.
• Dens vertikale retning snus hvis neste celle i den retningen er utenfor rutenettet.

Etter disse justeringene produserer en partikkel i $(x, y)$ to barnepartikler:

• Én i $(x - 1, y)$ hvis dens horisontale retning er venstre, eller i $(x + 1, y)$ hvis den er høyre;
• Én i $(x, y - 1)$ hvis dens vertikale retning er ned, eller i $(x, y + 1)$ hvis den er opp.

Begge barnepartiklene arver forelderens horisontale og vertikale retninger. Forelderen forsvinner deretter.

Flere partikler kan befinne seg i samme celle samtidig, uavhengig av retningene deres. De påvirker ikke hverandre og endrer ikke hverandres retninger.

Ved tid $0$ er det fire partikler i $(x_0, y_0)$, med følgende retningspar:

• Høyre og opp;
• Venstre og opp;
• Høyre og ned;
• Venstre og ned.

I hvert steg justerer alle partikler retningene sine samtidig og deler seg deretter som beskrevet ovenfor.

Du får $q$ spørringer. Hver spørring gir heltall $A, B, C$ og en tid $t$. For hver spørring, finn antallet rutenettceller $(x, y)$ som oppfyller $Ax + By + C = 0$ og inneholder minst én partikkel ved tid $t$.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen i hvert testtilfelle inneholder fire heltall $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$). Rutenettet har $n$ rader og $n$ kolonner. Startcellen er $(x_0, y_0)$, og det er $q$ spørringer.

Hver av de neste $q$ linjene inneholder fire heltall $A, B, C$ og $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Dette beskriver en spørring for linjen $Ax + By + C = 0$ ved tid $t$. Det er garantert at $A$ og $B$ ikke begge er $0$ samtidig.

Det er garantert at summen av $q$ over alle testtilfeller ikke overstiger $10^5$.

Utdata

For hver spørring, skriv ut ett heltall på én linje: antallet rutenettceller $(x, y)$ som oppfyller $Ax + By + C = 0$ og inneholder minst én partikkel ved tid $t$.

Eksempler

Inndata 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

Merk

Figuren nedenfor viser partikkelutviklingen i eksempelet samt de etterspurte rette linjene, der de grå cellene representerer cellene med heltallspunkter som den rette linjen går gjennom, og alle delingsretninger har gjennomgått gyldighetsjusteringer. Siden den tredje spørringen er for langt unna det betraktede rutenettet, er linjen for den tredje spørringen utelatt her.

Partikler i samme celle med samme retningspar er tegnet som ett enkelt symbol; multiplisiteter er utelatt.