נתון גרף לא מכוון עם $n$ צמתים, ובתחילה אין בגרף קשתות כלל. עליך לתחזק $q$ פעולות משני הסוגים הבאים:
- $+\ u\ v\ w$: הוסף קשת המחברת בין הצמתים $u$ ו-$v$, שמשקלה $w$.
- $?\ u\ v$: נגדיר את משקלו של מסלול להיות ה-AND הסיביותי (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$.