กำหนดกราฟไม่มีทิศทางที่มี $n$ จุดยอด โดยเริ่มต้นกราฟยังไม่มีเส้นเชื่อมใดๆ ให้จัดการการดำเนินการ $q$ ครั้ง ซึ่งมีสองประเภทดังนี้:
- $+\ u\ v\ w$: เพิ่มเส้นเชื่อมที่เชื่อมต่อระหว่างจุดยอด $u$ และ $v$ โดยมีน้ำหนักเท่ากับ $w$
- $?\ u\ v$: นิยามน้ำหนักของเส้นทางให้เป็นผลลัพธ์ของตัวดำเนินการแอนด์ระดับบิต (bitwise-and) ของน้ำหนักของเส้นเชื่อมทั้งหมดในเส้นทางนั้น จงคำนวณน้ำหนักที่มากที่สุดที่เป็นไปได้ของเส้นทางที่เริ่มต้นจากจุดยอด $u$ และสิ้นสุดที่จุดยอด $v$ หากไม่มีเส้นทางที่เชื่อมต่อระหว่างจุดยอด $u$ และ $v$ คำตอบจะเป็น $-1$
ข้อมูลนำเข้า
มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 100$) แทนจำนวนชุดข้อมูลทดสอบ สำหรับแต่ละชุดข้อมูลทดสอบ:
บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน $n$ และ $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) แทนจำนวนจุดยอดและจำนวนการดำเนินการตามลำดับ
สำหรับอีก $q$ บรรทัดถัดไป บรรทัดที่ $i$ เริ่มต้นด้วยอักขระ $op$ ($op \in \{+, ?\}$) แทนประเภทของคำถามที่ $i$
- หาก $op = +$ จะตามด้วยจำนวนเต็มสามจำนวน $u$, $v$ และ $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$) แทนการดำเนินการประเภทแรก
- หาก $op = ?$ จะตามด้วยจำนวนเต็มสองจำนวน $u$ และ $v$ ($1 \le u, v \le n$, $u \ne v$) แทนการดำเนินการประเภทที่สอง
รับประกันว่ามีการดำเนินการประเภทที่สองอย่างน้อยหนึ่งครั้งในแต่ละชุดข้อมูลทดสอบ นอกจากนี้ ผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $10^3$ และผลรวมของ $q$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $10^6$
ข้อมูลส่งออก
เพื่อลดขนาดของข้อมูลส่งออก สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลเพียงบรรทัดเดียวที่มีจำนวนเต็มหนึ่งจำนวน แทนผลรวมของคำตอบของการดำเนินการประเภทที่สองทั้งหมด
ตัวอย่าง
2
4 11
+ 1 3 6
+ 3 4 2
? 1 4
+ 1 4 3
? 4 1
+ 4 3 4
? 1 4
+ 3 2 3
? 1 2
+ 1 1 4
? 1 3
4 4
+ 1 2 64
+ 3 4 32
? 1 2
? 3 1
17
63
หมายเหตุ
สำหรับชุดข้อมูลทดสอบตัวอย่างแรก คำตอบของการดำเนินการประเภทที่สองคือ $2$, $3$, $4$, $2$ และ $6$
สำหรับชุดข้อมูลทดสอบตัวอย่างที่สอง คำตอบของการดำเนินการประเภทที่สองคือ $64$ และ $-1$