Giải bài trực tuyến

KrK có một trò chơi vô cùng thú vị cùng với các hình ellipse của mình. Mỗi hình Ellipse được đặc trưng bởi 2 con số nguyên dương là bán trục lớn a và bán trục nhỏ b.

KrK có N hình Ellipse đặt trên mặt bàn, các hình ellipse được đánh số lần lượt từ 1 đến N. Cặp số A và B được gọi là chỉ số hoàn hảo của hình Ellipse. Nếu với ellipse thứ i có a_i > A hoặc b_i > B thì hình ellipse đó được coi là không đẹp và sẽ biến mất khỏi mặt bàn (và không bao giờ trở lại). Và tất nhiên với hình ellipse nào mà có ai ≤ 0 hoặc bi ≤ 0 cũng sẽ biến mất khỏi mặt bàn (và không bao giờ trở lại). KrK có M truy vấn dành cho bạn như sau:

• Loại 1: Cho 3 số nguyên l, r và v, bạn cần đặt a_i = v, với i thuộc đoạn [l, r].
• Loại 2: Cho 3 số nguyên l, r và v, bạn cần đặt b_i = v, với i thuộc đoạn [l, r].
• Loại 3: Cho 3 số nguyên l, r và v, bạn cần đặt a_i = a_i + v, với i thuộc đoạn [l, r].
• Loại 4: Cho 3 số nguyên l, r và v, bạn cần đặt b_i = b_i + v, với i thuộc đoạn [l, r].
• Loại 5: Cho l và r, bạn cần in ra tổng diện tích các hình ellipse trong đoạn từ l đến r chia cho π (pi). Nếu hình ellipse trong đoạn [l, r] không còn nằm trên bàn nữa thì diện tích của nó bằng 0.
• Loại 6: Cho l và r, bạn cần in ra số lượng các hình ellipse còn nằm trên mặt bàn trong đoạn từ l đến r.

Input

Dòng đầu tiên chứa 2 số nguyên dương N và M – Số lượng hình ellipse ban đầu và số lượng truy vấn.

Dòng tiếp theo chứ 2n số nguyên, cặp thứ i miêu tả bán trục lớn ai và bán trục nhỏ bi của hình ellipse thứ i.

M dòng tiếp theo miêu tả các truy vấn KrK đề ra với định dạng sau t, l, r và v (nếu có) (1 ≤ t ≤ 6, 1 ≤ l ≤ r ≤ N) – với t là loại của truy vấn như đã miêu tả ở trên.

Dòng cuối cùng chứa 2 số nguyên dương A và B (Chỉ số hoàn hảo)

Output

Với mỗi truy vấn loại 5 và 6 in ra kết quả tương ứng ở mỗi dòng riêng biệt theo thứ tự.

Giới hạn

• 1 ≤ N, M ≤ 10⁵
• 1 ≤ a, b ≤ 10⁶
• -10⁶ ≤ v ≤ 10⁶
• 1 ≤ A, B ≤ 10⁶
• ^{Trong 20% số test, N, M ≤ 1000.}

Example

Input:

1 3
1 1
6 1 1 
3 1 1 1 
6 1 1
1 1

Output:

1
0