Trong văn hóa Á Đông xưa, các con số ~1, 5, 9~ thường được xem là tốt lành, vì chúng ứng với sinh, tức sinh sôi, nảy nở, trong chu trình sinh - lão - bệnh - tử.

Huy đang nghiên cứu các văn bản cổ, và anh thấy người xưa gọi một số là cát tường nếu biểu diễn thập phân của nó chỉ bao gồm các chữ số ~1, 5~ hoặc ~9~, và không có hai chữ số liên tiếp nào giống nhau. Như vậy, các số cát tường đầu tiên là ~1, 5, 9, 15, 19, 51, 59, 91, 95, 151, ...~.

Huy tiếp tục nghiên cứu, và anh thấy người xưa đã cố gắng tách các số tự nhiên thành tổng của hai số cát tường theo những cách khác nhau. Ví dụ, số ~2~ có thể được tách thành ~1 + 1~, ~10~ có thể được tách thành ~5 + 5~ hoặc ~1 + 9~. Họ ký hiệu ~f_x~ là số cách tách tổng của hai số cát tường. Như vậy, ~f_2 = 1~ và ~f_{10} = 2~. Huy tìm thấy một bài toán, trong đó yêu cầu tính tổng ~S = f_l + f_{l + 1} + ... + f_r~, nhưng vẫn chưa có lời giải hay công thức cụ thể. Bạn hãy giúp Huy tính toán giá trị ~S~ với các cặp ~l, r~ khác nhau để có thể giúp Huy tìm ra công thức tổng quát cho bài toán nhé.

Dữ liệu - Nhập từ tệp văn bản INTEGER.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~l, r~ ~(1 \le l \le r \le 10^{18})~.

Kết quả - Ghi ra tệp văn bản INTEGER.out:

• Một dòng duy nhất gồm giá trị ~S~ tìm được.

Chấm điểm

Ví dụ

Dữ liệu (INTEGER.inp)

2 10

Kết quả (INTEGER.out)

4

Giải thích

Ta có ~f_2 = 1, f_6 = 1~ và ~f_{10} = 2~. Có thể thấy các giá trị còn lại không có cách nào để tách thành hai số cát tường.

Cho một bảng kích thước ~n \times m~: có ~n~ hàng và ~m~ cột. Ta gọi giá trị của ô nằm trên hàng ~x~ ~(1 \leq x \leq n)~ và cột ~y~ ~(1 \leq y \leq m)~ là ~a_{x,\ y}~.

Bạn được phép chọn một số ô với quy tắc: Nếu ô ~(p,\ q)~ được chọn thì các ô ~(p - 1,\ q)~ và ~(p,\ q - 1)~ (nếu tồn tại trong bảng) sẽ không thể được chọn nữa. Hay nói cách khác: không được chọn hai ô mà có một ô nằm ngay bên trên hoặc bên trái ô còn lại.

Hãy tìm ra cách chọn sao cho tổng giá trị của các ô được chọn là lớn nhất có thể.

Dữ liệu - Nhập từ tệp văn bản BOARD.inp:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \times m \leq 400)~.
• ~n~ dòng tiếp theo mỗi dòng thứ ~i~ chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2},... , a_{i, m}~ ~(|a_{i, j}| \leq 10^9)~.

Kết quả - Ghi ra tệp văn bản BOARD.out:

• Gồm một dòng duy nhất chứa kết quả bài toán.

Chấm điểm

Ví dụ

Dữ liệu (BOARD.inp)

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

Kết quả (BOARD.out)

20

Giải thích

• Ta chọn các ô ~(1, 2)~, ~(1, 4)~, ~(2, 1)~, ~(2, 3)~, ~(3, 2)~ và ~(3, 4)~, khi đó kết quả là ~2 + 4 + 3 + 4 + 3 + 4 = 20~.

Dữ liệu (BOARD.inp)

4 5
-7 -6 10 -6 -2
9 -3 -7 8 9
-8 -5 -9 -2 -1
-3 4 -4 -2 -6

Kết quả (BOARD.out)

32

Dữ liệu (BOARD.inp)

1 7
7 7 1 1 8 15 3

Kết quả (BOARD.out)

23

Trên một con đường có hai hàng cột đèn chiếu sáng. Hàng bên trái gồm ~n~ cột đèn, hàng bên phải gồm ~m~ cột đèn. Các cột đèn ở bên trái được đặt thẳng hàng với nhau, các cột đèn ở bên phải được đặt thẳng hàng với nhau. Tất cả các cột đèn đều có cùng chiều cao. Một hôm, Huy đi qua con đường này và chợt nghĩ ra một bài toán rất thú vị: Có bao nhiêu cách nối các đường dây điện cho các cột đèn này, sao cho:

• Sử dụng chính xác ~n+m-1~ đường dây điện.
• Mỗi đường dây điện nối chính xác 2 cột đèn.
• Với mọi cặp cột đèn bất kỳ, luôn tồn tại một đường đi giữa hai cột đèn này (trực tiếp qua một đường dây điện hoặc gián tiếp thông qua các dây điện và cột đèn trung gian).
• Khi tất cả các dây điện đều được căng ra, hai dây điện bất kỳ không được có điểm chung nào trừ cột đèn là đầu mút chung của chúng (nếu có).

Huy suy nghĩ rất lâu vẫn chưa thể tìm ra cách giải bài toán. Bạn hãy thử giải bài toán này cùng Huy nhé.

Dữ liệu - Nhập từ tệp văn bản CONNECT.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 5000)~.

Kết quả - Ghi ra tệp văn bản CONNECT.out:

• Một dòng duy nhất gồm phần dư của kết quả tìm được khi chia cho ~10^9 + 7~.

Chấm điểm

Ví dụ

Dữ liệu (CONNECT.inp)

2 2

Kết quả (CONNECT.out)

12

Giải thích

Có tổng cộng 12 cách nối dây như liệt kê ở hình trên.

Giang gọi một dãy số là một khối nếu dãy số đó có độ dài là ~k+1~, và phần tử đầu tiên của dãy là ~k~ (~k~ có thể là số nguyên dương bất kỳ).

Ví dụ, ~(2,1,2)~ hoặc ~(1,2)~ là một khối, tuy nhiên ~(2,1)~ không phải một khối.

Giang gọi một dãy số là đẹp nếu có thể tồn tại một cách lặp lại các thao tác dưới đây cho đến khi dãy trở thành dãy rỗng (không còn phần tử nào):

• Chọn một đoạn con liên tiếp trong dãy sao cho đoạn con được chọn là một khối.
• Xóa đoạn con được chọn khỏi dãy và dồn các phần tử phía sau lên trước.

Ví dụ, ~(1,2,1,2,1,4,4)~ là một dãy đẹp vì có thể xóa dãy như sau:

• Chọn đoạn ~(1,2)~ bắt đầu ở vị trí ~3~. Hiển nhiên đoạn này là một khối. Xóa đoạn khỏi dãy. Dãy trở thành ~(1,2,1,4,4)~.
• Chọn đoạn ~(2,1,4)~ bắt đầu ở vị trí ~2~. Hiển nhiên đoạn này là một khối. Xóa đoạn khỏi dãy. Dãy trở thành ~(1,4)~.
• Chọn đoạn ~(1,4)~ bắt đầu ở vị trí ~1~. Hiển nhiên đoạn này là một khối. Xóa đoạn này và dãy trở thành dãy rỗng.

Giang đưa cho Huy một dãy ~a_1, a_2, …, a_n~. Cô đố Huy đếm xem có bao nhiêu đoạn con liên tiếp của dãy ~a~ là dãy đẹp. Tuy nhiên Huy còn bận làm một số việc khác nên không chưa thể trả lời câu hỏi này. Bạn hãy trả lời giúp Huy nhé.

Đoạn con liên tiếp là một đoạn con thu được bằng cách xóa không, một hoặc một vài phần tử ở đầu và cuối dãy và giữ nguyên thứ tự các phần tử còn lại. Ví dụ, ~(3, 4), (3, 4, 5)~ hay ~(1)~ đều là các đoạn con liên tiếp của ~(1, 2, 3, 4, 5)~ nhưng ~(1, 3)~ hay ~(3, 2)~ thì không. Đoạn con liên tiếp gồm các phần tử ở vị trí thứ ~l~ đến vị trí thứ ~r~ có thể được gọi là đoạn ~(l, r)~.

Dữ liệu - Nhập từ tệp văn bản DRANGE.inp:

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 7000)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le n)~.

Kết quả - Ghi ra tệp văn bản DRANGE.out:

• Một dòng duy nhất gồm số lượng đoạn con liên tiếp của dãy ~a~ là dãy đẹp.

Chấm điểm

Ví dụ

Dữ liệu (DRANGE.inp)

5
1 2 1 2 4

Kết quả (DRANGE.out)

5

Giải thích

• Các đoạn ~(l, r)~ là đoạn đẹp trong dãy là: ~(1,2),(2,4),(3,4),(1,4),(1,5)~.

Cho hai số nguyên dương ~N~ và ~Q~.

Có một cây gồm ~N~ đỉnh, mỗi đỉnh thứ ~i~ ~(1\leq i\leq N)~ cây có một giá trị ~A_i~. Bạn cần trả lời ~Q~ truy vấn có dạng như sau:

• Cho một đỉnh ~X~ ~(1\leq X\leq N)~, hãy tìm đỉnh ~Y~ sao cho giá trị

$$A_Y - A_X - D(X,\ Y)^2$$

là lớn nhất, với ~D(X,\ Y)~ là số cạnh trên đường đi ngắn nhất từ đỉnh ~X~ đến đỉnh ~Y~ trên cây, sau đó đưa ra giá trị lớn nhất đó.

Dữ liệu - Nhập từ tệp văn bản TREE.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ ~(1\leq N,\ Q\leq 2\times 10^5)~.
• Dòng tiếp theo gồm ~N~ số nguyên ~A_1,\ A_2,\ \dots,\ A_N~ ~(1\leq A_1,\ A_2,\ \dots,\ A_N\leq 10^9)~.
• ~N - 1~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~U~ và ~V~ mô tả có một cạnh từ đỉnh ~U~ đến đỉnh ~V~ trên cây.
• ~Q~ dòng tiếp theo mỗi dòng gồm một số nguyên ~X~ mô tả các truy vấn ~(1\leq X\leq N)~.

Kết quả - Ghi ra tệp văn bản TREE.out:

• Gồm ~Q~ dòng chứa kết quả bài toán.

Chấm điểm

Ví dụ

Dữ liệu (TREE.inp)

6 6
10 5 15 6 12 5
1 2
1 3
2 4
2 5
3 6
1
2
3
4
5
6

Kết quả (TREE.out)

4
6
0
2
0
9

Giải thích

• Với đỉnh ~X = 1~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_1 - D(1,\ 3)^2 = 15 - 10 - 1 = 4~.
• Với đỉnh ~X = 2~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_2 - D(2,\ 3)^2 = 15 - 5 - 4 = 6~.
• Với đỉnh ~X = 3~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_3 - D(3,\ 3)^2 = 15 - 15 - 0 = 0~.
• Với đỉnh ~X = 4~, ta tìm được đỉnh tương ứng là ~Y = 5~, khi đó, giá trị cần tìm là ~A_5 - A_4 - D(4,\ 5)^2 = 12 - 6 - 4 = 2~.
• Với đỉnh ~X = 5~, ta tìm được đỉnh tương ứng là ~Y = 5~, khi đó, giá trị cần tìm là ~A_5 - A_5 - D(5,\ 5)^2 = 12 - 12 - 0 = 0~.
• Với đỉnh ~X = 6~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_6 - D(6,\ 3)^2 = 15 - 5 - 1 = 9~.
• Dưới đây là hình dạng của cây: