Một nhóm gồm ~N~ học sinh thực hiện trò chơi loại người ra khỏi vòng tròn. Luật chơi như sau: ~N~ học sinh xếp thành vòng tròn, đánh số thứ tự từ ~1~ đến ~N~. Bắt đầu từ học sinh thứ tự ~1~, các học sinh lần lượt đếm từ ~1~ đến ~M~ tính theo chiều kim đồng hồ, học sinh thứ ~M~ bị loại ra khỏi vòng tròn. Khi một học sinh bị loại khỏi vòng tròn, thì vòng tròn thu hẹp lại và bắt đầu từ học sinh còn lại bên trái học sinh bị loại đếm lại từ ~1~ đến ~M~ để xác định học sinh bị loại tiếp theo, cứ như vậy cho đến khi nào trên vòng tròn chỉ còn một học sinh.

Yêu cầu

Cho trước ~N, M~, hãy chỉ ra số thứ tự (ban đầu, khi chưa loại học sinh nào) của học sinh còn lại cuối cùng trên vòng tròn.

Dữ liệu đầu vào

Gồm hai số ~N, M~ ~(2 \le N, M \le 10^3)~ cách nhau khoảng trắng.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số thứ tự của học sinh còn lại trên vòng tròn.

Ví dụ

Ví dụ 1

INPUT

8 3

OUTPUT

7

Cho một mảng ~A~ gồm ~N~ số nguyên dương: ~a_1, a_2, ..., a_N~.

Yêu cầu

Hãy tìm hai số nguyên trong mảng ~A~ sao cho ước chung lớn nhất của hai số đó là lớn nhất.

Dữ liệu đầu vào

Gồm hai hoặc nhiều dòng:

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \times N \le 2 \times 10^3)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 10^6)~, các số cách nhau khoảng trắng hoặc xuống hàng.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là ước chung lớn nhất tìm được.

Ví dụ

Ví dụ 1

INPUT

6
12 5 6 4 7 10

OUTPUT

6

Một xâu (xâu nguồn) chỉ gồm các chữ cái (kí tự) hoa A, B, C, ..., Z có thể được viết gọn (xâu thu gọn) theo các quy tắc sau:

1. ~Xm~ - gồm ~m~ chữ cái ~X~ (~m~ là một số tự nhiên);
2. ~(C)m~ - gồm ~m~ lần viết xâu thu gọn ~C~.

Nếu ~m = 0~ thì xâu ~C~ trong ngoặc sẽ được bỏ qua, nếu ~m = 1~ thì có thể không cần viết ~m~ (trong xâu thu gọn).

Ví dụ: xâu (AB3 (C2D)2 (C5D)0)2A3 hoặc (AB3 (C2D)2)2A3 là xâu thu gọn của xâu nguồn: ABBBCCDCCDABBBCCDCCDAAA.

Ghi chú: xét xâu: (C5D)0, ta có: ~m = 0~ nên (C5D) được bỏ qua.

Yêu cầu

Cho xâu thu gọn ~S~. Hãy viết dạng đầy đủ xâu nguồn (còn gọi là dạng khai triển) của xâu thu gọn ~S~. Trong xâu thu gọn có thể chứa các dấu cách nhưng các dấu cách này được coi là vô nghĩa và do đó không xuất hiện trong xâu nguồn.

Dữ liệu đầu vào

Gồm xâu thu gọn ~S~ (dài không quá ~200~ kí tự).

Dữ liệu đầu ra

Gồm một dòng duy nhất ghi xâu nguồn.

Ví dụ

Ví dụ 1

INPUT

(AB3 (C2D)2 (C5D)0)2A3

OUTPUT

ABBBCCDCCDABBBCCDCCDAAA