CaiWinDao và cuom1999 rủ nhau ôn luyện lại ngữ pháp tiếng Anh sau nhiều ngày buồn chán vì không được ra khỏi nhà. CaiWinDao tìm được ở trên internet một bài tập lựa chọn mạo từ không xác định (a, an) tương ứng với các danh từ số ít cho trước và hai bạn nhanh chóng giải được những câu đầu tiên trong bài. Tuy nhiên, số lượng câu hỏi trong bài quá lớn mà quy tắc xác định lại quá đơn giản nên cả hai nhanh chóng đâm ra buồn chán. CaiWinDao và cuom1999 quyết định nhờ hai bạn xác định nốt các mạo từ còn lại trong bài theo quy tắc thông thường: Điền mạo từ an nếu theo sau nó là danh từ bắt đầu bằng các nguyên âm a, e, i, o, u và điền mạo từ a trong các trường hợp còn lại. Các bạn hãy giúp CaiWinDao và cuom1999 nhé!

Yêu cầu: Cho trước một danh từ số ít đếm được ở dạng một xâu ký tự latin in thường, hãy tìm mạo từ không xác định đứng trước nó.

Input

• Một xâu ký tự chỉ chứa các chữ cái latin in thường.

Output

• Ghi ra mạo từ tương ứng với danh từ trong input ở dạng một xâu ký tự latin in thường.

• Dữ liệu đảm bảo không tồn tại các ngoại lệ do cách phát âm của âm đầu như an hour hay a uniform.

Example

orange

an

banana

a

ami đang đi vượt ải Codeforces. Để trở thành master, ami phải vượt qua \(n\) con quái vật. Con quái vật thứ \(i\) sẽ làm ami hao tổn \(a_i\) công lực. Và vì các ải này diễn ra liên tiếp, ami không có thời gian để hồi phục công lực. ami sẽ gục ngã nếu sau một trận chiến, công lực còn lại bé hơn hoặc bằng \(0\).

Ví dụ: nếu ban đầu ami có \(10\) công lực, và con quái vật đầu tiên có sức mạnh \(a_1 = 4\), ami sẽ vượt ải thành công và còn \(6\) công lực. Nếu con quái vật thứ hai có sức mạnh ít nhất là \(6\), ami sẽ bị đánh gục ở ải này.

ami đã nghiên cứu rất kỹ về đối thủ của mình. Anh biết rằng sức mạnh của chúng tương ứng là \(a_1, a_2, ..., a_n\). Và để thêm phần kỹ càng, ami sẽ mang theo một bộ giáp có thể chống được \(k\) sát thương. Nói cách khác, nếu ami sử dụng bộ giáp này khi đấu với quái vật thứ \(i\) thì chỉ mất đi \(max(0, a_i - k)\) công lực. Tuy nhiên, bộ giáp này chỉ sử dụng được cho \(1\) ải duy nhất và ami phải tính toán sử dụng sao cho tối ưu.

ami muốn vượt qua cả \(n\) ải này. Hỏi ban đầu anh phải chuẩn bị ít nhất bao nhiêu công lực? Biết rằng ami rất bá đạo nên sẽ sử dụng giáp một cách tối ưu.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, k \ (k \leq 10^9)\) tương ứng là số quái vật và sức mạnh của giáp.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\) là sức mạnh của \(n\) con quái vật.

Output

• In ra một số nguyên là công lực ít nhất ami cần chuẩn bị trước khi vượt ải.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10^5\).

Example

5 5
1 2 6 7 3

15

5 3 
1 1 1 1 1

5

Vì đang trong thời gian cách ly xã hội, CaiWinDao không thể đến nhà các em gái chơi. Anh đành ở nhà chơi với một người bạn mới là con Bot do chính mình sáng chế. Mỗi ngày, con Bot sẽ gợi ý CaiWinDao một trò chơi và hai "người" sẽ chơi với nhau xem ai thắng. Hôm nay, con Bot đưa cho CaiWinDao \(n\) que diêm. Nhiệm vụ của anh là phải tạo thành một hình chữ nhật rỗng bằng các que diêm đã cho sao cho diện tích hình chữ nhật tạo được là lớn nhất có thể. Lưu ý rằng, CaiWinDao không cần xài hết \(n\) que diêm.

Input

• Gồm một dòng chứa số que diêm, \(n \ (n > 0)\).

Output

• Gồm một số nguyên là diện tích lớn nhất có thể tạo thành.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^9\).

Example

4

1

17

16

3

0

ami không thích ước chung lớn nhất. Do đó, ami sẽ cần các bạn tìm ước chung lớn nhất giúp ami. Cho một dãy \(n\) số nguyên dương. Hãy tính ước chung lớn nhất của \(n\) số này.

"Dễ quá" - các bạn thầm nghĩ. Vậy nên ami muốn các bạn bỏ đi đúng 1 số để ước chung lớn nhất của các số còn lại là lớn nhất.

"Vẫn quá dễ" - các bạn cười thầm. Vì thế, hãy bỏ đi \(k\) số để ước chung lớn nhất của các số còn lại là lớn nhất nhé.

Input

• Dòng đầu chứa 2 số nguyên \(n\) và \(k\).

• Dòng tiếp theo chứa n số nguyên dương \(a_1\), \(a_2\), ..., \(a_n \ (1 \leq a_i \leq 3 \times 10^6)\).

Output

• In ra \(1\) dòng là ước chung lớn nhất của dãy số sau khi đã bỏ đi đúng k số.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 10\), và \(k = 0\).

• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq n \leq 10^5\), và \(k = 1\).

• Subtask \(3\) (\(30\%\) số điểm): \(0 \leq k < n \leq 3*10^5\), và \(1 \leq a_i \leq 10^5\).

• Subtask \(4\) (\(30\%\) số điểm): \(0 \leq k < n \leq 3*10^5\), và \(1 \leq a_i \leq 3*10^6\).

Example

3 1
1 2 2 

2

Hàm \(F(a)\) với a là một dãy số nguyên \(n \geq 1\) phần tử \(a_1\), \(a_2\), \(a_3\), ... \(a_n\) được định nghĩa thông qua đoạn code sau :

    F(a) = 0;
    Duyệt i từ 2 đến n
    {
       k = 0;
       Duyệt e từ 1 đến i-1
       {
           Nếu a[e] < a[i] thì
           {
               k = k + 1;
           }
       }
       F(a) = F(a) + k * a[i];
    }

cuom1999 thích những thứ nhỏ bé (ví dụ như Small), do đó cuom1999 muốn ami tính hàm F với tất cả các dãy số tự nhiên có độ dài bằng 2. Quá dễ, đáp án luôn là +∞. Còn ami thích những ghứ vĩ đại, do đó ami muốn các bạn tính tổng tất cả các hàm F(a) với a là một hoán vị n phần tử. Vì kết quả có thể lớn, các bạn cần in ra đáp số chia dư 1000000007.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(q\) là số câu hỏi.
• \(q\) tiếp theo, mỗi dòng dòng chứa 1 số nguyên dương \(n\).

Output

• In ra \(q\) dòng, mỗi dòng ứng với một câu hỏi.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 10\), \(q\) = 1.

• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq n \leq 100\), \(q\) = 1.

• Subtask \(3\) (\(60\%\) số điểm): \(1 \leq n \leq 10^6\), \(1 \leq q \leq 10^6\).

Example

4
1
2
3
4

0
2
24
240

Có \(n\) con kiến trên một sợi dây. Chúng được đánh số thứ tự từ \(1\) đến \(n\). Quy ước tọa độ của sợi dây là một trục \(Ox\) với hai đầu mút là \(-10^9\) và \(10^9\). Ban đầu các con kiến đứng tại tọa độ \(a_1, a_2, ..., a_n\). Mỗi giây, mỗi con kiến có thể bò sang trái \(1\) đơn vị, sang phải \(1\) đơn vị, hoặc đứng yên. Nói cách khác, sau mỗi giây, \(a_i=a_i + 1, a_i - 1\) hoặc \(a_i\).

Kiến Vua rất không hài lòng vì thứ tự các con kiến đứng rất lộn xộn, vì vậy ông muốn chúng di chuyển về lại trật tự để dễ quản lý. Ông muốn con kiến thứ nhất đứng bên trái con thứ hai, con thứ hai đứng bên trái con thứ ba, ... Hay nói cách khác, \(a_1 < a_2 < ... < a_n\).

Hỏi cần ít nhất bao nhiêu giây để các con kiến tạo thành trật tự như nhà vua mong muốn nếu chúng di chuyển một cách tối ưu? Biết rằng nhà vua chỉ kiểm tra trật tự tại các thời điểm là số nguyên. Giả sử sợi dây đủ rộng để các con kiến không bị rơi xuống đất khi gặp nhau.

Input

• Dòng đầu chứ một số nguyên dương \(n\) là số lượng kiến trên dây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n \ (-10^8 \leq a_i \leq 10^8)\) là tọa độ ban đầu của các con kiến.

Output

• Dòng đầu in ra một số nguyên dương là thời gian ít nhất để các con kiến di chuyển và tạo thành trật tự nhà vua mong muốn.

• Dòng thứ hai in ra \(n\) số nguyên \(b_1, b_2, ..., b_n \ (-10^9 \leq b_i \leq 10^9)\) là tọa độ của các con kiến sau khi di chuyển xong.

• Lưu ý:

• Nếu in đúng đáp án dòng 1, bạn sẽ được \(50\%\) số điểm của test tương ứng.
• Nếu có nhiều phương án cho dòng 2, bạn chỉ cần in một đáp án bất kỳ

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 3000\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \leq 3 \times 10^5\).

Example

3
3 2 1

2
1 2 3

4
1 2 3 4

0
1 2 3 4