Sau kì thi VOI, ~32~ người xuất sắc nhất đã được chọn để tham dự kì thi chọn đội tuyển quốc tế, và trong số ấy có cậu bé sangph2612. Việc đạt giải trong kì thi VOI đã là cực kì vẻ vang đối với một người tham gia CP, tuy nhiên việc "tạch" trong kì thi TST lại còn vẻ vang hơn! Sau khi thi xong ngày thi thứ hai, bước ra khỏi phòng thi với tâm trạng buồn bã, mắt ngấm lệ, miệng lẩm bẩm một bài hát bất kỳ của Phan Mạnh Quỳnh, thì cậu bé chợt nhận ra rằng điện thoại của mình đã không còn ở trong cặp. Lục lại kí ức, sangph2612 nhớ rằng anh ấy đã đưa điện thoại cho 1 người trong 32 người cùng thi chung với mình để nhờ cậu ta giữ giùm. Lúc này sangph2612 gọi ngay cho thám tử Gấu Trắng bằng chiếc điện thoại cục gạch năm 1900 của mình, mọi chuyện sau đó xảy ra như sau:

Việc tìm ra điện thoại của sangph không dễ dàng mấy, do đó Gấu Trắng đã quy động thêm $n - 1$ người nữa để giúp mình. Trong đó người thứ $1$ là Gấu Trắng, $n - 1$ người còn lại được đánh số từ $2$ đến $n$. Người thứ $i$ trong $n - 1$ người này gửi thông tin rằng anh ấy đã nghi ngờ người thứ $x$ trong 32 người thi đang giữ điện thoại sangph2612 cho người $p_i$.

Với sự trợ giúp từ các trợ thủ, Gấu Trắng cam kết rằng trong $q$ phút chắc chắn sẽ tìm được điện thoại cho sangph2612! Với phút thứ $i$ trong $q$ phút ấy, Gấu Trắng sẽ thực hiện một trong hai hành động sau:

• CHANGE $u$ $t$ $x$: Người $u$ nhận ra thông tin đã sai nên lại một thông tin mới. Lúc này, trong tập hợp thông tin sẵn có, Gấu Trắng sẽ xóa thông tin gửi từ $u$ đến ~p_u~ hiện tại đi, người ~p_u~ sẽ thay thành người $t$, và gửi thông tin nghi ngờ người $x$ cho người $p_u$ mới.
• ASK $u$: Hỏi xem thông tin truyền từ người $u$ khi đi đến Gấu Trắng thì có bao nhiêu người phân biệt bị nghi ngờ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n, q$ $(1 \leq n, q \leq 10^5)$.
• Dòng thứ $i$ trong $n - 1$ dòng sau chứa hai số nguyên ~p_i~ và ~x_i~ ~(1 \leq p_i < i \leq n, 1 \leq x_i \leq 32)~.

• Dòng thứ $i$ trong $q$ dòng sau, mô tả một trong hai hành động:

  • CHANGE $u$ $t$ $x$ $(1 \leq t < u \leq n, 1 \leq x \leq 32)$.
  • ASK $u$ $(1 \leq u \leq n)$.

Dữ liệu ra

• Trả lời đáp án cho mỗi hành động ASK của Gấu Trắng để giúp anh ấy tìm người giữ chiếc điện thoại Redmi của sangph.

Ràng buộc

• Subtask ~1~ (~20\%~ số điểm): $1 \leq n, q \leq 7000$.
• Subtask ~2~ (~20\%~ số điểm): Không có hành động CHANGE.
• Subtask ~3~ (~60\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

7 7
1 2
1 2
2 1
4 3
3 2
4 1
ASK 5
ASK 6
CHANGE 5 2 2
ASK 5
CHANGE 6 4 2
ASK 6 
ASK 7 

Output

3
1
1
2
2

Note

Mạng lưới thông tin ban đầu

• Với hành động thứ nhất: ASK $5$, có $3$ người phân biệt bị nghi ngờ là ${1, 2, 3}$.
• Với hành động thứ hai: ASK $6$, có $1$ người phân biệt bị nghi ngờ là ${2}$.

Mạng lưới thông tin sau hành động CHANGE $5$ $2$ $2$

• Với hành động thứ tư: ASK $5$, có $1$ người phân biệt bị nghi ngờ là ${2}$.

Mạng lưới thông tin sau hành động CHANGE $6$ $4$ $2$

• Với hành động thứ sáu: ASK $6$, có $2$ người phân biệt bị nghi ngờ là ${1, 2}$.

• Với hành động thứ bảy: ASK $7$, có $2$ người phân biệt bị nghi ngờ là ${1, 2}$.