يُعطى بيان غير موجّه يحتوي على $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$.