Cho một dãy ~A~ gồm ~n~ số nguyên ~a_{1}, a_{2}, a_{3}, ... a_{n}~ và hai số nguyên ~v, T~. Hãy tìm cách thêm số ~T~ vào vị trí ~v~ trong dãy ~A~ (các số ban đầu vẫn giữ nguyên thứ tự).

Input

Dòng thứ nhất gồm ba số nguyên ~n, v, T~ (~1 \leq n, 1 \leq v \leq n + 1 \leq 10^5 + 1, |T| \leq 10^5~).

Dòng tiếp theo gồm ~n~ số nguyên ~a_{1}, a_{2}, a_{3},..., a_{n}~ (~|a_{i}| \leq 10^5~).

Output

In ra dãy ~n + 1~ số (các số cách nhau một khoảng trắng) sau khi thêm số ~T~ vào vị trí ~v~.

Sample Test

Input:

5 2 9
8 6 2 10 5

Output:

8 9 6 2 10 5