Bài này bạn cần quản lý thông tin kết nối giữa các hành tinh.

Hành tinh ~A~, ~B~ được kết nối nếu chúng có đường đi trực tiếp hoặc có ~1~ dãy các hành tinh

~P_1~, ~P_2~, ...~P_n~ mà ~P_1 = A~, ~P_n = B~ và có kết nối giữa ~P_k~ và ~P_{k - 1}~, ~k \in \{2, \dots n\}~.

Kết nối là ~2~ chiều và có thể có nhiều kết nối giữa ~2~ thành phố.

Input

Gồm nhiều test, mỗi test vài dòng, mỗi dòng bắt đầu bằng 'D', 'C' hoặc 'Q' (chữ hoa hoặc

thường) sau đó là ~1 \rightarrow 5~ số nguyên với ý nghĩa như sau:

• 'D' ~N \rightarrow~ xác định số hành tinh là ~N~, ~N \le 6000000~, hành tinh đánh số từ ~1~ ...~N~.
• 'C' ~\rightarrow~ tạo kết nối giữa các cặp hành tinh.
• 'Q' ~\rightarrow~ kiểm tra các cặp hành tinh có kết nối.

Lệnh ~C~ và ~Q~ có cùng định dạng như sau (kí hiệu là chữ ~X)~

• ~X~ ~src~ ~dst~ -- Tạo/truy vấn kết nối giữa ~2~ hành tinh ~src~ và ~dst~

• ~X~ ~src~ ~dst~ ~nnn~ -- Tạo/truy vấn kết nối giữa hành tinh ~src~ và ~nnn~ hành tinh liên tiếp từ ~dst~. VD:

  • ~C~ ~1~ ~100$$1~ tạo ~3~ kết nối ~(1~, ~100)~, ~(1~, ~101)~, ~(1~, ~102)~.
  • ~C~ ~1~ ~100~ ~3~ tạo ~3~ kết nối sau ~(1~, ~100)~, ~(1~, ~105)~, ~(1~, ~110)~.
  • ~C~ ~1~ ~100~ ~5~ tạo ~3~ kết nối sau ~(1~, ~100)~, ~(1~, ~105)~, ~(1~, ~110)~.

• ~X~ ~src~ ~dst~ ~nnn~ ~dststep~ ~srcstep~ - Tạo/truy vấn kết nối giữa ~nnn~ cặp thành phố từ ~src~ với bước nhảy là ~srcstep~ tại ~src~ và tới ~dst~ với bước nhảy là ~dststep~. VD:

  • ~C~ ~1~ ~100~ ~3~ ~5~ ~15~ tạo ~3~ kết nối ~(1~, ~100)~, ~(16~, ~105)~, ~(31~, ~110)~.

Output

Với mỗi truy vấn 'Q' in ra ~2~ số: số đầu tiên là số cặp thành phố kết nối, số thứ hai là số cặp thành phố không kết nối trong truy vấn tương ứng.

Sample Input 1

d 5 
C 1 3 
D 20 
q 1 3 
c 1 10 10 
Q 1 2 18 1 1

Sample Output 1

0 1
9 9

Sample Input 2

d 5
d 1
q 1 1
d 10
q 1 6 5 1 1
c 1 2 9
q 1 6 5 1 1

Sample Output 2

1 0
0 5
5 0