Bản đồ một khu vực đồi núi được mô tả bằng bảng số gồm ~m~ dòng và ~n~ cột. Các dòng của bảng được đánh số từ 1 đến ~m~, từ trên xuống dưới. Các cột của bảng được đánh số từ 1 đến ~n~, từ trái sang phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ của bảng gọi là ô ~(i, j)~ được điền số ~h_{i,j}~ là chiều cao của vùng đất tương ứng so với mực nước biển.

Công ty du lịch AZ muốn xây dựng một tour du lịch leo núi, cụ thể công ty cần tìm một đường đi tăng trên bảng số là một dãy liên tiếp các ô chung cạnh mà các số điền trong các ô theo thứ tự tăng dần.

Yêu cầu: Cho bảng số mô tả chiều cao của các vùng đất, hãy tìm đường đi tăng trên bảng số gồm nhiều ô nhất.

Dữ liệu vao:

• Dòng đầu tiên chứa hai số nguyên ~m, n~;
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên ~a_{i,1}~, ~a_{i,2}~, ..., ~a_{i,n}~ (các số không vượt quá ~10^9~).

Kết quả: Ghi ra gồm một dòng chứa một số là số ô trên đường đi tìm được.

Vi du:

INPUT

3 3
1 1 0
1 2 3
2 2 5

OUTPUT

5

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài có ~m,n~ ≤ 10;
• Có 25% test khác ứng với 25% số điểm của bài có ~m,n~ ≤ 100;
• Có 25% test khác ứng với 25% số điểm của bài có ~m,n~ ≤ 1000;
• Có 25% số test còn lại ứng với 25% số điểm của bài có ~m× n~ ≤ ~10^6~.

Cho 8 số nguyên không âm ~𝑑_1~, ~𝑑_2~, … , ~𝑑_4~ và ~𝑟_1~, ~𝑟_2~, … , ~𝑟_4~ trong đó ~∀𝑖~: 0 ≤ ~𝑟_𝑖~ < ~𝑑_𝑖~ Tìm số nguyên dương ~𝑛~ bé nhất thỏa mãn: ~𝑛~ chia ~𝑑_𝑖~ dư đúng ~𝑟_𝑖~ (~∀𝑖~: 1 ≤ ~𝑖~ ≤ 4)

Dữ liệu vào:

• Dòng 1 chứa số ~𝑇~ ≤ ~10^4~ là số test.
• ~T~ khối dòng tiếp theo mỗi khối 4 dòng chứa dữ liệu cho 1 test: Dòng thứ ~𝑖~ chứa cặp số nguyên ~𝑑_𝑖~ , ~𝑟_𝑖~ cách nhau bởi dấu cách (0 ≤ ~𝑟_𝑖~ < ~𝑑_𝑖~ ≤ ~10^4~)

Kết quả: với mỗi test ghi ra một số nguyên dương duy nhất là số ~𝑛~ tìm được, trong trường hợp không tồn tại số ~𝑛~ thỏa mãn điều kiện, ghi ra số -1.

Ví dụ:

Input:

2
20 3
15 3
21 18
35 18
5 1
5 2
5 3
5 4

Output:

123
-1

Từ xâu nhị phân ~𝑆_0~ = "1" người ta sinh ra các xâu ~𝑆_1~, ~𝑆_2~, … , ~𝑆_𝑛~ trong đó ~𝑆_𝑖~ = ~𝑆_{𝑖−1}~ + ~𝑆_{𝑖−1}~. Ở đây ~𝑆_{𝑖−1}~ là xâu nhị phân tạo thành từ xâu 𝑆𝑖−1 bằng cách đảo hết các bit (bit 1 thành bit 0 và bit 0 thành bit 1).

Ví dụ:

~𝑆_0~ = "1"

~𝑆_1~ = "10"

~𝑆_3~ = "10010110"

~𝑆_4~ = "1001011001101001"

Yêu cầu: Cho số nguyên dương ~𝑛~, hãy xác định trong xâu ~𝑆_𝑛~ có bao nhiêu vị trí có 2 bit liên tiếp bằng nhau (tức là đếm số lần xuất hiện của xâu "00" và "11" trong 𝑆𝑛) Dữ liệu vào:

• Dòng 1 chứa số nguyên dương ~T~ ≤ ~10^5~ là số test
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~𝑛~ ≤ ~10^9~ ứng với một test

Kết quả: Ghi ra ~T~ dòng, mỗi dòng ghi một số nguyên duy nhất là số dư của kết quả tìm được khi chia cho 123456789.

Ví dụ:

Input:

4
1
2
3
4

Output:

0
1
2
5

Giáo sư Hà Phong của trường đại học Nevada vừa công bố một phát hiện khoa học mới về hành tinh XYZ. Công bố của ông đã cho thấy có tồn tại sự sống của một loài cây trên hành tinh XYZ. Sự tồn tại và phát triển của loại cây này rất kì lạ. Mỗi cây được lớn lên từ hai "mầm", hai "mầm" này sẽ đâm lên khỏi mặt đất với độ cao ~H~ vào một ngày nào đó và dừng lại ở đó không phát triển thêm nữa. Cây khi đâm lên khỏi mặt đất sẽ có dạng như một hình chữ nhật (xem Hình 1), hai cạnh bên được gọi là "vertical" cạnh bắc ngang được gọi là "horizontal". Mỗi cây trên hành tinh đó được biểu diễn bởi ba số: các tọa độ ~x~ của các "vertical" là ~L~ và ~R~, và độ cao ~H~.

Mỗi ngày có một cây mới mọc lên từ hành tinh. Mỗi cây mới mọc lên có chiều cao lớn hơn chiều cao của cây mọc lên ngày liền trước đó một đơn vị. Khi một cạnh "vertical" một cây mới giao với một cạnh "horizontal" một cây khác thì có một bông hoa tại điểm giao đó được nở ra với điều kiện giao điểm đó không phải là các đầu mút của cạnh "horizontal" và tại điểm đó chưa từng tồn tại bông hoa nào.

Yêu cầu: Cho biết tọa độ "vertical" của các cây mọc lên mỗi ngày, cây mọc lên trong ngày thứ nhất có chiều cao bằng 1. Hãy cho biết mỗi ngày có bao nhiêu bông hoa mới xuất hiện.

Dữ liệu vao:

• Dòng đầu tiên ghi một số nguyên ~n~ (1 ≤ ~n~ ≤ 100.000) là số ngày.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L,R~ (1 ≤ ~L~ < ~R~ ≤ ~10^5~) là tọa độ các cạnh "vertical" của cây mọc lên vào ngày thứ ~i~.

Kết quả: Ghi ra ~n~ dòng, dòng thứ ~i~ là số bông hoa mới được nở ra trong ngày thứ ~i~.

Vi du:

INPUT 1

4 
1 4 
3 7 
1 6 
2 6

OUTPUT 1

0 
1
1 
2

INPUT 2

5 
1 3 
3 5 
3 9 
2 4
3 8

OUTPUT 2

0 
0
0 
3
2

Ràng buộc:

• Có 25% số test tương ứng 25% số điểm có ~n~ ≤ 5000, ~R~ ≤ 5000;
• Có 25% số test khác tương ứng 25% số điểm có ~n~ ≤ 5000, ~R~ ≤ ~10^6~;
• Có 25% số test khác tương ứng với 25% số điểm có ~n~ ≤ 50000,~R~ ≤ 250;
• 25% số test còn lại tương ứng 25% số điểm có ~n~ ≤ ~10^5~, ~R~ ≤ ~10^5~.