Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMELLIP - Các hình Ellipse

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmellip


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ố AB được gọi là chỉ số hoàn hảo của hình Ellipse. Nếu với ellipse thứ i có ai > A hoặc bi > 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, rv, bạn cần đặt ai = v, với i thuộc đoạn [l, r].
  • Loại 2: Cho 3 số nguyên l, rv, bạn cần đặt bi = v, với i thuộc đoạn [l, r].
  • Loại 3: Cho 3 số nguyên lr và v, bạn cần đặt ai = ai + v, với i thuộc đoạn [l, r].
  • Loại 4: Cho 3 số nguyên lr và v, bạn cần đặt bi = bi + v, với i thuộc đoạn [l, r].
  • Loại 5: Cho lr, 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 lr, 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 ≤ 105
  • 1 ≤ a, b ≤ 106
  • -106 ≤ v ≤ 106
  • 1 ≤ A, B ≤ 106
  • 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

Được gửi lên bởi:VOJ Team
Ngày:2015-08-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VM - KrK

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.