Cho mảng A gồm các phần tử nguyên độ dài n và q truy vấn dưới dạng i x , chèn giá trị x vào vị trí i của mảng A . In ra mảng A sau mỗi truy vấn.

Input

• Dòng đầu tiên gồm 2 số nguyên n , q .

• Dòng tiếp theo gồm n số nguyên A i . q dòng tiếp theo, mỗi dòng gồm 2 số nguyên i x , là một truy vấn.

Output

q dòng, dòng thứ i là mảng A sau truy vấn i .

Điều kiện

1 ≤ n , q ≤ 100 . | A i | , | x | ≤ 100 .

Ví dụ

Input:

3 3
1 2 3
1 0
5 5
5 4

Output:

0 1 2 3
0 1 2 3 5
0 1 2 3 4 5