Vào năm 2112, tất cả công việc được chuyên môn hóa, năng suất lao động tăng cực kỳ cao, dẫn tới dư thừa của cải đủ cho gấp đôi dân số vào lúc đó. Vì thế mọi người làm theo năng lực, và hưởng theo nhu cầu.

Vì công việc chuyên môn hóa tới mức độ cao nhất, nên trong việc kinh doanh buôn bán cũng vậy. Ở một khu phố nọ, có \(n\) cửa hàng xếp kề nhau, đánh số từ \(1\) tới \(n\) theo chiều từ đầu tới cuối phố. Mỗi cửa hàng chỉ bán một mặt hàng mang bản sắc riêng của mình, có giá là \(a_{i}\). Để chống cạnh tranh, các mặt hàng phục vụ các nhu cầu khác nhau, và giá cả cũng khác nhau. Để thuận tiện cho người mua hàng dễ tìm kiếm, các chủ tịệm đã cùng nhau thỏa thuận lại vị trí bán hàng, để giá của các mặt hàng giảm dần (nói chính xác thuật ngữ là không tăng) khi đi từ đầu tới cuối phố, hay nói cách khác là \(a_{i} \geq a_{i + 1}\) với mọi \(i\) thỏa mãn \(1 \leq i < n\).

Tuy nhiên, thị trường thế giới đang trong giai đoạn khó khăn, nên dù Sở Giao dịch Hàng hóa Việt Nam (Mercantile Exchange of Vietnam - MXV) rất cố gắng để bình ổn giá, thì nó vẫn lên xuống liên tục như là chơi chứng khoán ở hiện tại. Cứ mỗi lần vật giá tăng, thông tin sẽ được truyền từ MXV tới phố theo hướng từ đầu đường tới cuối đường. Tuy nhiên, người ta có thành ngữ "tam sao thất bản", nên thông tin thường chỉ được truyền tới giữa phố là dừng. Giả sử giá cả tăng lên ít nhất bằng \(y\), và tin truyền tới cửa hàng \(x\), thì với mỗi cửa hàng \(i\) sao cho \(1 \leq i \leq x\), giá sẽ được đổi lại thành \(a_{i} \leftarrow \max(a_{i}, y)\)

Người tiêu dùng tại khu phố này thì đi chợ rất theo nguyên tắc. Họ mang theo \(c\) đồng trong người, và sẽ bắt đầu từ một cửa hàng \(u\) bất kỳ để đi tới cuối phố. Với mỗi cửa hàng \(i\) họ đi ngang qua, người đó sẽ dừng lại, và mua một món hàng để ủng hộ cửa hàng \(i\) đấy nếu còn đủ tiền trong người. Tức nếu \(c \geq a_{i}\) thì \(c \leftarrow c - a_{i}\). Sau đó họ di chuyển sang cửa hàng tiếp theo và làm tương tự cho tới cuối đường.

Đó là những hoạt động mua thường diễn ra trên một khu phố buôn bán không-quá-sầm-uất.

Hôm nay, khu phố lần lượt diễn ra \(q\) hoạt động, mỗi hoạt động thuộc một trong hai loại sau:

• Hoạt động loại \(1\) là mỗi cửa hàng từ \(1\) tới \(x\) nghe tin vật giá tăng \(y\).
• Hoạt động loại \(2\) là có một người khách hàng đem theo \(c\) đồng để đi mua sắm, bắt đầu tại cửa hàng \(u\).

Tại mỗi thời điểm có người mua hàng, bạn hãy cho biết họ mua được bao nhiêu món đồ nhé.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 3 \times 10^{5})\) là số cửa hàng.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 2 \times 10^{13})\) lần lượt là giá của các cửa hàng.
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 3 \times 10^{5})\) là số hoạt động.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) thuộc một trong hai dạng sau:
  • \(1\) \(x\) \(y\): cho biết hoạt động thứ \(i\) là hoạt động loại \(1\), với các tham số \(x\) và \(y\) \((1 \leq x \leq n, 1 \leq y \leq 2 \times 10^{13})\) tương ứng;
  • \(2\) \(u\) \(c\), cho biết hoạt động thứ \(i\) là hoạt động loại \(2\), với các tham số \(u\) và \(c\) \((1 \leq u \leq n, 1 \leq c \leq 2 \times 10^{13})\) tương ứng.

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất trên một dòng là số lượng món hàng mà người này mua được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 5000\).
• Subtask \(2\) (\(20\%\) số điểm): \(a_{i}\) và \(y\) đều là lũy thừa cơ số \(2\) (số có dạng \(2^{k}\) với \(k\) là một số nguyên không âm) với mọi \(i\) thỏa mãn \(1\leq i \leq q\) và mọi \(y\) trong các hoạt động loại \(1\).
• Subtask \(3\) (\(15\%\) số điểm): Không có hoạt động loại \(1\).
• Subtask \(4\) (\(15\%\) số điểm): Các hoạt động loại \(1\) nằm trước các hoạt động loại \(2\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

8
1919 1650 1496 849 674 565 98 20
9
2 6 2356
1 1 236
1 7 1122
2 7 4086
2 5 6863
1 8 1532
1 8 825
1 2 1890
2 1 10000

3
2
4
6