CBE1 - CSES 1

Xét thuật toán sau nhận đầu vào là một số nguyên dương \(n\). Nếu \(n\) chẵn, thuật toán sẽ chia nó cho hai, và nếu \(n\) lẻ, thuật toán nhân ba nó lên rồi cộng thêm một đơn vị. Thuật toán trên lặp lại điều này cho tới khi \(n\) bằng \(1\). Ví dụ, dãy số thực hiện với \(n=3\) là:

Việc của bạn là hãy mô phỏng lại cách hoạt động của thuật toán với một giá trị \(n\) cho trước.

Input

• Một dòng duy nhất chứa số \(n\)
• \(1 \leq n \leq 10^6\)

Output

• In ra một dòng lần lượt chứa từng giá trị của \(n\) trong khi chạy thuật toán

Example

3

3 10 5 16 8 4 2 1

Bạn nhận được tất cả các số từ \(1\) đến \(n\) trừ một số. Nhiệm vụ của bạn là tìm số bị thiếu đó.

Input

• Dòng đầu tiên chứa một số nguyên \(n\)
• Dòng thứ hai chứa \(n-1\) số. Các số khác nhau đôi một và mỗi số có giá trị từ \(1\) đến \(n\)

Constraints

• \(2 \leq n \leq 2\cdot 10^5\)

Output

• In ra số còn thiếu

Example

5
2 3 1 5

4

Bạn có một dãy ADN: một xâu kí tự chỉ gồm các chữ cái A, T, G, C. Hãy tìm đoạn ADN con dài nhất chỉ gồm các kí tự giống nhau.

Input

• Một dòng duy nhất chứa xâu \(s\)
• Độ dài xâu \(s\) thỏa mãn: \(1 \leq n \leq 10^6\)

Output

• In ra độ dài của đoạn ADN con dài nhất tìm được.

Example

ATTCGGGA

3