Ce problème comporte une pièce jointe. Vous pouvez l'utiliser pour simuler et visualiser les déplacements des particules.

VegiCat observe des particules sur une grille de $n$ lignes et $n$ colonnes. La case en bas à gauche a pour coordonnées $(1, 1)$. La coordonnée horizontale augmente de gauche à droite, et la coordonnée verticale augmente de bas en haut. Chaque particule possède une direction horizontale (gauche ou droite) et une direction verticale (haut ou bas). Au début de chaque étape, chaque particule ajuste ses directions comme suit :

• Sa direction horizontale est inversée si la case suivante dans cette direction se trouve en dehors de la grille.
• Sa direction verticale est inversée si la case suivante dans cette direction se trouve en dehors de la grille.

Après ces ajustements, une particule située en $(x, y)$ produit deux particules filles :

• Une en $(x - 1, y)$ si sa direction horizontale est gauche, ou en $(x + 1, y)$ si elle est droite ;
• Une en $(x, y - 1)$ si sa direction verticale est bas, ou en $(x, y + 1)$ si elle est haut.

Les deux particules filles héritent des directions horizontale et verticale de leur parent. La particule parente disparaît ensuite.

Plusieurs particules peuvent occuper la même case en même temps, quelles que soient leurs directions. Elles n'interagissent pas et ne modifient pas leurs directions respectives.

À l'instant $0$, il y a quatre particules en $(x_0, y_0)$, avec les paires de directions suivantes :

• Droite et haut ;
• Gauche et haut ;
• Droite et bas ;
• Gauche et bas.

À chaque étape, toutes les particules ajustent simultanément leurs directions puis se divisent comme décrit ci-dessus.

On vous donne $q$ requêtes. Chaque requête fournit des entiers $A, B, C$ et un instant $t$. Pour chaque requête, trouvez le nombre de cases de la grille $(x, y)$ qui vérifient $Ax + By + C = 0$ et contiennent au moins une particule à l'instant $t$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^5$), le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient quatre entiers $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$). La grille comporte $n$ lignes et $n$ colonnes. La case initiale est $(x_0, y_0)$ et il y a $q$ requêtes.

Chacune des $q$ lignes suivantes contient quatre entiers $A, B, C$ et $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Cela décrit une requête pour la droite $Ax + By + C = 0$ à l'instant $t$. Il est garanti que $A$ et $B$ ne sont pas tous les deux égaux à $0$ simultanément.

Il est garanti que la somme de $q$ sur l'ensemble des cas de test ne dépasse pas $10^5$.

Sortie

Pour chaque requête, affichez un entier sur une ligne : le nombre de cases de la grille $(x, y)$ qui vérifient $Ax + By + C = 0$ et contiennent au moins une particule à l'instant $t$.

Exemples

Entrée 1

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

Sortie 1

1
0
0
3

Note

La figure ci-dessous illustre l'évolution des particules dans l'exemple ainsi que les droites interrogées, où les cases grises représentent les cases contenant des points à coordonnées entières par lesquels passe la droite, et où toutes les directions de division ont subi les ajustements de validité. Comme la troisième requête est trop éloignée de la grille considérée, la droite de la troisième requête est omise ici.

Les particules situées dans une même case avec la même paire de directions sont représentées par un seul symbole ; les multiplicités sont omises.