Diberikan sebuah graf tak berarah dengan $n$ simpul, yang pada awalnya tidak memiliki sisi. Lakukan $q$ operasi dari dua jenis berikut:
- $+\ u\ v\ w$: Tambahkan sebuah sisi yang menghubungkan simpul $u$ dan $v$ dengan bobot $w$.
- $?\ u\ v$: Definisikan bobot suatu lintasan sebagai hasil operasi bitwise-and dari bobot semua sisi pada lintasan tersebut. Hitung bobot terbesar yang mungkin dari suatu lintasan yang dimulai dari simpul $u$ dan berakhir di simpul $v$. Jika tidak ada lintasan yang menghubungkan simpul $u$ dan $v$, jawabannya adalah $-1$.
Masukan
Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:
Baris pertama berisi dua bilangan bulat $n$ dan $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) yang menyatakan banyaknya simpul dan banyaknya operasi.
Untuk $q$ baris berikutnya, baris ke-$i$ diawali dengan sebuah karakter $op$ ($op \in \{+, ?\}$) yang menyatakan jenis kueri ke-$i$.
- Jika $op = +$, maka diikuti oleh tiga bilangan bulat $u$, $v$, dan $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), yang menyatakan operasi jenis pertama.
- Jika $op = ?$, maka diikuti oleh dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u \ne v$), yang menyatakan operasi jenis kedua.
Dijamin bahwa terdapat setidaknya satu operasi jenis kedua pada setiap kasus uji. Selain itu, jumlah $n$ di semua kasus uji tidak melebihi $10^3$, dan jumlah $q$ di semua kasus uji tidak melebihi $10^6$.
Keluaran
Untuk mengurangi ukuran keluaran, bagi setiap kasus uji cukup keluarkan satu baris yang berisi satu bilangan bulat, yang menyatakan jumlah dari jawaban untuk semua operasi jenis kedua.
Contoh
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
Catatan
Untuk kasus uji contoh pertama, jawaban untuk operasi-operasi jenis kedua berturut-turut adalah $2$, $3$, $4$, $2$, dan $6$.
Untuk kasus uji contoh kedua, jawaban untuk operasi-operasi jenis kedua berturut-turut adalah $64$ dan $-1$.