Description
Given a linked list of length N, where the last node points to the M-th node in the list. Note that when M equals 0, it indicates that the last node points to NULL.
Your task is to get an input T and perform T insertion operations.
For each operation, you need to find the first node with value A (where V = A) in the list and insert a new node with value B after it. If no node with value A is found in the list, skip this operation.
After completing all operations, output each node's value in the linked list once, starting from the head.
Example Operation 1:
Insert a node with value 2 after the node with value 1.
Example Operation 2:
Insert a node with value 6 after the node with value 5.
Other Example Operation:
This question is a partial judge.
Please implement functions defined in the header file.
- insertNode: get an input T and perform T insertion operations
- printLinkedList: output each node's value in the linked list once, starting from the head
Input
The first line contains two integers N and M, where N represents the length of the linked list, and the last node in the linked list points to the M-th node.
The second line contains N integers Vi , representing the value of the i-th node.
The third line contains one integer T, representing T insertion operations to be performed.
The following T lines each contain two integers A and B, indicating to insert a node with value B after the first node with value V equal to A.
Constraints
- 1 ≤ N ≤ 106
- 0 ≤ M ≤ N
- 1 ≤ T ≤ 100
- -109 ≤ A, B, V ≤ 109
Subtasks
- Testcases 1 ~ 3: 0 ≤ V ≤ 106, V is unique, M = 0
- Testcases 4 ~ 6: 0 ≤ V ≤ 106, V is unique
- Testcases 7 ~ 8: No additional restrictions
Output
After completing T operations, output each node's value in the linked list once, starting from the head.
Please remember to print "\n" at the end.