Giống như bất kỳ thủ đô nào, thành phố Skibidi có một hệ thống tàu điện rất phát triển. Hệ thống gồm một số ga được nối với nhau bởi các đường hầm, và giữa hai ga bất kỳ luôn có đúng một đường đi không lặp lại đường hầm nào. Nói cách khác, hệ thống là một cây.

Mỗi ga có một trọng số ~x \in \{-1, 1\}~. Khi Per đi qua một ga có trọng số ~-1~, cậu ấy phải trả ~1~ jack; khi đi qua ga có trọng số ~1~, cậu ấy được thưởng ~1~ jack.

Ban đầu hệ thống chỉ có một ga duy nhất mang số ~1~ với trọng số ~x = 1~. Mỗi ngày xảy ra một trong hai sự kiện:

• Xây ga mới: một ga mới với trọng số ~x~ được nối vào ga ~v~. Ga mới được đánh số lớn hơn số của mọi ga hiện có.
• Truy vấn: cho hai ga ~u~, ~v~ và một số nguyên ~k~. Xét đường đi từ ~u~ tới ~v~, hãy cho biết có tồn tại một đoạn liên tiếp các ga trên đường đi đó mà tổng trọng số đúng bằng ~k~ hay không. Đoạn liên tiếp có thể rỗng, khi đó tổng bằng ~0~.

Nhiệm vụ của bạn là trả lời mọi truy vấn.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~t~ — số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu chứa một số nguyên ~n~ — số lượng sự kiện.
  • ~n~ dòng tiếp theo, mỗi dòng là một trong hai dạng:
    • + v x — xây một ga mới với trọng số ~x~ nối vào ga ~v~ (ga ~v~ chắc chắn đã tồn tại).
    • ? u v k — một truy vấn trên đường đi giữa hai ga ~u~ và ~v~ (cả hai ga chắc chắn đã tồn tại).

Kết quả

Với mỗi truy vấn, in ra trên một dòng YES nếu tồn tại đoạn liên tiếp có tổng đúng bằng ~k~, ngược lại in ra NO.

Ví dụ

Đầu vào:

1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0

Đầu ra:

NO
YES
NO
YES
YES
YES

Giải thích: Sau sự kiện đầu tiên, ga ~2~ (trọng số ~-1~) được nối vào ga ~1~.

• Truy vấn ~1~: đường đi chỉ gồm ga ~1~ với trọng số ~1~. Các tổng tạo được là ~0~ và ~1~, không có ~2~.
• Truy vấn ~2~: đường đi ~1 \to 2~ có trọng số ~[1, -1]~. Chọn đoạn chỉ gồm ga ~1~ được tổng ~1~.
• Truy vấn ~3~: đường đi ~1 \to 3~ có trọng số ~[1, 1]~, mọi tổng đều không âm nên không thể bằng ~-1~.
• Truy vấn ~6~: chọn đoạn rỗng, tổng bằng ~0~.

Đầu vào:

1
7
+ 1 -1
+ 2 -1
+ 2 1
+ 3 -1
? 5 2 2
? 3 1 -1
? 5 4 -3

Đầu ra:

NO
YES
YES

Giải thích: Truy vấn cuối xét đường đi ~5 \to 4~ với trọng số ~[-1, -1, -1, 1]~; ba ga đầu cho tổng ~-3~.

Giới hạn

• ~1 \le t \le 10^4~
• ~1 \le n \le 2 \cdot 10^5~
• ~x \in \{-1, 1\}~
• ~-n \le k \le n~
• Tổng các giá trị ~n~ trên tất cả các bộ test không vượt quá ~2 \cdot 10^5~

Điểm mấu chốt: vì mọi trọng số đều là ~\pm 1~, tập các tổng tạo được luôn là một đoạn số nguyên liên tiếp chứa ~0~. Thật vậy, nếu một đoạn có tổng ~S > 0~ thì bỏ đi một ga ở đầu đoạn làm tổng thay đổi đúng ~1~ đơn vị, nên mọi giá trị giữa ~0~ và ~S~ đều đạt được. Tương tự với ~S < 0~.

Do đó đáp án là YES khi và chỉ khi

~\text{minSub}(u, v) \le k \le \text{maxSub}(u, v)~

với ~\text{maxSub}~, ~\text{minSub}~ là tổng đoạn con liên tiếp lớn nhất và nhỏ nhất trên đường đi (cho phép đoạn rỗng, nên ~\text{maxSub} \ge 0 \ge \text{minSub}~).

Việc còn lại là tính hai giá trị đó trên một đường đi bất kỳ của cây đang lớn dần.