Bé Bo đang học về tính lẻ chẵn. Hôm nay, cô giáo dạy Toán cho Bo bài toán như sau: Cho hai số nguyên dương x, y. Dãy số ~A~ được xây dựng theo quy tắc:

• ~A_1 = x~

• ~A_2 = y~

• ~A_i~ = (~A_{i - 1} + A_{i - 2}~)%~k~ nếu ~i ≥ 3~ và ~i~ chỉ số chẵn

• ~Ai~ = |~A_{i - 1} - A_{i - 2}~|% ~k~ nếu ~i ≥ 3~ và ~i~ là chỉ số lẻ

Trong đó ~k = 10^9 + 7~ và % là phép chia lấy phần dư, |~A_{i - 1} - A_{i - 2}~| là giá trị tuyệt đối của ~A_{i - 1}~ - A_{i - 2}~

Ví dụ: với ~x~ = 5, ~y~ = 7 thì một vài phần tử đầu tiên của dãy số ~A~ là: 5, 7, 2, 9, 7, 16, 9, 25, 16, 41…

Yêu cầu: Cho trước số nguyên dương ~n~, hãy tính An.

Input

Gồm một dòng chứa ba số nguyên dương lần lượt là x, y, n, giữa các số cách nhau bởi một dấu cách. (~1 ≤ x, y ≤ 10^9~, ~3 ≤ n ≤ 10^6~)

Output

• Một số nguyên là giá trị của An.

Example

Input

5 7 8

Output

25

Bác nông dân John có một khu đất trồng rau hình chữ nhật kích thước mxn, gồm m hàng, mỗi hàng gồm ~n~ ô vuông độ dài cạnh là 1. Bác John cần làm hàng rào để ngăn cách từng ô vuông riêng biệt. Đường biển xung quanh khu đất cũng cần được rào lại.

Yêu cầu: Em hãy giúp bác John tính tổng độ dài cần rào là bao nhiêu?

Input

• Gồm một dòng chứa hai số nguyên dương lần lượt là ~m~ và ~n~, giữa ~m~ và ~n~ được cách nhau bởi dấu cách (~1≤m,n≤10^9~).

Output

• Một số nguyên dương là tổng độ dài cần rào.

Examples

Input1

2 3

Output1

17

Input2

5 3

Output2

38

Để làm quen với bài tập lập trình về kí tự, thầy giáo giao cho các bạn làm bài tập sau: Cho một dãy kí tự là các chữ cái Latinh in hoa. Hãy in ra các kí tự có số lần xuất hiện không nhỏ hơn ~k~ trong dãy trên theo thứ tự từ điển.

Yêu cầu: Hãy lập trình giải bài toán trên.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ cách nhau một khoảng trắng, trong đó ~n~ là số lượng kí tự của dãy và ~k~ là số lần xuất hiện cần phải đếm. (~1 ≤ k ≤ n ≤ 10^6~)
• Dòng thứ 2 chứa n kí tự là chữ cái Latinh in hoa viết liền nhau.

Output

• Gồm một dãy các kí tự có số lần xuất hiện không nhỏ hơn ~k~ và được sắp xếp theo thứ tự từ điển. Trường hợp không có kí tự nào thỏa mãn thì ghi một số 0.

Scoring

• Có 20% số test tương ứng 20% số điểm với (~1 ≤ k ≤ n < 10^2~)
• Có 40% số test tương ứng 40% số điểm với (~10^2 ≤ k ≤ n < 10^4~)
• Có 40% số test tương ứng 40% số điểm với (~10^4 ≤ k ≤ n ≤ 10^6~)

Example

Input

10 3
CABADDABDD

Output

AD

Ta định nghĩa các kí tự in thường (~'a'…'z'~) và in hoa (~'A'…'Z'~) được sắp xếp theo đúng thứ tự cho trong bảng chữ cái gọi là sắp xếp tăng dần, còn sắp xếp theo chiều ngược lại được gọi là sắp xếp giảm dần.

Cho một xâu ~S~ chỉ gồm các ký tự in thường (~'a'…'z'~) và in hoa (~'A'…'Z'~).

Yêu cầu: Sắp xếp xâu ~S~ theo thứ tự: Các kí tự in hoa giảm dần rồi đến các kí tự in thường giảm dần.

Input

• Gồm một dòng duy nhất chứa xâu ~S~ (~|S| ≤ 10^5~).

Output

• Xâu ~S~ sau khi được sắp xếp theo yêu cầu đề bài.

Scoring

• Có 50% số điểm ứng với các test có ~|S| ≤ 1000~.
• Có 50% số điểm ứng với các test có ~|S| ≤ 10^5~.

Example

Input

aBAbDAbaC

Output

DCBAAbbaa