小葱 กับ 小绪 เป็นเพื่อนสนิทกัน ตั้งแต่ 小葱 สุ่มแบบ 11 ครั้งแล้วได้ 1UR2SR มา 小绪 ก็คิดว่า 小葱 ดวงดีมาก จึงตั้งโจทย์ให้ 小葱 เพื่อทดสอบดวงของเขา

เริ่มแรก 小绪 วาดจุด $N$ จุดบนระนาบ ได้แก่ $P_1,P_2,\ldots,P_N$ แล้วเชื่อมจุดเหล่านี้ตามลำดับ โดยเชื่อม $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$ ได้ส่วนของเส้นตรง $N-1$ เส้น

จากนั้น ในแต่ละครั้ง 小绪 จะวาดเส้นตรงหนึ่งเส้นบนระนาบ แล้วถาม 小葱 ว่าเส้นตรงนี้ตัดกับส่วนของเส้นตรงกี่เส้น โดยเฉพาะอย่างยิ่ง การตัดกันที่จุดปลายของส่วนของเส้นตรงก็นับว่าตัดกัน และกรณีที่เส้นตรงครอบคลุมส่วนของเส้นตรงทั้งเส้นก็นับว่าตัดกันเช่นกัน

แน่นอนว่าโจทย์เช่นนี้ไม่ยากเกินไปสำหรับ 小葱 เขาเพียงใช้สัญชาตญาณอาศัยดวงของตนก็ให้คำตอบที่ถูกต้องได้

小绪 ต้องการทดสอบว่าดวงของ 小葱 ดีเพียงใด จึงเพิ่มความยากของโจทย์:

นอกจากการถามแล้ว 小绪 จะแทรกจุดใหม่ $P$ ระหว่าง $P_i$ กับ $P_{i+1}$ เป็นครั้งคราว แล้วกำหนดดัชนีของทุกจุดใหม่ตามลำดับ กล่าวคือ ดัชนีของจุดหลัง $P_i$ จะเพิ่มขึ้นตามลำดับ และจุด $P$ จะกลายเป็นจุด $P_{i+1}$ ใหม่ โดยเฉพาะอย่างยิ่ง สามารถแทรกจุด $P$ ก่อนจุดแรกหรือหลังจุดสุดท้ายได้ด้วย

小葱 ซึ่งดวงดีมากยังคงตอบได้อย่างง่ายดาย 小绪 จึงเพิ่มความยากอีกขั้น:

หลังการแทรกหรือการถามแต่ละครั้ง 小绪 จะบันทึกส่วนของเส้นตรงทั้งหมดหลังการดำเนินการ เรียกสิ่งนี้ว่าเวอร์ชันในอดีต เวอร์ชันในอดีต $T$ หมายถึงเวอร์ชันที่ได้หลังการดำเนินการครั้งที่ $T$

การแทรกจุดใหม่เปลี่ยนเป็นการแทรกจุด $P$ โดยอ้างอิงเวอร์ชันในอดีต $T$ เวอร์ชันหนึ่ง เพื่อให้ได้เวอร์ชันในอดีตใหม่ ส่วนหลังการถาม เวอร์ชันในอดีตใหม่จะเหมือนกับเวอร์ชันในอดีต $T$ ที่ถูกถาม

คำถามของ 小绪 เปลี่ยนเป็น: สำหรับเวอร์ชันในอดีต $T$ ที่กำหนด และเส้นตรงหนึ่งเส้น จงหาว่าเส้นตรงนี้ตัดกับส่วนของเส้นตรงกี่เส้น

แม้ 小葱 จะดวงดี แต่ก็จนปัญญาเมื่อพบโจทย์เช่นนี้ เขาจึงมาหาคุณซึ่งกำลังเข้าร่วม CTSC เพื่อขอให้ช่วยแก้ปัญหานี้

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

ไฟล์ข้อมูลนำเข้าคือ shallot.in

บรรทัดแรกมีจำนวนเต็มสองจำนวน $N,M,C$ ระบุจำนวนจุดเริ่มต้น จำนวนการดำเนินการทั้งหมด และข้อมูลถูกเข้ารหัสหรือไม่ หาก $C=1$ แสดงว่าข้อมูลถูกเข้ารหัส ค่า $X_0,Y_0,X,Y$ ในการถามแต่ละครั้ง และค่า $X,Y$ ในการแทรก เป็นข้อมูลที่ถูกเข้ารหัส คุณต้องนำค่าเหล่านี้ไป XOR กับ $\mathit{last\_ans}$ เพื่อให้ได้ข้อมูลที่ถูกต้อง โดย $\mathit{last\_ans}$ คือคำตอบของการถามครั้งล่าสุด และเริ่มต้นด้วย $\mathit{last\_ans}=0$

จากนั้นมี $N$ บรรทัด แต่ละบรรทัดมีจำนวนเต็มสองจำนวน โดยสองจำนวนในบรรทัดที่ $i$ คือพิกัดแนวนอนและแนวตั้งของ $P_i$

จากนั้นมี $M$ บรรทัด แทนการดำเนินการ $M$ ครั้งของ 小绪 ผลหลังการดำเนินการในบรรทัดที่ $i$ (เริ่มนับจาก $1$) คือเวอร์ชันในอดีต $i$

สำหรับแต่ละการดำเนินการ จะมีตัวอักษรหนึ่งตัวก่อน เพื่อระบุประเภทของการดำเนินการครั้งนี้ของ 小绪

หากตัวอักษรเป็น H แสดงว่าเป็นการถาม: ตามด้วยจำนวนเต็มห้าจำนวน $T,X_0,Y_0,X,Y$ หมายความว่าในเวอร์ชันในอดีต $T$ นั้น 小绪 ให้เส้นตรงที่ผ่าน $(X_0,Y_0)$ และมีทิศทาง $(X,Y)$ โดย 小葱 ต้องตอบว่าเส้นตรงนี้ตัดกับส่วนของเส้นตรงกี่เส้น

หากตัวอักษรเป็น Z แสดงว่าเป็นการแทรก ตามด้วยจำนวนสี่จำนวน $T,i,X,Y$ หมายความว่า 小绪 แทรกจุดพิกัด $(X,Y)$ หลัง $P_i$ โดยอ้างอิงเวอร์ชันในอดีต $T$ โดยเฉพาะอย่างยิ่ง ถ้า $i=0$ หมายถึงแทรกจุดนี้ก่อน $P_1$

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

ไฟล์ข้อมูลส่งออก shallot.out ต้องมีหนึ่งบรรทัดสำหรับการถามแต่ละครั้ง แต่ละบรรทัดมีจำนวนเต็มหนึ่งจำนวน แทนคำตอบที่ถูกต้องซึ่ง 小葱 ควรตอบ

ตัวอย่าง

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

2 3 0
0 0
1 1
H 0 1 0 -1 1
H 1 0 1 1 1
H 2 -1 -1 1 1

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

1
0
1

หมายเหตุ

สำหรับการถามครั้งที่สาม เส้นตรงครอบคลุมส่วนของเส้นตรงทั้งเส้น ซึ่ง 小绪 ก็นับว่าตัดกันเช่นกัน

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

2 3 0
0 0
2 2
Z 0 2 0 2
H 0 0 1 1 1
H 1 0 1 1 1

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

0
2

ตัวอย่าง 3

ดู shallot/shallot.in และ shallot/shallot.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ข้อจำกัด

รับประกันว่า $T$ ของการถามแต่ละครั้งไม่เกินจำนวนการดำเนินการปัจจุบัน และข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม

มีข้อมูลพิเศษสี่ประเภทต่อไปนี้ ซึ่งแต่ละคู่ไม่มีส่วนร่วมกัน:

1. สำหรับ $15\%$ ของข้อมูล รับประกันว่า $1\le N,M\le1000$
2. สำหรับ $15\%$ ของข้อมูล รับประกันว่าสำหรับการดำเนินการครั้งที่ $i$ มี $T=i-1$
3. สำหรับ $15\%$ ของข้อมูล รับประกันว่า $C=0$ และไม่มีการดำเนินการแก้ไข
4. สำหรับ $15\%$ ของข้อมูล ในการแทรกรับประกันว่า $Y=0$ (สำหรับข้อมูลที่เข้ารหัส หมายถึงค่า $Y$ หลังถอดรหัส) กล่าวคือ เส้นตรงที่ให้ขนานกับแกน $x$

สำหรับข้อมูลข้างต้น ยังรับประกันว่า $1\le N,M\le5\times10^4$

สำหรับ $100\%$ ของข้อมูล รับประกันว่า $1\le N,M\le10^5$ พิกัดทั้งหมดอยู่ในช่วง $[-10^8,10^8]$ และในข้อมูลแต่ละชุด ผลรวมคำตอบของการถามทั้งหมดไม่เกิน $10^6$ จำนวนการแทรกไม่เกิน $5\times10^4$ โปรดสังเกตว่าส่วนของเส้นตรงเหล่านี้อาจตัดกันเองได้