Để chọn lựa các vị thần cho thiên đường infinity, đấng tối cao doangiaphuc13 đã quyết định sẽ cho các thí sinh ứng cử một bể nước hình hộp chữ nhật được chia thành \(n\) ngăn liên tiếp bởi \(n-1\) vách ngăn thẳng đứng, mỏng (bề dày không đáng kể). Đáy bể phẳng, nằm ngang ở độ cao \(0\); mỗi ngăn có diện tích đáy bằng \(1\) đơn vị, do đó thể tích nước trong một ngăn đúng bằng chiều cao cột nước của ngăn đó. Vách thứ \(i\) \((1 \le i \le n-1)\) nằm giữa ngăn \(i\) và ngăn \(i+1\), có chiều cao \(h_i\). Các \(h_i\) đôi một khác nhau. Hai thành ngoài cùng (bên trái ngăn \(1\) và bên phải ngăn \(n\)) cao vô hạn nên nước không bao giờ chảy ra khỏi bể. Gọi \(y_i\) là mực nước (chiều cao cột nước) ở ngăn \(i\). Theo nguyên lí bình thông nhau, nước chảy qua vách \(i\) từ ngăn \(i\) sang ngăn \(i+1\) khi và chỉ khi \(y_i > h_i\) và \(y_i > y_{i+1},\) và chảy theo chiều ngược lại khi \(y_{i+1} > h_i\) và \(y_{i+1} > y_i.\) Hệ ở trạng thái cân bằng khi không có vách nào đang có nước chảy qua. Nói riêng, hai ngăn kề nhau có mực nước bằng nhau và cùng không thấp hơn đỉnh vách giữa chúng tạo thành một khối nước thông nhau. Sau đó chúng luôn dâng lên cùng nhau. Các thí sinh cần xử lí \(q\) thao tác, mỗi thao tác thuộc một trong ba loại:

• 1 p v — đổ từ từ (thành một dòng rất nhỏ) tổng cộng \(v\) đơn vị thể tích nước vào ngăn \(p\). Trong suốt quá trình đổ, hệ luôn kịp trở về trạng thái cân bằng; nước đầy tràn qua vách thấp hơn của một khối nước sẽ chảy tiếp sang ngăn bên kia, có thể tràn qua nhiều vách liên tiếp.
• 2 p — cho biết mực nước hiện tại của ngăn \(p\).
• 3 l r — cho biết mực nước lớn nhất trong các ngăn \(l,l+1,\dots,r\).

Mực nước nói chung không nguyên, nên hãy in nó dưới dạng phân số tối giản.

Chú ý: Áp suất do nước gây ra ở đáy ngăn \(i\) là \(p_i=d\cdot y_i\) với \(d\) là trọng lượng riêng của nước, nên mực nước và áp suất đáy chỉ sai khác một hằng số.

Input

Dòng đầu chứa hai số nguyên \(n\) và \(q\) — số ngăn và số thao tác.

Dòng thứ hai chứa \(n-1\) số nguyên \(h_1,h_2,\dots,h_{n-1}\) — chiều cao các vách ngăn, đôi một khác nhau.

\(q\) dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong ba dạng:

• 1 p v
• 2 p
• 3 l r

Ràng buộc

• \(2 \le n \le 2\cdot10^5\), \(1 \le q \le 2\cdot10^5\).
• \(1 \le h_i \le 10^9\), các \(h_i\) đôi một khác nhau.
• \(1 \le p \le n\).
• \(1 \le v \le 10^9\).
• \(1 \le l \le r \le n\).
• Ban đầu bể hoàn toàn khô: \(y_i=0\) với mọi \(i\).

Output

Với mỗi thao tác loại \(2\) hoặc loại \(3\), in trên một dòng hai số nguyên \(a\) và \(b\) sao cho mực nước cần tìm bằng \(\frac{a}{b},\) với \(\gcd(a,b)=1\) và \(b\ge1\).

Nếu mực nước bằng \(0\) thì in 0 1.

Example

5 10
3 1 4 2
1 1 2
2 1
1 1 5
3 1 5
1 5 5
2 4
3 2 4
1 3 20
2 1
3 1 1

2 1
3 1
5 2
5 2
32 5
32 5

3 8
5 2
1 1 4
2 1
1 1 4
3 1 3
2 3
1 3 5
2 2
3 1 3

4 1
5 1
1 1
4 1
5 1

Scoring

• Subtask 1 (30 điểm): \(n,q\le2000\).
• Subtask 2 (30 điểm): \(n,q\le2\cdot10^5\) và không có thao tác loại \(3\).
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.