Bài toán này có tệp đính kèm. Bạn có thể sử dụng nó để mô phỏng và trực quan hóa chuyển động của các hạt.

VegiCat quan sát các hạt trên một lưới gồm $n$ hàng và $n$ cột. Ô ở góc dưới bên trái có tọa độ $(1, 1)$. Tọa độ ngang tăng từ trái sang phải, và tọa độ dọc tăng từ dưới lên trên. Mỗi hạt có một hướng ngang (trái hoặc phải) và một hướng dọc (lên hoặc xuống). Vào đầu mỗi bước, mỗi hạt điều chỉnh hướng của mình như sau:

• Hướng ngang của nó bị đảo ngược nếu ô tiếp theo theo hướng đó nằm ngoài lưới.
• Hướng dọc của nó bị đảo ngược nếu ô tiếp theo theo hướng đó nằm ngoài lưới.

Sau các điều chỉnh này, một hạt tại $(x, y)$ tạo ra hai hạt con:

• Một hạt tại $(x - 1, y)$ nếu hướng ngang của nó là trái, hoặc tại $(x + 1, y)$ nếu là phải;
• Một hạt tại $(x, y - 1)$ nếu hướng dọc của nó là xuống, hoặc tại $(x, y + 1)$ nếu là lên.

Cả hai hạt con đều kế thừa hướng ngang và hướng dọc của hạt cha. Sau đó hạt cha biến mất.

Nhiều hạt có thể chiếm cùng một ô tại cùng một thời điểm, bất kể hướng của chúng. Chúng không tương tác hay làm thay đổi hướng của nhau.

Tại thời điểm $0$, có bốn hạt tại $(x_0, y_0)$, với các cặp hướng sau:

• Phải và lên;
• Trái và lên;
• Phải và xuống;
• Trái và xuống.

Ở mỗi bước, tất cả các hạt đồng thời điều chỉnh hướng của mình rồi phân tách như mô tả ở trên.

Bạn được cho $q$ truy vấn. Mỗi truy vấn cho các số nguyên $A, B, C$ và thời điểm $t$. Với mỗi truy vấn, hãy tìm số lượng ô lưới $(x, y)$ thỏa mãn $Ax + By + C = 0$ và chứa ít nhất một hạt tại thời điểm $t$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), là số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Dòng đầu tiên của mỗi bộ dữ liệu chứa bốn số nguyên $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$). Lưới có $n$ hàng và $n$ cột. Ô ban đầu là $(x_0, y_0)$, và có $q$ truy vấn.

Mỗi dòng trong $q$ dòng tiếp theo chứa bốn số nguyên $A, B, C$ và $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Dòng này mô tả một truy vấn cho đường thẳng $Ax + By + C = 0$ tại thời điểm $t$. Dữ liệu đảm bảo $A$ và $B$ không đồng thời bằng $0$.

Dữ liệu đảm bảo tổng của $q$ trong tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên trên một dòng: số lượng ô lưới $(x, y)$ thỏa mãn $Ax + By + C = 0$ và chứa ít nhất một hạt tại thời điểm $t$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
0
0
3

Ghi chú

Hình dưới đây minh họa sự tiến hóa của các hạt trong ví dụ cũng như các đường thẳng được truy vấn, trong đó các ô màu xám biểu thị các ô chứa điểm nguyên mà đường thẳng đi qua, và tất cả các hướng phân tách đều đã được điều chỉnh hợp lệ. Vì truy vấn thứ ba nằm quá xa lưới đang xét nên đường thẳng của truy vấn thứ ba được lược bỏ ở đây.

Các hạt trong cùng một ô có cùng cặp hướng được vẽ bằng một ký hiệu duy nhất; bội số được lược bỏ.