Trong thời kì kháng chiến của dân tộc ta, đội công tác hậu cần được giao nhiệm vụ cấp bách là chế tạo đạn dược kịp thời để tiếp tế cho chiến trường. Người lính trong đội được cung cấp A đơn vị sắt và B đơn vị thuốc súng.

Biết rằng:

• Một viên đạn xuyên giáp cần 1 đơn vị thuốc súng và 2 đơn vị sắt
• Một viên đạn nổ cần 2 đơn vị thuốc súng và 1 đơn vị sắt

Với nguồn nguyên liệu sẵn có, người lính cần tính toán sao cho số lượng đạn chế tạo là nhiều nhất.

Yêu cầu: TÍnh số viên đạn tối đa có thể chế tạo.

Dữ liệu vào: Đọc từ file TIEPTE.INP hai số nguyên dương A và B ~(0 < A, B < 10^9)~

Dữ liệu ra: Ghi ra file TIEPTE.OUT một số nguyên là số đạn tối đa.

Sampple Input

6 8

Sample Output

4

Giải thích

Có thể làm 2 xuyên giáp + 2 đạn nổ hoặc 1 xuyên giáp + 3 đạn nổ

Ràng buộc:

• Subtask 1 (80%): ~A, B \le 10^5~
• Subtask 2 (20%): Không giới hạn

Trong tiết luyện tập về cách viết số tự nhiên, cô giáo cho các bạn chơi một trò chơi như sau.

Cô giáo cho ~n~ thẻ học, mỗi thẻ gồm hai số nguyên trong đó thẻ thứ ~k~ có phần bên trái là số nguyên ~A_k~, phần bên phải là số nguyên ~B_k~.

Cô thực hiện bốc ra hai thẻ i và j ~(i \ne j,\ 1 \le i,j \le n)~ và gập đôi chúng lại. Khi đó:

• thẻ i để lộ phần bên phải ~B_i~
• thẻ j để lộ phần bên trái ~A_j~

Sau đó, cô đặt hai phần này cạnh nhau để tạo ra một số mới ~B_iA_j~ và yêu cầu các bạn đọc số đó.

Ví dụ: Tấm thẻ thứ nhất chứa hai số ~(12, 34)~ và tấm thẻ thứ hai chứa hai số ~(567, 8)~, số ghép được là ~34567~ (tức ba mươi tư nghìn năm trăm sáu mươi bảy).

Yêu cầu: Hãy đưa ra số lớn nhất ghép được khi bốc ra hai trong ~n~ thẻ cho trước.

Dữ liệu vào

Đọc từ tệp văn bản GHEPTHE.INP:

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

• ~n~ dòng tiếp theo, mỗi dòng chứa hai số ~A_k~, ~B_k~ ~(1 \le A_k, B_k \le 10^9)~.

Dữ liệu ra

Ghi ra tệp GHEPTHE.OUT một số duy nhất là số ghép được.

Ví dụ

GHEPTHE.INP

3
12 32
3 52
367 1

GHEPTHE.OUT

52367

Giới hạn

• Subtask 1 (40%): ~n \le 1000~
• Subtask 2 (40%): với mọi thẻ ~A_i < B_i~; đồng thời với mọi ~i < n~ thì ~B_i \le A_{i+1}~
• Subtask 3 (20%): không có giới hạn nào khác.

Trong một lần thám hiểm tàn tích của một thư viện cổ, Kay tìm thấy một mảnh giấy kỳ lạ có chứa một thông điệp là một xâu gồm các kí tự chữ cái thường. Tưởng chừng xâu vô nghĩa nhưng Kay phát hiện một ghi chú ở góc mảnh giấy rằng:

"Đây là một phần của mật mã đối xứng được sử dụng bởi một tổ chức cổ bí ẩn".

Đáng tiếc, qua thời gian, phần mật mã đã bị mất đi một số kí tự. Nhiệm vụ của bạn là khôi phục lại mật mã đối xứng bằng cách chèn thêm ít kí tự nhất vào xâu kí tự mà Kay tìm được.

Dữ liệu vào

Đọc từ tệp văn bản MATMA.INP gồm một xâu ~S~.

Dữ liệu ra

Ghi ra tệp văn bản MATMA.OUT gồm một dòng duy nhất là số kí tự ít nhất cần chèn thêm vào xâu ~S~ để thu được một xâu đối xứng.

Ví dụ

Giới hạn

• Subtask 1 (50%): độ dài của xâu ~S~ không vượt quá ~255~ kí tự.
• Subtask 2 (50%): độ dài của xâu ~S~ không vượt quá ~10^3~ kí tự.

Trên bàn có ~n~ chiếc đĩa được đánh số từ ~1~ đến ~n~. Ban đầu, đĩa thứ ~i~ chứa ~i~ viên kẹo. Trong ~m~ ngày tiếp theo, mỗi ngày có một bạn học sinh đến và thay đổi lại các viên kẹo ở một số đĩa. Ngày thứ ~j~, bạn học sinh thực hiện việc điều chỉnh như sau: bạn lấy bớt một vài viên kẹo hoặc thêm vào một vài viên kẹo mà bạn mang theo. Các bạn học sinh thống nhất với nhau rằng sau khi thay đổi, tất cả các đĩa từ ~l_j~ đến ~r_j~ đều có cùng số viên kẹo là ~c_j~. Bạn học sinh ~j~ chỉ thay đổi số kẹo trong các đĩa từ ~l_j~ đến ~r_j~, những đĩa còn lại bạn ấy không thay đổi.

Nếu tổng số kẹo hiện có trên các đĩa từ ~l_j~ đến ~r_j~ thừa hoặc thiếu so với số kẹo cần thiết để mỗi đĩa trong đoạn có đúng ~c_j~ viên, thì bạn học sinh sẽ: Lấy đi đúng số kẹo thừa, hoặc bổ sung đúng số kẹo còn thiếu.

Sau mỗi ngày, thầy Kiên muốn biết số lượng kẹo đã thay đổi so với ngày hôm trước sau khi bạn học sinh hôm đó đã lấy đi hay thêm vào. Hãy lập trình giúp thầy Kiên tính toán giá trị trên.

Dữ liệu vào

Đọc từ tệp văn bản XEPKEO.INP gồm:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n,m \le 10^5)~.

• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~l_j, r_j, c_j~ ~(1 \le l_j \le r_j \le n,\ 1 \le c_j \le 10^6)~.

Dữ liệu ra

Ghi ra tệp văn bản XEPKEO.OUT gồm ~m~ dòng.

Dòng thứ ~j~ ghi số lượng kẹo đã thay đổi sau khi bạn học sinh ~j~ thực hiện việc thêm vào hoặc lấy đi so với ngày trước đó.

Ví dụ

Giới hạn

• Subtask 1 (20%): ~n \le 1000,\ m \le 1000~.

• Subtask 2 (20%): ~c_j = c_1~ với mọi j ~(1 \le j \le m)~.

• Subtask 3 (20%): ~n \le 10000,\ m \le 1000~.

• Subtask 4 (20%): Không có ràng buộc gì thêm.