Hôm nay Bờm mới được học về dãy số, Bờm thấy chúng rất thú vị, nên bài tập cô giáo cho về nhà làm Bờm đều cố gắng làm hết. Tuy nhiên đến bài cuối cùng thì Bờm nghĩ mãi không ra, và Bờm quyết định đi ngủ và đợi ngày mai hỏi các bạn thi HSG QG.

Bài toán cuối cùng của Bờm có phát biểu như sau: cho dãy số ~a_1, a_2, \dots, a_n~ có ~n~ phần tử đánh số từ 1 đến ~n~, đếm xem với dãy đã cho có bao nhiêu dãy con liên tiếp có chênh lệch của phần tử lớn nhất và phần tử nhỏ nhất là một số chẵn.

Yêu cầu: Hãy giúp Bờm giải quyết bài toán trên.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ (~1 \le a_i \le 10^9~).

Output

• Ghi ra một số nguyên duy nhất là số dãy con liên tiếp có chênh lệch giữa số lớn nhất và số nhỏ nhất là một số chẵn.

Sample Input 1

5
4 5 2 6 3

Sample Output 1

11

Bờm đang lập trình cho một cánh tay robot để có thể dùng phấn vẽ lên trên bảng đen, coi bảng đen là một mặt phẳng tọa độ chuẩn Oxy (trục Ox tăng từ trái sang phải, trục Oy tăng từ dưới lên trên).

Kế hoạch mô tả các thao tác thực hiện của cánh tay robot là một mảng gồm ~N~ vector ~(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)~, trong đó ~x_i~ và ~y_i~ là các số nguyên chẵn. Vận hành thực tế của cánh tay robot như sau: đầu tiên nó bắt đầu đặt viên phấn từ điểm (1, 1) và sau đó thực hiện ~N~ bước, ở bước thứ ~i~, cánh tay robot sẽ di chuyển viên phấn trên bảng từ điểm hiện tại ~(x, y)~ đến thẳng điểm ~(x + x_i, y + y_i)~. Ta có thể hình dung cánh tay robot đang vẽ một loại đường đứt đoạn trong mặt phẳng tọa độ, và các đoạn của đường đứt đoạn đó chính là các vector đã cho.

Trong khi Bờm đang nghĩ về cách thay đổi kế hoạch để thay đổi đường đứt đoạn mà robot có thể vẽ ra, anh ấy tự hỏi viên phấn sẽ đi qua các trục tọa độ bao nhiêu lần với đường robot sẽ vẽ ra với kế hoạch hiện tại. Do đó Bờm muốn có một chương trình mô phỏng quá trình thay đổi kế hoạch và trả lời các truy vấn số lần đi qua trục tọa độ với đường robot vẽ ra.

Giả sử kế hoạch mô tả các thao tác của robot chứa ~N~ vector là một mảng đánh số từ 1 đến ~N~. Ban đầu con trỏ của chương trình mô phỏng chỉ vào vị trí 1 của mảng này. Và chương trình mô phỏng cần thực hiện các lệnh sau:

• “B”: lùi con trỏ về vị trí trước vị trí hiện tại trong mảng (nếu vị trí hiện tại là ~i~ thì nó sẽ lùi về vị trí ~i - 1~, nếu ~i = 1~ thì nó giữ nguyên vị trí hiện tại).
• “F”: di chuyển con trỏ đến vị trí tiếp theo trong mảng (nếu vị trí hiện tại là ~i~ thì nó sẽ tiến đến vị trí ~i + 1~, nếu ~i = N~ thì nó giữ nguyên vị trí hiện tại).
• “C nx ny”: thay đổi vector của vị trí hiện tại của con trỏ trong mảng thành ~(nx, ny)~, với ~nx, ny~ cũng là những số nguyên chẵn.
• “Q”: trả lời câu hỏi của Bờm rằng với kế hoạch hiện tại thì đường robot sẽ vẽ ra có bao nhiêu lần đi qua trục tọa độ. Nếu đi qua gốc (0, 0) thì được tính là 2 lần đi qua trục tọa độ.

Yêu cầu: Hãy xây dựng chương trình mô phỏng nêu trên.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~).
• Tiếp theo là ~N~ dòng, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~ (~|x_i|, |y_i| \le 500~).
• Dòng tiếp theo chứa số nguyên ~M~ là số thao tác truy vấn (~1 \le M \le 3 \times 10^5~).
• Tiếp theo là ~M~ dòng, mỗi dòng mô tả một trong 4 truy vấn trên (~|nx|, |ny| \le 500~).

Output

• Ghi ra nhiều dòng, mỗi dòng ứng với kết quả của truy vấn loại “Q”.

Sample Input 1

5
6 2
0 -6
-2 2
-6 -8
4 0
12
Q
C 4 4
Q
F
F
F
C -6 -2
Q
B
B
C -4 -6
Q

Sample Output 1

3
5
5
4

Cuội càng ngày càng trở nên nghiện Vietlott, một trò chơi xổ số may rủi đã xuất hiện tại Việt Nam được vài năm nay. Trò xổ số diễn ra như sau:

• Cuội sẽ đến văn phòng xổ số gần nhất của Vietlott và chọn loại giải mình sẽ tham gia, mỗi loại giải của Vietlott tương ứng với độ dài của dãy số trên tờ vé số Cuội sẽ mua. Cuội có thể mua nhiều tờ vé số tùy ý.
• Vào cuối ngày, công ty Vietlott, với mỗi loại giải công ty sẽ quay số để tìm ra một dãy số may mắn ứng với từng loại giải.

Tất nhiên, Cuội sẽ giành được giải đặc biệt nếu một trong những tờ vé số anh ấy đã mua có dãy số trùng với dãy số may mắn ứng với loại giải của tờ vé số đó mà công ty Vietlott quay ra. Bạn của Cuội là Bờm làm trong công ty Vietlott đã quyết định giúp cậu bằng cách nói cho cậu biết một số đặc điểm của một dãy số may mắn:

• Dãy số chỉ bao gồm các số tự nhiên từ khoảng ~[1, N]~.
• Tất cả các số trong dãy số là phân biệt.
• Hai số liên tiếp trong dãy đều nằm trong danh sách các cặp số được phép đứng cạnh nhau trong dãy. Danh sách các cặp số được phép đứng cạnh nhau có đặc điểm sau:
  • Là một tập các cặp số khác nhau trong khoảng ~[1, N]~. Và nếu ta coi mỗi cặp số là một cạnh của một đồ thị.
  • Đồ thị tạo bởi tập các cặp số được phép đứng cạnh nhau là một đồ thị không có cạnh nào nằm trong nhiều hơn một chu trình đơn.

Bờm đã đưa cho Cuội một danh sách các cặp số được phép đứng cạnh nhau và Cuội quyết định ngày mai, Cuội sẽ mua số lượng vé bằng tất cả các dãy may mắn có thể xuất hiện của một loại giải để chắc chắn giành được giải thưởng. Nhưng trước đó, anh ấy cần biết loại giải nào sẽ giúp anh ấy có lợi nhất, để biết được điều này anh ấy cần tính toán với mỗi loại giải sẽ có bao nhiêu dãy số may mắn có thể quay ra tương ứng với loại giải đó. Sẽ có đúng ~N~ loại giải tương ứng với độ dài từ 1 đến ~N~ của dãy số may mắn.

Yêu cầu: Với giá trị ~L~ từ 1 đến ~N~, đếm xem có bao nhiêu dãy số may mắn có độ dài đúng bằng ~L~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 4000, 0 \le M \le 10^5~).
• ~M~ dòng tiếp theo mỗi dòng mô tả một cặp số có thể đứng cạnh nhau. Dữ liệu đảm bảo không có cặp số nào xuất hiện quá một lần trong dữ liệu.

Output

• Ghi ra trên một dòng gồm ~N~ số nguyên ~s_1, s_2, \dots, s_N~, số thứ ~i~ là kết quả số dãy may mắn có độ dài ~i~ lấy phần dư cho ~10^9 + 7~.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

3 4 2

Bờm và Cuội gần đây đã tìm thấy một bảng trò chơi xếp hình domino cổ đại. Bảng có dạng hình chữ nhật được chia thành các lưới ô vuông kích thước ~N \times M~, các hàng được đánh số từ 1 đến ~N~, các cột được đánh số từ 1 đến ~M~, và ~N~ và ~M~ là các số tự nhiên lẻ. Bảng được lấp đầy bởi ~\frac{N \times M - 1}{2}~ quân domino, mỗi domino chiếm hai ô liền kề, một số domino được đặt theo chiều ngang, một số lại được đặt theo chiều dọc, và rõ ràng sẽ có một ô trên bảng không bị quân domino nào đặt lên.

Bờm và Cuội nhìn vào bảng này và nghĩ về tất cả những nhiệm vụ tuyệt vời có thể nghĩ ra từ bảng xếp hình domino này. Một ý tưởng ngay lập tức nảy ra với họ. Với cách đặt các ô domino trên một bảng hiện tại, thì có thể di chuyển được bao nhiêu quân domino từ vị trí ban đầu của chúng đến vị trí khác, hay có bao nhiêu quân domino có thể thay đổi vị trí?

Ví dụ, đối với một bảng được sắp xếp như trên, ô trống ở vị trí ~(1, 5)~, trước tiên chúng ta có thể di chuyển domino đặt trên các ô ~(2, 5), (3, 5)~ lên trên và do đó, ô trống sẽ là ô ~(3, 5)~. Sau khi di chuyển nó, nhiều khả năng hơn sẽ mở ra, vì vậy giả sử ta có thể di chuyển domino ở các ô ~(4, 5), (5, 5)~ lên trên hoặc domino ở ~(3, 3), (3, 4)~ về phía phải. Trong tổng số 12 quân cờ domino trên bảng này, tám quân trong đó có thể được di chuyển khỏi vị trí ban đầu của chúng theo một cách nào đó.

Yêu cầu: Hãy viết một chương trình đếm xem có bao nhiêu quân cờ domino khác nhau có thể được di chuyển ra vị trí khác theo một cách nào đó.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ là số hàng và số cột của bảng, cả hai đều là các số lẻ (~1 \le N, M < 500~).
• Dòng thứ ~i~ trong ~\frac{N \times M - 1}{2}~ tiếp theo, mỗi dòng chứa bốn số nguyên dương ~x_1, y_1, x_2, y_2~ tương ứng là vị trí đặt của quân domino thứ ~i~ trên bảng là hai ô ~(x_1, y_1)~ và ~(x_2, y_2)~, với ~x_1, x_2~ là chỉ số hàng và ~y_1, y_2~ là chỉ số cột. Dữ liệu đảm bảo các quân domino không xếp chồng lên nhau, không vượt quá giới hạn của bảng, và hai ô của một quân domino đặt lên là hai ô kề nhau trên bảng.

Output

• Ghi ra một số nguyên duy nhất là số quân domino có thể di chuyển ra vị trí khác với vị trí ban đầu.

Sample Input 1

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

Sample Output 1

8

Ban ra đề đang viết chương trình sinh test cho một bài về đồ thị. Họ cần sinh một đơn đồ thị vô hướng ~n~ đỉnh ~m~ cạnh. Thuật toán sinh như sau:

1. Nếu đã lấy đủ ~m~ cạnh thì dừng.
2. Gọi ~E~ là tập các cặp ~(u, v)~ với ~u < v~ và ~u~ đang không kề với ~v~, tức ~E~ là tập các cạnh chưa có trong đồ thị.
3. Sắp xếp ~E~ theo thứ tự từ điển (~(u, v)~ đứng trước ~(x, y)~ nếu hoặc là ~u < x~ hoặc là ~u = x~ và ~v < y~).
4. Chọn một số tự nhiên ~i~ trong phạm vi từ ~1~ đến ~|E|~.
5. Nạp cạnh thứ ~i~ trong ~E~ vào đồ thị, lặp lại bước 1.

Cho biết các số được chọn ở bước thứ 4, hãy giúp ban ra đề in ra các cạnh của đồ thị. Lưu ý, các loại chỉ số trong bài đều được đánh số bắt đầu từ ~1~.

Input

• Dòng đầu chứa hai số nguyên dương là số đỉnh và số cạnh của đồ thị: ~n, m~.
• ~m~ dòng tiếp theo, dòng thứ ~t~ chứa một số nguyên dương là số được chọn ở bước thứ 4 của lần lặp thứ ~t~: ~i_t~.

Output

In ra ~m~ cạnh được chọn theo thứ tự chọn của thuật toán. Với mỗi cạnh, in ra hai đỉnh trên một dòng cách nhau bởi dấu cách, đỉnh bé hơn phải được in trước.

Sample Input 1

4 4
3
3
1
3

Sample Output 1

1 4
2 3
1 2
3 4

Giải thích:

• Ban đầu ~E = \{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}~ nên cạnh thứ 3 là ~(1, 4)~.
• Tiếp theo ~E = \{(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)\}~ nên cạnh thứ 3 là ~(2, 3)~.
• Tiếp theo ~E = \{(1, 2), (1, 3), (2, 4), (3, 4)\}~ nên cạnh thứ 1 là ~(1, 2)~.
• Tiếp theo ~E = \{(1, 3), (2, 4), (3, 4)\}~ nên cạnh thứ 3 là ~(3, 4)~.

Hùng vừa cắt một tấm gỗ mỏng hình chữ nhật thành nhiều miếng hình chữ nhật. Máy cưa cậu dùng mỗi lần sẽ nhận vào một miếng gỗ hình chữ nhật và cắt làm hai hình chữ nhật với tổng diện tích không đổi. Vị trí cắt có thể điều chỉnh được, chi phí cắt phụ thuộc vào trọng lượng miếng gỗ, do miếng gỗ ban đầu có độ dày đồng đều nên chi phí cắt có thể xem là diện tích miếng gỗ đó.

Miếng gỗ ban đầu có kích thước ~n \times m~. Hùng đã dùng bút vẽ ~n - 1~ đường kẻ ngang và ~m - 1~ đường kẻ dọc, kết hợp với các đường biên chia hình chữ nhật thành một lưới tọa độ. Các điểm được đánh tọa độ từ ~(0, 0)~ đến ~(n, m)~ từ trên xuống dưới, từ trái qua phải. Các lát cắt đều song song với biên và được đánh dấu bởi tọa độ các điểm này. Mỗi lát cắt là một đường liên tục và cắt dứt điểm một miếng nào đó làm hai phần. Miếng gỗ ban đầu đã được cắt xong, Hùng cần báo cáo lại quá trình cắt. Cậu nhớ chính xác tọa độ tất cả các lát cắt mà mình thực hiện, tuy nhiên không nhớ chính xác thứ tự đã cắt. Hùng đưa cho bạn danh sách các lát cắt này và nhờ bạn sắp xếp lại thứ tự cho hợp lý. Cậu cũng biết rằng có thể có nhiều thứ tự khác nhau, và quả quyết rằng trong số các thứ tự đúng đó, mình đã cắt theo một thứ tự có tổng chi phí cắt là nhỏ nhất.

Yêu cầu: Hãy giúp Hùng tìm ra một thứ tự cắt (tức hoán vị các lát cắt theo trí nhớ của Hùng) hợp lý và có tổng chi phí nhỏ nhất, hoặc thông báo là cậu đã nhớ nhầm.

Input

• Dòng đầu chứa ba số nguyên dương là kích thước ban đầu và số lát cắt: ~n, m, k~ (~1 \le n, m \le 10^9, 1 \le k \le 10^5~).
• ~k~ dòng tiếp theo, mỗi dòng ghi một lát cắt: ~u, v, x, y~ (~0 \le u \le x \le n, 0 \le v \le y \le m~) có nghĩa lát cắt này kéo dài từ điểm ~(u, v)~ đến điểm ~(x, y)~. Dữ liệu đảm bảo lát cắt song song với biên, không trùng lên biên của hình chữ nhật đang cắt và có độ dài khác ~0~.

Output

Nếu không có thứ tự nào hợp lý, in ra ~-1~. Ngược lại in ra trên hai dòng:

• Dòng đầu chứa chi phí cắt nhỏ nhất tìm được.
• Dòng tiếp theo chứa ~k~ số là một hoán vị của ~\{1, 2, \ldots, k\}~ cho biết thứ tự các lát cắt tìm được.

Dữ liệu đảm bảo chi phí nhỏ nhất nếu có sẽ không vượt quá ~10^{18}~.

Sample Input 1

5 10 11
3 5 5 5
3 0 3 10
0 5 3 5
1 5 1 10
2 5 2 10
4 5 4 10
3 1 5 1
3 2 5 2
3 3 5 3
3 4 5 4
1 8 2 8

Sample Output 1

164
2 1 3 4 5 6 8 7 9 11 10