Cân thăng bằng là một loại cân dùng để đo khối lượng của các vật, dựa trên nguyên tắc thăng bằng cơ học. Nó thường có hai đĩa cân đặt ở hai bên. Khi hai vật đặt vào hai bên đĩa cân có khối lượng như nhau thì cân sẽ thăng bằng, đĩa cân sẽ nằm ngang, nếu bên nào có vật nặng hơn thì đĩa cân bên đó sẽ bị nghiêng xuống dưới thấp hơn.

Cho ~N~ quả cân có hình thức giống nhau nhưng trong đó có một quả cân nặng hơn các quả cân còn lại (các quả cân còn lại có khối lượng như nhau). Hỏi cần ít nhất bao nhiêu lần cân để chắc chắn tìm ra được quả cân nặng hơn đó.

Input Specification

• Một dòng chứa số nguyên ~N~ ~(1 \le N \le 10^9)~ là số lượng quả cân.

Output Specification

• Một số tự nhiên là kết quả của bài toán.

Sample Input

5

Sample Output

2

Note

Gọi ~5~ quả cân lần lượt là: ~A, B, C, D, E~.

Có thể chia ~5~ quả cân thành ~3~ nhóm: ~(A, B), (C, D), (E)~.

Lần cân thứ nhất, cho nhóm ~(A, B)~ lên đĩa cân trái, nhóm ~(C, D)~ lên đĩa cân phải. Có ~3~ trường hợp có thể xảy ra:

• Nếu cân thăng bằng thì quả cân cần tìm là ~E~.

• Nếu cân nghiêng về phía nhóm ~(A, B)~ thì nhóm này chứa quả cân cần tìm. Ta thực hiện lần cân thứ hai với mỗi bên đĩa một quả cân sẽ xác định được quả cân cần tìm.

• Trường hợp cân nghiêng về phía nhóm ~(C, D)~, ta làm tương tự như trên

Có một trò chơi Pinball được mô tả như sau:

• Có hai hàng gồm N ô đẩy bóng, hàng trên được đánh số bằng các số lẻ tăng dần, hàng dưới được đánh số bằng các số chẵn tăng dần;
• Bóng bắt đầu vào từ ô số ~1~.
• Bóng được đẩy liên tục theo hình Zic-Zac từ đầu hàng đến cuối và ngược lại như hình sau:

Hỏi sau ~K~ lần đẩy thì bóng đang ở ô số mấy?

Dữ liệu

• Dòng thứ nhất chứa một số tự nhiên ~N~ ~(N~ chẵn, ~4 \le N \le 10^{15})~;
• Dòng thứ hai chứa một số tự nhiên ~K~ ~(1 \le K \le 10^{15})~

Kết quả

• Gồm một số tự nhiên là kết quả của bài toán.

Chấm điểm

• Có 50% số test ứng với 50% số điểm có: ~K < N \le 100~
• 30% số test khác ứng với 30% số điểm có: ~N \le 100, K \le 10^5~
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Sample Input 1

8
4

Sample Output 1

5

Note 1

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5~

Sample Input 2

8
10

Sample Output 2

3

Note 2

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow 5 \rightarrow 6 \rightarrow 3~

Có thể dùng các que diêm để xếp thành các số từ ~0~ đến ~9~ như sau:

Cho một số tự nhiên ~N~ ~(100 ≤ N ≤ 999)~ mà các chữ số của nó được xếp bởi các que diêm theo cách như trên. Vẫn với số que diêm như vậy thì có thể xếp thành số nhỏ nhất và số lớn nhất có ba chữ số là số nào?

Chú ý: kết quả tạo thành không có số ~0~ ở đầu.

Dữ liệu

• Một dòng chứa một số tự nhiên ~N~ ~(100 ≤ N ≤ 999)~ là số ban đầu.

Kết quả

• Dòng thứ nhất là số bé nhất tìm được;
• Dòng thứ hai là số lớn nhất tìm được.

Sample Input 2

123

Sample Output 2

104
971

Note

• Số lượng các que diêm đều là ~12~.

Cho hình tam giác số gồm ~N~ dòng, dòng thứ ~i~ ~(1 ≤ i ≤ N)~ gồm ~i~ ô vuông. Mỗi ô vuông chứa một giá trị là số thứ tự của ô đó theo thứ tự từ trên xuống dưới, từ trái sang phải. Tam giác được chia thành các vòng từ ngoài vào trong như hình dưới đây:

Hình trên mô tả tam giác số với ~N = 10~ có ~4~ vòng:

• Vòng 1 màu vàng.
• Vòng 2 màu xanh.
• Vòng 3 màu cam.
• Vòng 4 màu trắng.

Hãy tính tổng các giá trị trong ô vuông của vòng thứ ~K~ của tam giác.

Dữ liệu

• Dòng đầu tiên chứa số tự nhiên ~N~ ~(1 ≤ N ≤ 10^5)~ là số dòng của tam giác số;
• Dòng thứ hai chứa số tự nhiên ~K~ ~(1 ≤ K≤ (N+2)/3)~.

Kết quả

• Gồm một số tự nhiên là kết quả của bài toán.

Chấm điểm

• Có 20% số test ứng với 20% số điểm có: ~K = 1 ; N \le 5~;
• 20% số test khác ứng với 20% số điểm có: ~K = 1; N \le 100~
• 30% số test khác ứng với 30% số điểm có: ~N \le 100~
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Sample Input 1

8
2

Sample Output 1

20

Note 1

~5 + 8 + 12 + 17 + 23 + 24 + 25 + 26 + 27 + 20 + 14 + 9 = 210~

Sample Input 2

5
1

Sample Output 2

98

Note 2

~1 + 2 + 4 + 7 + 11 + 12 + 13 + 14 + 15 + 10 + 6 + 3 = 98~

Cho một số tự nhiên ~S~ và một số tự nhiên ~K~. Hãy thay đổi tối đa ~K~ chữ số của ~S~ để tạo ra một số tự nhiên ~X~ ~(X > 0)~ nhỏ nhất chia hết cho ~3~ (không có số ~0~ ở đầu).

Dữ liệu

• Dòng đầu tiên chứa một số tự nhiên ~S~ có không quá ~15~ chữ số;
• Dòng thứ hai chứa một số tự nhiên ~K~ ~(1 \le K ≤ 15)~.

Kết quả

• Một số tự nhiên là số ~X~ mới thoả mãn yêu cầu đề bài.

Chấm điểm

• Có 40% số test ứng với 40% số điểm có: ~K = 1~;
• 30% số test khác ứng với 30% số điểm có: ~S ≤ 10^5~;
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Sample Input

2024
1

Sample Output

2004