The linked list program we wrote during the lecture did not use a header file for the class specification. Make sure your implementation uses a header file called mylinkedlist.h. Once you have the specification file, need a file called mylinkedlist.cpp and implement functions that you have included in the header file. You need to implement only those functions that are needed to accomplish the following task:

Given a key (or data) to be inserted into the linked list of size N. The task is to insert the element at head or tail of the linked list depending on the input just before it p. If p is 0, then insert the element at beginning else insert at end.

Hint : When inserting at the end, make sure that you handle NULL explicitly.

Input Format:

You will use a file called input.txt. First line of input contains number of testcases T. For each testcase, first line of input contains length of linked list N and next line contains 2*N integers, each element to be inserted into the list is preceded by a 0 or 1 which decide the place to be inserted.

Output Format:

For each testcase, there will be a single line of output which contains the linked list elements.

Constraints:

1 <= T <= 100

1 <= N <= 10³

Example:

Input:

3

5

9 0 5 1 6 1 2 0 5 0

3

5 1 6 1 91

4

15 0 36 0 95 0 14 0

Output:

5 2 9 5 6

5 6 9

14 95 36 15

Explanation:

Testcase 1: After inserting the elements at required position, we have linked list as 5, 2, 9, 5, 6.