Ở một quốc gia nọ có một trung tâm cấp nước. Vì việc cung cấp thẳng từ trung tâm cấp nước đến các hộ gia đình rất khó khăn, nên quốc gia này quyết định xây dựng thêm nhiều trung tâm cấp nước khác. Họ quyết định sẽ xây dựng hệ thống cấp nước theo mô hình là một cây có gốc ở trung tâm hiện tại, nước chảy đi theo hướng từ gốc đến lá, các lá sẽ làm nhiệm vụ cung cấp nước cho người dân.

Do bị bóc lột bởi một số thế lực, quốc gia này không có nước sạch trong lòng đất, chỉ có thể dựa vào nước mưa. Mưa có thể xảy ra ở nhiều nơi, khi trời mưa, một số trung tâm cấp nước sẽ ở trong khu vực mưa và sẽ nhận được một lượng mưa nhất định (có thể khác nhau).

Để kiểm soát lượng nước ở các trung tâm cấp nước, người ta muốn bạn giải quyết bài toán sau:

• Ban đầu có duy nhất một trung tâm, nút gốc 1, không có nước.

• Ở mỗi thời điểm, có thể có trung tâm mới đi vào hoạt động. Truy vấn này sẽ được cung cấp dưới dạng:

  + ~u~ ~v~ ~(1 \le u < v)~: Trung tâm ~v~ đi vào hoạt động, với đỉnh cha là trung tâm ~u~. Dữ liệu đảm bảo rằng ~v~ là số nguyên dương nhỏ nhất chưa được dùng để đánh số cho bất kì trung tâm nào khác. Khi trung tâm ~v~ đi vào hoạt động, trung tâm ~v~ không có nước nhưng toàn bộ lượng nước đang có ở trung tâm ~u~ sẽ chảy sang trung tâm ~v~.

• Ở mỗi thời điểm, mưa có thể diễn ra. Truy vấn này có dạng:

  # ~u~ ~k~ ~(1 \le u, 0 < k \le 10^9)~: Mưa xảy ra và trung tâm ~u~ nhận được lượng nước ~k~. Dữ liệu đảm bảo ~u~ là một nút đã được thêm vào cây. Khi một trung tâm ~u~ nhận được nước, nếu trung tâm này không phải là nút lá thì nước sẽ chảy đều đến các trung tâm con.

  • Ví dụ, nếu u có đúng ~2~ con là ~x~ và ~y~ mà mưa đổ ra ở cây con gốc ~u~ thì ~x~ và ~y~ sẽ cùng nhận được lượng nước là ~k/2~. Sau đó nếu ~x~ và ~y~ mà vẫn không phải nút lá thì nước sẽ tiếp tục chảy đến các nút con của chúng.
  • Xem như thời gian để nước chảy là không đáng kể, mỗi khi mưa rơi thì các nút lá sẽ nhận được nước chảy về ngay lập tức.

• Ở mỗi thời điểm, người ta cần biết lượng nước đang có tại một trung tâm nhất định. Truy vấn này có dạng:

  ? ~u~ ~(1 \le u)~: In ra lượng nước đang có ở trung tâm u.

  • Dễ chứng minh được rằng kết quả có thể được biểu diễn dưới dạng ~\frac{P}{Q}~ với ~P~ và ~Q~ là hai số nguyên tố cùng nhau, bạn chỉ cần in ra giá trị ~P \times Q^{-1}~ mod ~(10^9+7)~.

Input format

Chú ý rằng input của bài này đã bị mã hóa.

Cụ thể, tất cả các số ~u, v, k~, trong ~+~ ~u~ ~v~, # ~u~ ~k~, ~?~ ~u~ được cho trong input thực tế là ~u \oplus ans~, ~v \oplus ans~, và ~k \oplus ans~ với ~ans~ là kết quả (giá trị được in ra) của truy vấn ~?~ cuối cùng, ~ans~ ban đầu được gán là 0. (~\oplus~ là bitwise xor).

Input

Dòng đầu tiên là một số nguyên ~n\ (1 \le n \le 3 \times 10^5)~, số lượng truy vấn.

~n~ dòng tiếp theo, mỗi dòng là một truy vấn có dạng đã nêu ở trên.

Output

Với mỗi truy vấn ? in ra kết quả theo dạng đã nêu.

Subtask

• ~30\%~ số điểm có ~n \le 10000~
• ~70\%~ còn lại không có điều kiện gì thêm.

Sample Input

16
+ 1 2
+ 1 3
# 1 2
? 3
# 0 2
? 3
+ 500000004 500000002
+ 500000004 500000003
? 500000002
? 500000003
# 1 4
? 1
? 2
? 3
? 500000012
? 500000002

Sample Output

1
500000006
500000006
0
0
0
500000008
500000007
1

Note

Input không mã hóa:

16
+ 1 2
+ 1 3
# 1 2
? 3
# 1 3
? 2
+ 2 4
+ 2 5
? 4
? 5
# 1 4
? 1
? 2
? 3
? 4
? 5

Lượng nước có trong mỗi trung tâm (ban đầu và sau mỗi truy vấn):

[0]
[0, 0]
[0, 0, 0]
[0, 1, 1]
[0, 1, 1]
[0, 2.5, 2.5]
[0, 2.5, 2.5]
[0, 0, 2.5, 2.5]
[0, 0, 2.5, 2.5, 0]
[0, 0, 2.5, 2.5, 0]
[0, 0, 2.5, 2.5, 0]
[0, 0, 4.5, 3.5, 1]
[0, 0, 4.5, 3.5, 1]
[0, 0, 4.5, 3.5, 1]
[0, 0, 4.5, 3.5, 1]