Trò con bò

Farmer John và em đang chăn bò ở trên trang trại của mình. Vì thấy chán, Farmer John đã tạo ra một trò chơi cho người em.

Hiện tại, trên trang trại có \(N\) cái chuồng đang trống và độc lập nhau. Vì là quản trò, Farmer John sẽ ra \(K\) lượt hiệu lệnh và có ba loại hiệu lệnh sau:

• join X Y: Kết nối chuồng thứ \(X\) và chuồng thứ \(Y\) lại với nhau.
• add X V: Thêm \(V\) \((V \leq 100)\) con bò vào chuồng thứ \(X\) và những chuồng được kết nối với chuồng \(X\). Hai chuồng \(X\) và \(Y\) được xem là kết nối với nhau nếu có đường đi giữa chúng qua một số chuồng trung gian đã kết nối trước đó.
• get X: Farmer John hỏi người em rằng chuồng thứ \(X\) có bao nhiêu con bò.

Vì em của Farmer John còn non trẻ nên đã nhờ bạn làm bài này. Bạn hãy giúp đỡ nhé.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \leq N \leq 10^5, 1 \leq K \leq 5 \times 10^5)\) --- số chuồng và số lệnh.

• \(K\) dòng tiếp theo chứa các lệnh của Farmer John, mỗi dòng thuộc một trong ba loại:

• join X Y: Kết nối chuồng \(X\) và chuồng \(Y\).

• add X V: Thêm \(V\) con bò vào chuồng \(X\) và những chuồng kết nối với nó.
• get X: Trả về số con bò hiện có trong chuồng \(X\).

Output

• Với mỗi truy vấn dạng get X, in ra số lượng bò trong chuồng \(X\) trên một dòng riêng biệt.

Example

4 10
join 1 2
add 1 100
join 2 3
add 1 50
join 3 4
add 1 25
get 1
get 2
get 3
get 4

175
175
75
25

Scoring

• Có \(30\%\) số test có \(n, k \leq 5000\).
• Có \(30\%\) số test có mỗi truy vấn join có \(y = x + 1\).
• \(40\%\) số test còn lại không có ràng buộc gì thêm.