VMELLIP - Các hình Ellipse

Giới hạn

• Thời gian: 1.0s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

---

• Người up: voj
• Nguồn bài: VM - KrK