Dieses Problem hat einen Anhang. Du kannst ihn verwenden, um die Bewegungen der Teilchen zu simulieren und zu visualisieren.

VegiCat beobachtet Teilchen auf einem Gitter mit $n$ Zeilen und $n$ Spalten. Die untere linke Zelle hat die Koordinaten $(1, 1)$. Die horizontale Koordinate wächst von links nach rechts, und die vertikale Koordinate wächst von unten nach oben. Jedes Teilchen hat eine horizontale Richtung (links oder rechts) und eine vertikale Richtung (oben oder unten). Zu Beginn jedes Schrittes passt jedes Teilchen seine Richtungen wie folgt an:

• Seine horizontale Richtung wird umgekehrt, falls die nächste Zelle in dieser Richtung außerhalb des Gitters liegt.
• Seine vertikale Richtung wird umgekehrt, falls die nächste Zelle in dieser Richtung außerhalb des Gitters liegt.

Nach diesen Anpassungen erzeugt ein Teilchen bei $(x, y)$ zwei Kindteilchen:

• Eines bei $(x - 1, y)$, falls seine horizontale Richtung links ist, oder bei $(x + 1, y)$, falls sie rechts ist;
• Eines bei $(x, y - 1)$, falls seine vertikale Richtung unten ist, oder bei $(x, y + 1)$, falls sie oben ist.

Beide Kindteilchen erben die horizontale und vertikale Richtung des Elternteilchens. Das Elternteilchen verschwindet anschließend.

Mehrere Teilchen können unabhängig von ihren Richtungen gleichzeitig dieselbe Zelle besetzen. Sie interagieren nicht miteinander und ändern nicht die Richtungen der jeweils anderen.

Zum Zeitpunkt $0$ befinden sich vier Teilchen bei $(x_0, y_0)$ mit den folgenden Richtungspaaren:

• Rechts und oben;
• Links und oben;
• Rechts und unten;
• Links und unten.

In jedem Schritt passen alle Teilchen gleichzeitig ihre Richtungen an und teilen sich dann wie oben beschrieben auf.

Dir sind $q$ Anfragen gegeben. Jede Anfrage gibt ganze Zahlen $A, B, C$ und einen Zeitpunkt $t$ an. Bestimme für jede Anfrage die Anzahl der Gitterzellen $(x, y)$, die $Ax + By + C = 0$ erfüllen und zum Zeitpunkt $t$ mindestens ein Teilchen enthalten.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.

Die erste Zeile jedes Testfalls enthält vier ganze Zahlen $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$). Das Gitter hat $n$ Zeilen und $n$ Spalten. Die Startzelle ist $(x_0, y_0)$, und es gibt $q$ Anfragen.

Jede der nächsten $q$ Zeilen enthält vier ganze Zahlen $A, B, C$ und $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Dies beschreibt eine Anfrage für die Gerade $Ax + By + C = 0$ zum Zeitpunkt $t$. Es wird garantiert, dass $A$ und $B$ nicht gleichzeitig beide $0$ sind.

Es wird garantiert, dass die Summe von $q$ über alle Testfälle $10^5$ nicht überschreitet.

Ausgabe

Gib für jede Anfrage eine ganze Zahl in einer eigenen Zeile aus: die Anzahl der Gitterzellen $(x, y)$, die $Ax + By + C = 0$ erfüllen und zum Zeitpunkt $t$ mindestens ein Teilchen enthalten.

Beispiele

Eingabe 1

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

Ausgabe 1

1
0
0
3

Hinweis

Die folgende Abbildung zeigt die Entwicklung der Teilchen im Beispiel sowie die abgefragten Geraden, wobei die grauen Zellen diejenigen Zellen darstellen, die ganzzahlige Punkte enthalten, durch welche die Gerade verläuft, und alle Aufteilungsrichtungen bereits den Gültigkeitsanpassungen unterzogen wurden. Da die dritte Anfrage zu weit vom betrachteten Gitter entfernt liegt, wurde die Gerade der dritten Anfrage hier weggelassen.

Teilchen in derselben Zelle mit demselben Richtungspaar werden als ein einziges Symbol gezeichnet; Vielfachheiten sind weggelassen.