Given a Linked List, an integer k and an element, add that element at the kth position of the linked list.

Example

List: 1→3→4→7
k: 2
Element: 5
Result: 1→5→3→4→7

Testing

Input Format

The first line contains ‘T’ denoting the number of independent test cases.

For each test case the input has three lines:

• A number ‘n’, denoting the length of the linked list.
• n space-separated integers denoting elements of the linked list.
• k and val denoting the position and the new element value

Output Format

For each test case, the output has one line with space-separated integers.

Sample Input

2
4
1 3 4 7
2 5
3
4 5 6
1 1

Expected Output

1 5 3 4 7
1 4 5 6

Constraints

1 <= T <= 100

1 <= n <= 1000

1 <= k <= n

1 <= element <= 1000