โจทย์ข้อนี้มีไฟล์แนบ คุณสามารถใช้มันเพื่อจำลองและแสดงภาพการเคลื่อนที่ของอนุภาคได้

VegiCat สังเกตอนุภาคบนตารางที่มี $n$ แถวและ $n$ คอลัมน์ ช่องซ้ายล่างมีพิกัดเป็น $(1, 1)$ พิกัดแนวนอนจะเพิ่มขึ้นจากซ้ายไปขวา และพิกัดแนวตั้งจะเพิ่มขึ้นจากล่างขึ้นบน แต่ละอนุภาคมีทิศทางแนวนอน (ซ้ายหรือขวา) และทิศทางแนวตั้ง (ขึ้นหรือลง) ในตอนเริ่มต้นของแต่ละก้าว แต่ละอนุภาคจะปรับทิศทางของตัวเองดังนี้:

• ทิศทางแนวนอนของมันจะถูกกลับด้าน หากช่องถัดไปในทิศทางนั้นอยู่นอกตาราง
• ทิศทางแนวตั้งของมันจะถูกกลับด้าน หากช่องถัดไปในทิศทางนั้นอยู่นอกตาราง

หลังจากปรับทิศทางเหล่านี้แล้ว อนุภาคที่ตำแหน่ง $(x, y)$ จะสร้างอนุภาคลูกสองตัว:

• ตัวหนึ่งอยู่ที่ $(x - 1, y)$ หากทิศทางแนวนอนของมันคือซ้าย หรืออยู่ที่ $(x + 1, y)$ หากเป็นขวา;
• อีกตัวหนึ่งอยู่ที่ $(x, y - 1)$ หากทิศทางแนวตั้งของมันคือลง หรืออยู่ที่ $(x, y + 1)$ หากเป็นขึ้น

อนุภาคลูกทั้งสองจะสืบทอดทิศทางแนวนอนและทิศทางแนวตั้งมาจากอนุภาคแม่ จากนั้นอนุภาคแม่จะหายไป

อนุภาคหลายตัวสามารถอยู่ในช่องเดียวกันในเวลาเดียวกันได้ไม่ว่าจะมีทิศทางใดก็ตาม พวกมันจะไม่ทำอันตรกิริยาหรือเปลี่ยนทิศทางของกันและกัน

ณ เวลา $0$ มีอนุภาคสี่ตัวอยู่ที่ $(x_0, y_0)$ โดยมีคู่ทิศทางดังต่อไปนี้:

• ขวาและขึ้น;
• ซ้ายและขึ้น;
• ขวาและลง;
• ซ้ายและลง

ในแต่ละก้าว อนุภาคทั้งหมดจะปรับทิศทางพร้อมกันแล้วจึงแตกตัวตามที่อธิบายไว้ข้างต้น

คุณได้รับคำถาม $q$ ข้อ แต่ละคำถามกำหนดจำนวนเต็ม $A, B, C$ และเวลา $t$ สำหรับแต่ละคำถาม จงหา จำนวนช่องตาราง $(x, y)$ ที่สอดคล้องกับ $Ax + By + C = 0$ และมีอนุภาคอย่างน้อยหนึ่งตัว ณ เวลา $t$

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^5$) คือจำนวนกรณีทดสอบ รายละเอียดของกรณีทดสอบมีดังต่อไปนี้

บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยจำนวนเต็มสี่ตัว $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$) ตารางมี $n$ แถวและ $n$ คอลัมน์ ช่องเริ่มต้นคือ $(x_0, y_0)$ และมีคำถาม $q$ ข้อ

แต่ละบรรทัดใน $q$ บรรทัดถัดไปประกอบด้วยจำนวนเต็มสี่ตัว $A, B, C$ และ $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$) ซึ่งอธิบายคำถามสำหรับเส้นตรง $Ax + By + C = 0$ ณ เวลา $t$ รับประกันว่า $A$ และ $B$ จะไม่เป็น $0$ พร้อมกัน

รับประกันว่าผลรวมของ $q$ จากทุกกรณีทดสอบไม่เกิน $10^5$

ข้อมูลส่งออก

สำหรับแต่ละคำถาม ให้แสดงผลจำนวนเต็มหนึ่งตัวในหนึ่งบรรทัด: จำนวนช่องตาราง $(x, y)$ ที่สอดคล้องกับ $Ax + By + C = 0$ และมีอนุภาคอย่างน้อยหนึ่งตัว ณ เวลา $t$

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

1
0
0
3

หมายเหตุ

รูปด้านล่างแสดงวิวัฒนาการของอนุภาคในตัวอย่าง รวมถึงเส้นตรงที่ถูกถาม โดยที่ช่องสีเทาแทนช่องที่มีจุดพิกัดจำนวนเต็มซึ่งเส้นตรงลากผ่าน และทิศทางการแตกตัวทั้งหมดได้รับการปรับความถูกต้องตามขอบเขตแล้ว เนื่องจากคำถามที่สามอยู่ห่างจากตารางที่พิจารณาเกินไป จึงละเส้นตรงของคำถามที่สามไว้ในที่นี้

อนุภาคในช่องเดียวกันที่มีคู่ทิศทางเดียวกันจะถูกวาดเป็นสัญลักษณ์เดียว โดยละจำนวนซ้ำไว้