$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$-ші жолында алдымен $i$-ші сұранымның түрін білдіретін $op$ ($op \in \{+, ?\}$) таңбасы беріледі.
- Егер $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$ болады.