Trên một mặt hồ có rất nhiều lá sen xếp thành một hàng dài. Một ngày chủ nhật, Alice mang theo một vài con ếch ra bờ hồ để nghiên cứu cách nhảy của chúng trên những chiếc lá.

Alice đánh số các lá theo thứ tự tăng dần từ trái sang phải. Cô ta dự định thực hiện buổi thí nghiệm trong ~q~ phút. Mỗi phút Alice sẽ thực hiện một trong hai hành động sau:

• Thả một con ếch có bước nhảy bằng ~k~ vào chiếc lá thứ ~i~. Mỗi phút con ếch này sẽ nhảy về bên phải ~k~ lá. Hay nói cách khác, nếu ở phút thứ ~t~ con ếch đang ở chiếc lá thứ ~x~ thì ở phút thứ ~t + 1~ nó sẽ nhảy sang chiếc lá thứ ~x + k~.
• Đếm số con ếch đang ở trên các lá ~l, l + 1, ..., r~.

Do biết trước bước nhảy của những con ếch, Alice muốn tính toán trước kết quả của các hành động đếm để có thể đối chiếu với kết quả thực tế. Các bạn hãy giúp Alice thực hiện việc này nhé.

Dữ liệu

• Dòng đầu tiên gồm một số nguyên dương ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ mô tả hành động của Alice ở phút thứ ~i~ và thuộc một trong hai dạng sau:
  • ~1\ k\ i~: thả một con ếch có bước nhảy ~k~ ở chiếc lá ~i~ ~(1 \le i, k \le 10^5)~.
  • ~2\ l\ r~: đếm số con ếch trên những chiếc lá thuộc đoạn ~[l, r]~ ~(1 \le l \le r \le 10^5)~.

Kết quả

• In ra các số nguyên không âm là câu trả lời cho các hành động loại 2, mỗi câu trả lời in trên một dòng.

Ví dụ

Dữ liệu

5
1 1 2
1 2 1
2 1 4
1 1 1
2 2 4

Kết quả

2
1

Giải thích

Dưới đây là bảng cho biết vị trí của mỗi con ếch ở từng thời điểm.