小葱 dan 小绪 adalah sepasang sahabat. Sejak 小葱 mendapatkan 1UR2SR dalam sebelas tarikan berturut-turut, 小绪 merasa bahwa keberuntungan 小葱 sangat baik. Maka, 小绪 memberikan sebuah soal untuk menguji keberuntungan 小葱.

Mula-mula, 小绪 menggambar $N$ titik pada bidang, yaitu $P_1,P_2,\ldots,P_N$. Ia menghubungkan titik-titik tersebut secara berurutan, yakni menghubungkan $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, sehingga memperoleh $N-1$ ruas garis.

Setelah itu, setiap kali 小绪 menggambar sebuah garis lurus pada bidang, ia bertanya kepada 小葱 berapa banyak ruas garis yang berpotongan dengan garis tersebut. Perpotongan di ujung ruas garis juga dihitung, dan garis yang sepenuhnya menutupi ruas garis juga dianggap berpotongan.

Tentu saja soal seperti ini tidak menyulitkan 小葱. Dengan mengandalkan keberuntungannya, ia dapat memberikan jawaban yang benar hanya melalui intuisi.

小绪 ingin menguji seberapa baik sebenarnya keberuntungan 小葱, sehingga ia meningkatkan kesulitan soal:

Selain mengajukan pertanyaan, sesekali 小绪 menyisipkan titik baru $P$ di antara $P_i$ dan $P_{i+1}$, kemudian memberi ulang indeks semua titik secara berurutan. Artinya, indeks titik-titik setelah $P_i$ bertambah, dan $P$ menjadi titik $P_{i+1}$ yang baru. Secara khusus, $P$ juga boleh disisipkan sebelum titik pertama atau setelah titik terakhir.

小葱 yang sangat beruntung tetap dapat menjawab dengan mudah. Maka 小绪 kembali meningkatkan kesulitannya:

Setelah setiap penyisipan atau pertanyaan, 小绪 mencatat semua ruas garis setelah operasi tersebut sebagai sebuah versi historis. Versi historis $T$ menyatakan versi yang diperoleh setelah operasi ke-$T$.

Operasi penyisipan diubah menjadi menyisipkan titik $P$ berdasarkan suatu versi historis $T$ untuk memperoleh versi historis baru. Setelah operasi pertanyaan, versi historis baru sama dengan versi historis $T$ yang ditanyakan.

Pertanyaan 小绪 kepada 小葱 diubah menjadi: untuk suatu versi historis $T$, diberikan sebuah garis lurus, tentukan berapa banyak ruas garis yang berpotongan dengannya.

Meskipun sangat beruntung, 小葱 tidak tahu harus berbuat apa menghadapi soal seperti ini. Ia pun menemui Anda yang datang untuk mengikuti CTSC dan meminta bantuan untuk menyelesaikannya.

Masukan

Berkas masukan adalah shallot.in.

Baris pertama berisi dua bilangan bulat $N,M,C$, yang menyatakan jumlah titik awal, jumlah seluruh operasi, serta apakah data dienkripsi. Jika $C=1$, data telah dienkripsi: $X_0,Y_0,X,Y$ dalam setiap operasi pertanyaan dan $X,Y$ dalam operasi penyisipan adalah data terenkripsi. Anda harus melakukan XOR terhadap nilai-nilai tersebut dengan $last\_ans$ untuk memperoleh data yang benar. Di sini $last\_ans$ adalah jawaban pertanyaan sebelumnya dan awalnya $last\_ans=0$.

$N$ baris berikutnya masing-masing berisi dua bilangan bulat. Dua bilangan pada baris ke-$i$ menyatakan koordinat horizontal dan vertikal $P_i$.

$M$ baris berikutnya menyatakan $M$ operasi 小绪. Hasil setelah operasi pada baris ke-$i$ (penomoran dimulai dari $1$) adalah versi historis $i$.

Setiap operasi diawali sebuah huruf yang menyatakan jenis operasi 小绪 tersebut.

Jika hurufnya H, operasi ini merupakan pertanyaan. Berikutnya terdapat lima bilangan bulat $T,X_0,Y_0,X,Y$. Pada versi historis $T$, 小绪 memberikan garis yang melalui $(X_0,Y_0)$ dan memiliki arah $(X,Y)$; 小葱 harus menjawab berapa banyak ruas garis yang berpotongan dengannya.

Jika hurufnya Z, operasi ini merupakan penyisipan. Berikutnya terdapat empat bilangan $T,i,X,Y$, yang menyatakan bahwa berdasarkan versi historis $T$, 小绪 menyisipkan titik berkoordinat $(X,Y)$ setelah $P_i$. Khususnya, jika $i=0$, titik tersebut disisipkan sebelum $P_1$.

Keluaran

Untuk setiap operasi pertanyaan, keluarkan satu baris pada berkas shallot.out yang berisi satu bilangan bulat: jawaban benar yang seharusnya diberikan 小葱.

Contoh

Masukan 1

2 3 0
0 0
1 1
H 0 1 0 -1 1
H 1 0 1 1 1
H 2 -1 -1 1 1

Keluaran 1

1
0
1

Penjelasan

Pada pertanyaan ketiga, garis sepenuhnya menutupi ruas garis. 小绪 menganggapnya juga sebagai perpotongan.

Masukan 2

2 3 0
0 0
2 2
Z 0 2 0 2
H 0 0 1 1 1
H 1 0 1 1 1

Keluaran 2

0
2

Masukan dan keluaran 3

Lihat shallot/shallot.in dan shallot/shallot.ans pada direktori peserta.

Batasan

Dijamin bahwa $T$ pada setiap operasi pertanyaan tidak lebih besar daripada jumlah operasi saat ini. Semua data masukan adalah bilangan bulat.

Terdapat empat jenis data khusus berikut yang saling tidak beririsan:

1. Untuk 15% data, dijamin $1\le N,M\le1000$;
2. Untuk 15% data, dijamin bahwa pada operasi ke-$i$, $T=i-1$;
3. Untuk 15% data, dijamin $C=0$ dan tidak ada operasi perubahan;
4. Untuk 15% data, pada operasi penyisipan dijamin $Y=0$ (untuk data terenkripsi, yang dimaksud adalah $Y$ setelah dekripsi), yaitu garis yang diberikan sejajar dengan sumbu $x$.

Data di atas juga menjamin $1\le N,M\le5\times10^4$.

Untuk 100% data, dijamin $1\le N,M\le10^5$, semua koordinat berada dalam $[-10^8,10^8]$, jumlah jawaban seluruh pertanyaan pada setiap kumpulan data tidak melebihi $10^6$, dan jumlah operasi penyisipan tidak melebihi $5\times10^4$. Perhatikan bahwa ruas-ruas garis ini dapat saling berpotongan.