Cho một dãy các ô màu gồm ~n~ ô, mỗi ô trên dãy được gán một giá trị ~a_i~ và có màu ~c_i~. Có ~q~ truy vấn:

• 1 col x (~1 \le col\le 10^5,1\le x \le 10^8~): Những ô có màu khác col sẽ được tăng giá trị lên một lượng ~x~.

• 2 col y (~1 \le col\le10^5,1\le y \le 10^{15}~): Xét dãy gồm các ô có màu col (thứ tự các ô trong dãy này là thứ tự các ô trong dãy ban đầu), tìm độ dài ~l~ lớn nhất sao cho tổng của ~l~ phần tử đầu tiên trong dãy này có giá trị không lớn hơn ~y~.

Input

Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~) — số lượng phần tử trong dãy.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~a_i~ và ~c_i~ (~1 \le a_i\le 10^8,1\le c_i \le 10^5~) — lần lượt là giá trị và màu của ô thứ ~i~.

Dòng thứ ~n+2~ gồm một số nguyên dương ~q~ (~1 \le q \le 2 \cdot 10^5~) — số lượng truy vấn cần thực hiện.

Mỗi dòng trong ~q~ dòng tiếp theo chứa 1 trong 2 loại truy vấn trên.

Output

Với mỗi truy vấn thuộc loại 2, in ra một số nguyên ~l~ sao cho tổng của ~l~ phần tử đầu tiên trong dãy oo có màu ~i~ có giá trị không lớn hơn ~y~.

Scoring

Sample Input 1

5
1 2
3 2
2 1
5 1
6 1
4
2 2 6
1 1 4
2 1 6
2 2 6

Sample Output 1

2
1
1

Notes

Ban đầu, dãy ô của ta sẽ có các giá trị sau:

Ở truy vấn 1, chỉ có 2 ô đầu tiên trong dãy là có màu ~2~, tổng giá trị của 2 ô này ~1+3=4 \le 6~ nên độ dài ~l~ lớn nhất của truy vấn là ~2~.

Sau truy vấn 2, dãy ô hiện tại là:

Ở truy vấn 3, xét dãy các ô có màu ~1~, ta không thể lấy cùng lúc 2 ô ~3~ và ~4~ hoặc nhiều hơn vì ~2+5 = 7 > 6~, vì thế đáp án của truy vấn này là ~1~.

Ở truy vấn cuối cùng, ta cũng không thể lấy hết 2 ô có màu ~2~ vì ~5+7 = 12 > 6~, vì thế đáp án là ~1~.