Nguồn: Học sinh Giỏi THPT Hà Nội năm 2008 - 2009

Cho hai số \(n, m\) nguyên dương (\(n, m \le 200\)). Hỏi trong biểu diễn thập phân của tổng \(S = 2^n + 3^m\) chữ số đầu tiên là chữ số nào?

Ví dụ: với \(n = 4, m = 2\) thì \(S = 25\) có chữ số đầu tiên là \(2\). Với \(n = 8, m = 4\) thì \(s = 337\) có chữ số đầu là \(3\).

Input

Dữ liệu vào từ tệp văn bản LT.IN:

• Gồm một dòng duy nhất ghi \(2\) số \(n, m\) cách nhau bởi dấu cách.

Output

Kết quả ra tệp văn bản LT.OU:

• Một số duy nhất là đáp số của bài toán.

Examples

4 2

2

8 4

3

Note

• Có \(50\%\) số test cho kết quả \(S \le 10^9\)

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2008 - 2009

Cho \(3\) hình chữ nhật có kích thước tương ứng là : \(a_i \times b_i\) (\(i = 1, 2, 3\)). Trong đó \(a_i, b_i\) là các số nguyên dương không vượt quá \(10^9\). Hỏi \(3\) hình chữ nhật trên có thể ghép thành một hình vuông không? Nếu ghép được hãy cho biết độ dài cạnh hình vuông đó, ngược lại ghi số \(0\).

Input

Dữ liệu vào từ tệp văn bản GH.IN:

• Gồm \(3\) dòng, mỗi dòng ghi \(2\) số nguyên dương là kích thước của một hình chữ nhật.

Output

Kết quả ra tệp văn bản GH.OU:

• Gồm một dòng duy nhất là đáp số của bài toán.

Examples

1 6
6 2
3 6

6

1 6
6 2
2 4

0

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2008 - 2009

Trên bàn cờ kich thước \(m \times n\) ô, gồm \(m\) dòng, \(n\) cột. Các dòng được đánh số từ \(1\) đến \(m\), từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái qua phải, mỗi ô ghi một số nguyên dương. Một quân mã đứng trên một ô của dòng \(1\) cần phải nhảy đến một ô nào đó của dòng \(m\) theo quy tắc đi của quân mã trên bàn cờ Quốc tế và chỉ được nhảy từ dòng có chỉ số bé đến dòng có chỉ số lớn hơn.

Yêu cầu: Tìm cách nhảy sao cho tổng các số ghi trên các ô mà quân mã nhảy qua là lớn nhất (kể cả ô đầu tiên mà quân mã đứng).

Input

Dữ liệu vào từ tệp văn bản QM.IN:

• Dòng đầu ghi số \(m, n\) (\(m, n \le 100\))
• \(m\) dòng sau mỗi dòng ghi \(n\) số nguyên dương, các số cách nhau một dấu cách.

Output

Kết quả ra tệp văn bản QM.OU:

• Một số duy nhất là tổng lớn nhất của các số ghi trên các ô mà quân mã nhảy qua.

Examples

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

26

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2008 - 2009

Có \(n\) câu lạc bộ (CLB) dự định tuyển học viên tại các trường học, mỗi CLB tuyển ít nhất \(2\) học viên. Do \(2\) CLB bất kì có thời gian sinh hoạt không giao nhau, nên mỗi học sinh có thể tham gia sinh hoạt tại nhiều CLB. Danh sách học sinh đăng ký tham gia được đánh số thứ tự là \(1, 2, 3, ...\). Do mọi học sinh đã đăng kí đều sẵn sàng tham gia vào mọi CLB và để dễ quản lý, các CLB đều chọn cho mình các học viên có số thứ tự liên tiếp nhau trong danh sách đã đăng ký (như vậy một học sinh có thể được chọn vào nhiều CLB và có thể có những học sinh không được chọn vào CLB nào). Sau đó mỗi CLB chọn ra ít nhất \(2\) học viên (trong số các học sinh thuộc danh sách trên) để đại diện cho CLB cuả mình. Một học viên có thể làm đại diện cho nhiều CLB nếu anh ta tham gia vào các CLB đó.

Yêu cầu: Chọn các học viên làm đại diện cho các CLB, sao cho số học viên được chọn là ít nhất.

Input

Dữ liệu vào từ tệp văn bản CLB.IN:

• Dòng đầu ghi số nguyên dương \(n\). (\(1 \le n \le 10000\))
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo ghi \(2\) số \(a_i, b_i\) (\(1 \le a_i < b_i \le 10^9\)) cho biết CLB thứ \(i\) chọn các học viên liên tiếp có số thứ tự từ \(a_i\) đến \(b_i\).

Output

Kết quả ra tệp văn bản CLB.OU:

• Một số duy nhất là số lượng nhỏ nhất các học viên thỏa mãn yêu cầu bài toán.

Examples

3
7 9
3 8
10 20

4

Note

• \(50\%\) số test có \(n \le 10^2\) và \(a_i,b_i <10^3\)