Question

Implement a singly linked list having all unique elements with the following operations.
I 0 x – Inserts element x at the end.
I 1 y x – If the element y exists, then insert element x after the element y, else insert element y before the existing element x. Assuming either the element x or the element y exists.
I 2 z y x – Inserts element x in the middle of the elements z and y. The element z appears before the element y.
U x p – Links the next pointer of the element x to the node lying at the pth position from the element x while traversing towards right. In case of insufficient number of nodes, the counting continues by updating the existing linked list to its circular version.
Input:
Line 1 contains an integer N indicating the total number of operations.
Each of the following N lines contains an operation to be performed in the format as is described above.
Output:
Line 1 has 1 if the linked list gets updated to its circular version, else 0.
Line 2 has a count of the number of nodes whose addresses are contained in the next pointer of multiple nodes. If output at Line 2 is zero then output Line 4 will not be printed.
Line 3 has space separated contents of all the nodes which are counted to get the output at Line 2 in increasing order. If output at Line 2 is zero then output Line 3 will have space separated contents of the generated linked list.
Line 4 has space separated respective frequencies of each output value, say x, at Line 3. 'Frequency of each output value x' means the count of multiple nodes whose next pointers have address of a node with this value x.
Constraints
All integers range in between 1 and 1000.
Sample Input I:
3
I 0 1
I 1 1 7
I 2 1 7 3
Sample Output I:
0
0
1 3 7
EXPLANATION I:
Linked list after execution of each of the three operations given in the input is shown below.

1

1 - > 7

1 - > 3 - > 7

Sample Input II:
10
I 0 1
I 0 7
I 1 6 7
I 1 1 2
I 2 1 7 3
I 2 3 6 5
I 2 1 7 4
U 2 3
U 2 2
U 1 6
Sample Output II:
1
1
6
3
EXPLANATION II:
Linked list after execution of each of the ten operations given in the input is shown below.


​

Answer 1

Answer:

1

1

3

6

Explanation:

Linked list after execution of each of the ten operations given in the input is shown below.