Cai มหาเศรษฐีผู้โดดเด่น มีความหลงใหลที่เฉพาะเจาะจงมาก: เขาจะรู้สึกสบายใจก็ต่อเมื่อเท้าของเขาวางอยู่บนขอบหรือจุดยอดของการปูกระเบื้องอย่างมั่นคง — นั่นคืออยู่บนเส้นขอบของกระเบื้องปูพื้นแผ่นใดแผ่นหนึ่ง เมื่อไม่นานมานี้ เขาได้ซื้อคอลเลกชันกระเบื้องปูพื้นรูปสามเหลี่ยมระดับไฮเอนด์ที่เหมือนกันทุกประการ เขาวางแผนที่จะใช้กระเบื้องเหล่านี้ปูทางเดินที่ยาวและตรงในคฤหาสน์หลังใหม่ของเขา
ทางเดินนี้เป็นแถบอนันต์บนระนาบสองมิติ เพื่อให้มั่นใจว่าการออกแบบเป็นไปตามมาตรฐานสูงสุดของเขา Cai ได้กำหนดกฎการปูกระเบื้องที่เข้มงวด: กระเบื้องรูปสามเหลี่ยมทุกแผ่นจะต้องวางให้พาดผ่านความกว้างทั้งหมดของทางเดิน โดยสัมผัสกับเส้นขอบที่ขนานกันทั้งสองเส้น สิ่งนี้จะสร้าง เทสเซลเลชัน (tessellation) แถวเดียวที่ต่อเนื่องกันของแถบ กระเบื้องแผ่นหนึ่งจะต้องตรงกับรูปสามเหลี่ยมอ้างอิงที่เขาชื่นชอบทุกประการ และกระเบื้องแผ่นอื่นๆ ทั้งหมดจะต้องเท่ากันทุกประการกับรูปสามเหลี่ยมนั้น
ปัจจุบัน Cai ยืนอยู่ที่ตำแหน่งคงที่ในโถงทางเดิน เขาเหนื่อยล้าหลังจากทำงานปรับสภาพพื้นผิวโลกมาทั้งวัน และพูดตามตรงคือเขาจะไม่ขยับไปไหนเลย เขาต้องการให้กระเบื้องขยายตัวออกไปทั่วพื้นโดยอัตโนมัติโดยเริ่มจากรูปสามเหลี่ยมอ้างอิงของเขา ตราบใดที่ลวดลายที่ได้เป็นไปตามกฎของเขา แน่นอนว่ามันจะสำเร็จก็ต่อเมื่อขอบหรือจุดยอดของกระเบื้องตรงกับตำแหน่งปัจจุบันของเขาพอดี!
งานของคุณคือพิจารณาว่าเป็นไปได้หรือไม่ที่จะปูกระเบื้องทางเดิน بحيث ตำแหน่งปัจจุบันของ Cai คือจุด $D$ อยู่บนขอบหรือจุดยอดของ เทสเซลเลชัน ที่มี $\triangle ABC$ พอดี ขอบของทางเดินถูกนิยามว่าเป็นเส้นขนานสองเส้นที่ไม่ซ้ำกัน $l_1$ และ $l_2$ ซึ่ง $l_1$ ผ่านจุด $A$ และ $B$ และ $l_2$ ผ่านจุด $C$ เทสเซลเลชัน ของแถบที่เกิดจาก $(l_1, l_2)$ คือการปูกระเบื้องทั่วทั้งแถบโดยใช้สำเนาที่เท่ากันทุกประการของรูปสามเหลี่ยม $\triangle ABC$ (อนุญาตให้เลื่อนขนาน หมุน และสะท้อนได้) โดยไม่มีการทับซ้อนและไม่มีช่องว่าง
ภาพประกอบของชุดข้อมูลทดสอบตัวอย่างสองชุดแรก
ข้อมูลนำเข้า
มีข้อมูลทดสอบหลายชุด บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^3$) แสดงจำนวนชุดข้อมูลทดสอบ สำหรับข้อมูลทดสอบแต่ละชุด:
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $x_a$ และ $y_a$ ($-100 \le x_a, y_a \le 100$) คือพิกัดของจุด $A$
บรรทัดที่สองประกอบด้วยจำนวนเต็มสองจำนวน $x_b$ และ $y_b$ ($-100 \le x_b, y_b \le 100$) คือพิกัดของจุด $B$
บรรทัดที่สามประกอบด้วยจำนวนเต็มสองจำนวน $x_c$ และ $y_c$ ($-100 \le x_c, y_c \le 100$) คือพิกัดของจุด $C$
บรรทัดที่สี่ประกอบด้วยเศษส่วนสองจำนวน $x_{d1}/x_{d2}$ และ $y_{d1}/y_{d2}$ โดยที่ $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ เป็นจำนวนเต็มที่สอดคล้องกับ $-10^7 < x_{d1}, y_{d1} < 10^7$ และ $0 < x_{d2}, y_{d2} < 10^7$ แทนพิกัดของจุด $D$
รับประกันว่า $A$, $B$ และ $C$ ประกอบกันเป็นรูปสามเหลี่ยมที่ไม่ลดรูป
ข้อมูลส่งออก
สำหรับข้อมูลทดสอบแต่ละชุด ให้แสดงผล "Yes" ในหนึ่งบรรทัด หากมีเทสเซลเลชันที่ถูกต้องซึ่งทำให้จุด $D$ อยู่บนขอบหรือจุดยอดของรูปสามเหลี่ยมอย่างน้อยหนึ่งรูปในลวดลาย มิฉะนั้นให้แสดงผล "No"
ตัวอย่าง
ข้อมูลนำเข้า 1
4 -2 1 0 0 0 2 2/1 0/1 -2 1 0 0 0 2 1/1 0/1 0 1 -2 1 0 2 1/2 7/4 0 1 -2 1 0 2 -3/2 3/4
ข้อมูลส่งออก 1
Yes No Yes No