Tässä tehtävässä on liitetiedosto. Voit käyttää sitä hiukkasten liikkeiden simulointiin ja visualisointiin.

VegiCat tarkkailee hiukkasia ruudukossa, jossa on $n$ riviä ja $n$ saraketta. Vasemman alakulman ruudun koordinaatit ovat $(1, 1)$. Vaakakoordinaatti kasvaa vasemmalta oikealle ja pystykoordinaatti alhaalta ylös. Jokaisella hiukkasella on vaakasuunta (vasen tai oikea) ja pystysuunta (ylös tai alas). Jokaisen askeleen alussa jokainen hiukkanen mukauttaa suuntiaan seuraavasti:

• Sen vaakasuunta käännetään päinvastaiseksi, jos seuraava ruutu kyseisessä suunnassa on ruudukon ulkopuolella.
• Sen pystysuunta käännetään päinvastaiseksi, jos seuraava ruutu kyseisessä suunnassa on ruudukon ulkopuolella.

Näiden mukautusten jälkeen ruudussa $(x, y)$ oleva hiukkanen tuottaa kaksi lapsihiukkasta:

• Yhden ruutuun $(x - 1, y)$, jos sen vaakasuunta on vasen, tai ruutuun $(x + 1, y)$, jos se on oikea;
• Yhden ruutuun $(x, y - 1)$, jos sen pystysuunta on alas, tai ruutuun $(x, y + 1)$, jos se on ylös.

Molemmat lapsihiukkaset perivät vanhemman vaaka- ja pystysuunnan. Tämän jälkeen vanhempi katoaa.

Useat hiukkaset voivat olla samassa ruudussa samaan aikaan suunnistaan riippumatta. Ne eivät vuorovaikuta keskenään eivätkä muuta toistensa suuntia.

Ajanhetkellä $0$ ruudussa $(x_0, y_0)$ on neljä hiukkasta, joilla on seuraavat suuntaparit:

• Oikea ja ylös;
• Vasen ja ylös;
• Oikea ja alas;
• Vasen ja alas.

Jokaisella askeleella kaikki hiukkaset mukauttavat samanaikaisesti suuntiaan ja jakautuvat sitten yllä kuvatulla tavalla.

Sinulle annetaan $q$ kyselyä. Jokaisessa kyselyssä annetaan kokonaisluvut $A, B, C$ sekä ajanhetki $t$. Selvitä jokaiselle kyselylle ruudukon niiden ruutujen $(x, y)$ lukumäärä, jotka toteuttavat yhtälön $Ax + By + C = 0$ ja sisältävät vähintään yhden hiukkasen ajanhetkellä $t$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), testitapausten lukumäärän. Seuraavaksi annetaan testitapausten kuvaukset.

Jokaisen testitapauksen ensimmäinen rivi sisältää neljä kokonaislukua $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$). Ruudukossa on $n$ riviä ja $n$ saraketta. Alkuruutu on $(x_0, y_0)$, ja kyselyjä on $q$.

Jokainen seuraavista $q$ rivistä sisältää neljä kokonaislukua $A, B, C$ ja $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Tämä kuvaa suoraa $Ax + By + C = 0$ koskevaa kyselyä ajanhetkellä $t$. On taattu, etteivät $A$ ja $B$ ole molemmat samanaikaisesti $0$.

On taattu, että lukujen $q$ summa yli kaikkien testitapausten on enintään $10^5$.

Tuloste

Tulosta jokaiselle kyselylle yksi kokonaisluku omalle rivilleen: niiden ruudukon ruutujen $(x, y)$ lukumäärä, jotka toteuttavat yhtälön $Ax + By + C = 0$ ja sisältävät vähintään yhden hiukkasen ajanhetkellä $t$.

Esimerkit

Syöte 1

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

Tuloste 1

1
0
0
3

Huomautus

Alla oleva kuva esittää hiukkasten kehitystä esimerkissä sekä kysellyt suorat, missä harmaat ruudut esittävät niitä kokonaislukupisteitä sisältäviä ruutuja, joiden kautta suora kulkee, ja kaikki jakautumissuunnat on jo mukautettu laillisiksi. Koska kolmas kysely on liian kaukana tarkasteltavasta ruudukosta, kolmannen kyselyn suora on jätetty tästä pois.

Samassa ruudussa olevat hiukkaset, joilla on sama suuntapari, on piirretty yhtenä symbolina; moninkertaisuudet on jätetty pois.