# Hpargmented Graph

###### tags: `cp`

Semua orang adalah Jv dan semua orang menyukai JeO.

Pada suatu hari, semua orang ingin memberikan hadiah kepada JeO berupa sebuah graf dengan $N$ vertex. Karena semua orang menyukai JeO dan JeO menyukai semua orang, JeO menerima hadiah semua orang dengan senang hati.

Sebulan kemudian, JeO memberikan balik hadiah kepada Jv (sehingga ia memberikan hadiah kepada semua orang) berupa $M$ jenis edge dua arah untuk melengkapi graf tersebut. Edge jenis $i$ menghubungkan semua verteks $u$ dan $v$ dengan edge seberat $w$, di mana $u \equiv a_i \; (\text{mod } b_i)$, $v \equiv c_i \; (\text{mod } d_i)$, dan $w = e_i$. Perhatikan bahwa di antara setiap pasang node pada graf, jika sudah ada $1$ edge yang menghubungkan keduanya, JeO tidak akan menambahkan edge khusus pada kedua node itu.

Joshjms yang iri akan semua orang ingin mengacak-acak graf yang dirangkai JeO dan Jv. Maka, Joshjms ingin melakukan $Q$ operasi secara berurutan. Operasi-operasi yang mungkin dilakukan adalah sebagai berikut.

- `A x`: Joshjms ingin mengetahui banyak verteks yang terhubung dengan verteks $x$ (tidak termasuk verteks $x$ itu sendiri).
- `B x y`: Joshjms ingin membuat sebuah edge antara node $x$ dengan $y$ (jika belum ada).
- `C x y`: Joshjms ingin memotong edge yang menghubungkan $x$ dengan $y$ (jika ada).
- `D x y`: Joshjms ingin mengetahui $\text{d}(x, y)$, di mana $\text{d}(a, b)$ adalah jarak terpendek verteks $a$ dari verteks $b$. Bila verteks $x$ dan $y$ tidak terhubung, keluarkan $-1$.
- `E p q r s`: Joshjms ingin memotong semua edge antara verteks $u$ dan $v$ yang memenuhi $u \equiv p \; (\text{mod } q)$ dan $v \equiv r \; (\text{mod } s)$.
- `F p q r s`: Joshjms ingin membuat edge antara semua verteks $u$ dan $v$ yang memenuhi $u \equiv p \; (\text{mod } q)$ dan $v \equiv r \; (\text{mod } s)$.

Keluarkan hasil dari setiap operasi `A` dan `D`.

## Format Masukan

Baris pertama berisi dua buah bilangan bulat $N$ dan $M$.

$M$ baris berikutnya masing-masing berisi lima buah bilangan bulat $a_i$, $b_i$, $c_i$, $d_i$, dan $e_i$.

Baris berikutnya berisi sebuah bilangan bulat $Q$.

$Q$ baris berikutnya berisi salah satu di antara format
- $\texttt{A} \; x$,
- $S \; x \; y$, atau
- $T \; p \; q \; r \; s$,

di mana $S \in \{ \texttt{B}, \texttt{C}, \texttt{D} \}$ dan $T \in \{ \texttt{E}, \texttt{F} \}$.

Dijamin terdapat setidaknya satu operasi `A` atau `D`.

## Format Keluaran

Untuk setiap operasi `A` dan `D`, keluarkan sebuah bilangan bulat yang merupakan jawaban dari operasi tersebut.

## Batasan

- $1 \leq N \leq 10^{12}$
- $0 \leq M \leq 10^5$
- $1 \leq Q \leq 10^5$
- $a_i < c_i \leq N+1$ dan $b_i < d_i \leq N+1$ untuk $1 \leq i \leq M$
- $0 \leq e_i \leq 10^9$ untuk $1 \leq i \leq M$
- $x_i, y_i \leq N$ untuk $1 \leq i \leq Q$
- $p < q \leq N+1$ dan $r < s \leq N+1$ untuk $1 \leq i \leq Q$

## Subsoal

1. (1 poin) $N \leq 10^3, M \leq 10$
2. (2 poin) $N \leq 100, M \leq 10^3$
3. (2 poin) $N \leq 10^3, M \leq 10^3, Q \leq 10$
4. (3 poin) $N \leq 10^5, M \leq 10,$ semua query bertipe `A`
5. (3 poin) $N \leq 10^5, M \leq 10,$ semua query bertipe `D`
6. (4 poin) $M = 1$, semua query bertipe `A` atau `D`
7. (10 poin) $M \leq 300$, semua query bertipe `A` atau `D`
8. (10 poin) $M \leq 7500$, semua query bertipe `A` atau `D`
9. (10 poin) $M = 0$, tidak ada query `E` atau `F`
10. (10 poin) Tidak ada query `E` atau `F`
11. (15 poin) $M, Q \leq 300$
12. (15 poin) $M, Q \leq 7500$
13. (15 poin) Tidak ada batasan tambahan