小葱 và 小绪 là đôi bạn thân. Kể từ khi 小葱 nhận được 1UR2SR trong một lượt quay 11 lần liên tiếp, 小绪 cho rằng 小葱 rất may mắn, nên đưa cho cậu một bài toán để kiểm tra vận may.

Đầu tiên, 小绪 vẽ $N$ điểm trên mặt phẳng, lần lượt là $P_1,P_2,\ldots,P_N$. Cậu nối các điểm theo thứ tự, tức là nối $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, thu được $N-1$ đoạn thẳng.

Sau đó, mỗi lần 小绪 vẽ một đường thẳng trên mặt phẳng và hỏi 小葱 đường thẳng này giao với bao nhiêu đoạn thẳng. Đặc biệt, giao tại đầu mút của đoạn thẳng cũng được tính là giao; đường thẳng chứa toàn bộ đoạn thẳng cũng được tính là giao.

Bài toán như vậy đương nhiên không làm khó được 小葱: chỉ cần dựa vào vận may và trực giác, cậu đã có thể đưa ra đáp án đúng.

小绪 muốn kiểm tra xem vận may của 小葱 tốt đến mức nào, nên tăng độ khó của bài toán:

Ngoài việc đặt câu hỏi, thỉnh thoảng 小绪 chèn một điểm mới $P$ vào giữa $P_i$ và $P_{i+1}$, rồi đánh lại chỉ số tất cả các điểm theo thứ tự. Nghĩa là chỉ số của các điểm sau $P_i$ tăng lên, còn $P$ trở thành điểm $P_{i+1}$ mới. Đặc biệt, cũng có thể chèn $P$ trước điểm đầu tiên hoặc sau điểm cuối cùng.

小葱 vô cùng may mắn vẫn dễ dàng trả lời, nên 小绪 lại tiếp tục tăng độ khó:

Sau mỗi thao tác chèn hoặc truy vấn, 小绪 ghi lại tất cả các đoạn thẳng sau thao tác đó, gọi là một phiên bản lịch sử. Phiên bản lịch sử $T$ là phiên bản thu được sau thao tác thứ $T$.

Thao tác chèn điểm mới được đổi thành: dựa trên một phiên bản lịch sử $T$, chèn một điểm $P$ để thu được một phiên bản lịch sử mới. Sau thao tác truy vấn, phiên bản lịch sử mới chính là phiên bản lịch sử $T$ được truy vấn.

Câu hỏi của 小绪 dành cho 小葱 cũng đổi thành: với một phiên bản lịch sử $T$ và một đường thẳng, hỏi đường thẳng đó giao với bao nhiêu đoạn thẳng.

Tuy rất may mắn, 小葱 cũng bó tay trước bài toán này. Cậu đành tìm đến bạn, người đang tham gia CTSC, nhờ bạn giải quyết.

Dữ liệu vào

Tệp đầu vào là shallot.in.

Dòng đầu chứa hai số nguyên $N,M,C$, cho biết số điểm ban đầu, tổng số thao tác và dữ liệu có được mã hóa hay không. Nếu $C=1$, dữ liệu đã được mã hóa: $X_0,Y_0,X,Y$ trong mỗi thao tác truy vấn và $X,Y$ trong thao tác chèn đều đã được mã hóa. Bạn cần XOR chúng với $last\_ans$ để thu được dữ liệu đúng, trong đó $last\_ans$ là đáp án của truy vấn trước đó; ban đầu $last\_ans=0$.

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên; hai số ở dòng thứ $i$ là hoành độ và tung độ của $P_i$.

$M$ dòng tiếp theo mô tả $M$ thao tác của 小绪. Kết quả sau thao tác ở dòng thứ $i$ (đánh số từ $1$) là phiên bản lịch sử $i$.

Mỗi thao tác bắt đầu bằng một chữ cái biểu thị loại thao tác của 小绪.

Nếu chữ cái là H, đây là một truy vấn. Tiếp theo là năm số nguyên $T,X_0,Y_0,X,Y$: trong phiên bản lịch sử $T$, 小绪 cho một đường thẳng đi qua $(X_0,Y_0)$ với vectơ chỉ phương $(X,Y)$, và 小葱 phải trả lời đường thẳng đó giao với bao nhiêu đoạn thẳng.

Nếu chữ cái là Z, đây là một thao tác chèn. Tiếp theo là bốn số $T,i,X,Y$: dựa trên phiên bản lịch sử $T$, 小绪 chèn một điểm có tọa độ $(X,Y)$ sau $P_i$. Đặc biệt, nếu $i=0$, điểm đó được chèn trước $P_1$.

Dữ liệu ra

Trong tệp đầu ra shallot.out, với mỗi thao tác truy vấn, ghi một dòng chứa một số nguyên là đáp án đúng mà 小葱 cần trả lời.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
0
1

Ghi chú

Trong truy vấn thứ ba, đường thẳng chứa toàn bộ đoạn thẳng; 小绪 cũng tính trường hợp này là giao.

Dữ liệu vào 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

Dữ liệu ra 2

0
2

Ví dụ 3

Xem shallot/shallot.in và shallot/shallot.ans trong thư mục của thí sinh.

Giới hạn

Bảo đảm rằng $T$ trong mỗi thao tác truy vấn không lớn hơn số thao tác hiện tại; mọi dữ liệu đầu vào đều là số nguyên.

Có bốn loại dữ liệu đặc biệt sau đây, đôi một không giao nhau:

1. Với $15\%$ dữ liệu, bảo đảm $1\le N,M\le 1000$;

2. Với $15\%$ dữ liệu, bảo đảm trong thao tác thứ $i$, $T=i-1$;

3. Với $15\%$ dữ liệu, bảo đảm $C=0$ và không có thao tác sửa đổi;

4. Với $15\%$ dữ liệu, trong thao tác chèn, bảo đảm $Y=0$ (với dữ liệu mã hóa, đây là $Y$ sau khi giải mã), tức là đường thẳng được cho song song với trục $x$.

Các dữ liệu trên còn thỏa mãn $1\le N,M\le 5\times 10^4$.

Với $100\%$ dữ liệu, bảo đảm $1\le N,M\le 10^5$, tất cả tọa độ nằm trong $[-10^8,10^8]$, tổng đáp án của mọi truy vấn trong mỗi bộ dữ liệu không vượt quá $10^6$, và số thao tác chèn không vượt quá $5\times 10^4$. Lưu ý rằng các đoạn thẳng có thể giao nhau.