Sau bao thời gian chuẩn bị, cuối cùng đã tới ngày Gấu Trắng trình diễn tại buổi Đại Hòa Nhạc. Tuy nhiên, trong lúc duyệt qua bài nhạc của mình, cậu nhận ra bài nhạc còn thiếu một yếu tố vô cùng quan trọng: sự bay bổng. Vậy nên, Gấu Trắng quyết định tăng một tone cho bản nhạc của mình và sẵn sàng biểu diễn!

Chỗ ngồi khán giả có dạng cây, với vị trí sân khấu nằm về phía gốc của cây (sân khấu không phải là gốc). Gốc của cây là đỉnh ~1~. Mỗi đỉnh của cây là một chỗ ngồi. Ban đầu mỗi chỗ ngồi sẽ có giới hạn âm lượng là ~c~: nếu âm lượng tại một chỗ ngồi vượt quá ~c~, giá trị đó sẽ được gán lại thành ~c~.

Gấu Trắng nhận được rất nhiều sự ủng hộ từ khán giả, cậu muốn theo dõi âm thanh vỗ tay từ dưới khán đài. Sẽ có ~q~ sự kiện lần lượt diễn ra như sau:

• clap ~u~ : Một khán giả vỗ tay tại ~u~; lần vỗ tay này không tạo ra âm thanh và không thay đổi âm lượng, nhưng tạo ra sóng âm tại ~u~.

• travel ~d~:

  • Tất cả các sóng âm sẽ lan truyền trong không khí: di chuyển ~d~ chỗ ngồi về phía sân khấu.

  • Khi đi vào một vị trí, sóng âm sẽ tăng âm lượng tại vị trí đó lên ~1~ đơn vị (nhưng không vượt quá giới hạn âm lượng tại vị trí đó). Lưu ý: với mỗi đợt travel, sóng âm không thay đổi âm lượng tại vị trí mà nó bắt đầu di chuyển, chỉ ảnh hưởng đến âm lượng tại các vị trí mà nó đi vào.

  • Mỗi sóng âm sau khi di chuyển đủ ~d~ bước sẽ dừng lại, nhưng không biến mất.

  • Mỗi sóng âm, ngay sau khi đi vào gốc của cây và tăng âm lượng tại gốc, sẽ biến mất, kể cả khi chưa di chuyển đủ số bước theo yêu cầu của đợt travel.

• count ~u~: Tính toán tổng âm lượng của tất cả chỗ ngồi trong cây con gốc ~u~ ở thời điểm hiện tại.

Input

• Dòng đầu tiên chứa ba số nguyên ~n, c, q~ ー số lượng đỉnh trong cây, giới hạn âm lượng ở mỗi đỉnh, và số lượng sự kiện (~1 \leq n, c, q \leq 10^5~).

• Dòng thứ ~i~ trong ~n-1~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ ー có cạnh nối giữa hai đỉnh ~x_i~ và ~y_i~ (~1 \leq x_i, y_i \leq n~, với ~1 \leq i \leq n-1~). Dữ liệu đảm bảo đồ thị là đồ thị cây.

• Mỗi dòng trong ~q~ dòng tiếp theo chứa các sự kiện theo mô tả đề bài, mỗi sự kiện thuộc một trong ba dạng:

  • clap ~u~ (~1 \leq u \leq n~).
  • count ~u~ (~1 \leq u \leq n~).
  • travel ~d~ (~1 \leq d \leq n~).

Output

Với mỗi sự kiện loại count ~u~, in ra tổng âm lượng của tất cả chỗ ngồi trong cây con gốc ~u~ tại thời điểm sự kiện.

Scoring

• Subtask ~1~ (~5\%~): ~1 \leq n, c, q \leq 5000~.

• Subtask ~2~ (~15\%~): ~c = 1~.

• Subtask ~3~ (~40\%~): ~c = 10^5~.

• Subtask ~4~ (~40\%~): Không có giới hạn gì thêm.

Sample Input 1

6 2 10
1 2
2 3
1 4
4 5
4 6
count 1
clap 5
travel 1
count 1
clap 4
clap 3
travel 2
count 1
count 4
count 3

Sample Output 1

0
1
4
1
0

Notes

• Khán đài ban đầu nhìn như sau:

  

• Sau sự kiện thứ hai, khán đài nhìn như sau:

  

• Sau sự kiện thứ ba, khán đài nhìn như sau:

  

• Sau sự kiện thứ sáu, khán đài nhìn như sau:

  

• Sau sự kiện thứ bảy, khán đài nhìn như sau: