Trong phòng thí nghiệm có \(n\) mẫu vật xếp thành một hàng. Mẫu vật thứ \(i\) có khối lượng \(m_i\) và thể tích \(v_i\).

Nếu ghép các mẫu vật từ \(a\) đến \(b\) thành một khối thì khối đó có khối lượng \(m_a + \cdots + m_b\) và thể tích \(v_a + \cdots + v_b\). Khối lượng riêng của khối là

Bạn cần xử lí \(q\) thao tác. Mỗi thao tác thuộc một trong ba loại:

• 1 p x y — thay mẫu vật \(p\) bằng một mẫu mới có khối lượng \(x\) và thể tích \(y\): \(m_p=x,\ v_p=y\).
• 2 p x — gắn thêm vào mẫu vật \(p\) một khối lượng \(x\), thể tích không đổi: \(m_p=m_p+x\).
• 3 l r — trong tất cả các đoạn \([a,b]\) với \(l\le a\le b\le r\), tìm đoạn có khối lượng riêng lớn nhất.

Nếu có nhiều đoạn cùng đạt giá trị lớn nhất, chọn đoạn có \(a\) nhỏ nhất. Nếu vẫn còn nhiều đoạn, chọn đoạn có \(b\) nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(m_1,m_2,\ldots,m_n\).
• Dòng thứ ba chứa \(n\) số nguyên \(v_1,v_2,\ldots,v_n\).
• Dòng thứ tư chứa số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng mô tả một thao tác theo một trong ba dạng trên.

Ràng buộc

• \(1\le n,q\le 2\cdot10^5\).
• \(1\le m_i,v_i\le10^9\).
• Sau mọi thao tác, luôn có \(1\le m_i,v_i\le10^9\).
• Với thao tác loại \(1\): \(1\le p\le n,\ 1\le x,y\le10^9\).
• Với thao tác loại \(2\): \(1\le p\le n,\ 1\le x\) và \(m_p+x\le10^9\).
• Với thao tác loại \(3\): \(1\le l\le r\le n\).

Output

Với mỗi thao tác loại 3, in trên một dòng ba giá trị a b p/q, trong đó \([a,b]\) là đoạn được chọn và

Phân số \(p/q\) phải được tối giản. Vì mọi \(v_i>0\) nên mẫu số luôn dương.

Example

4
2 10 3 8
4 5 2 8
6
3 1 4
3 3 4
1 2 20 5
3 1 4
2 3 5
3 2 4

2 2 2/1
3 3 3/2
2 2 4/1
2 2 4/1

Scoring

• Subtask 1 (15 điểm): \(n,q\le300\).
• Subtask 2 (25 điểm): Không có thao tác cập nhật, tức là mọi thao tác đều thuộc loại 3. \(n,q\le2\cdot10^5\)
• Subtask 3 (60 điểm): Không có giới hạn gì thêm. \(n,q\le2\cdot10^5\)