Description

After catching Jerryfish, Spongebob and Patrick thought they were happy enough so they went home. And then they found that Squidward had come home already :)

Squidward told them he need to drum up a marching band fast(for some reason). So he needed their help. Hence Spongebob and Patrick joined Squidward's band.

Today is their practicing day. Squidward is teaching all the members how to move at a performance. At a performance there are N rows. And in the i-th row, there are sz_i people. Note row may be empty(i.e. sz_i = 0). Everyone plays exactly one musical instrument. The musical instrument played by the j-th people in the i-th row is represented by a lower case letter c_ij.

Squidward ask them to move Q times. In each move, there are three types of moving:

1. all the people in the a_i-th row move to the front of the b_i-th row (without messing up the original order)
2. all the people in the a_i-th row move to the back of the b_i-th row (without messing up the original order)
3. exchange all the people in the a_i-th row and the b_i-th row (without messing up the original order)

Now it’s your turn! You need to help them to move and tell Squidward the final formation in the end.

Input

The first line contains one integer N (1 ≤ N ≤ 10⁵) – the number of rows.

Then N lines follow. First the i+1-th line contains one integer sz_i – the number of people in the i-th row. If there are some people in the row, a space character and sz_i characters c_ij are followed where c_ij is the musical instrument played by the j-th people in the i-th row. The sum of all the sz_i is less than or equal to 10⁶.

The N+2-th line contains one integer Q (1 ≤ Q ≤ 10⁵) – the times they need to move.

Then Q lines follow. The i+N+3-th line contains three integer type_i, a_i, b_i (1 ≤ type_i ≤ 3, 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i) – the type of moving and the numbers of two rows which need to move.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample below
• For the first five testcases: 1 ≤ N, Q ≤ 10³, the sum of all the sz_i ≤ 10⁴

Hint:

If you have no idea how to implement, please take it as your reference.

#include <stdlib.h>
#include <stdio.h>
typedef struct _Node {
    char val;
    struct _Node* next;
} Node;
 
//list[i]'s head node
Node *head[100005] = {};
 
//list[i]'s tail node
Node *tail[100005] = {};
 
void swap(int a, int b) {
    //swap list[a] and list[b]
    Node *tmp = (Node *)malloc(sizeof(Node));
 
    /* swap(head_node)
    tmp = head[a];
    head[a] = head[b];
    head[b] = tmp;
    */
 
    /* swap(tail_node)
 
    */
}
void append(int a, int b) {
    //append list[a] to list[b]'s behind
    if(head[a] == NULL) return;
    if(head[b] == NULL) {
        swap(a, b);
        return;
    }
    /*
    tail[b]->next = head[a];
    tail[b] = ...
    ...
    */
}

Output

After all the moving, for each row output all the musical instrument played in that row and then print a newline('\n') character.

If there is no people in some row, just output an empty line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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 deletion operations.
For each operation, you need to delete the first node with value V equal to A in the list. If no such node 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.
If the linked list is empty, output "EMPTY!!!"

Example Operation 1:

Delete a node with value 2.

Delete a node with value 5.

Example Operation 2:

Delete a node with value 5.

Other Example Operation:

This question is a partial judge.
Please implement functions defined in the header file.

• getCycleEnd: returns the end node of the cycle, that is, the node whose next node is the start node of the cycle in Tortoise and Hare algorithm, in the linked list (if there is no cycle in the linked list, returns NULL)
• deleteNode: gets an input T and perform T deletion operations

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 V_i , 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 one integers A, indicating to delete the first node with value V equal to A.

Constraints

• 1 ≤ N ≤ 10⁶
• 0 ≤ M ≤ N
• 1 ≤ T ≤ 100
• -10⁹ ≤ A, V ≤ 10⁹

^​Subtasks

• Testcases 1 ~ 5: 0 ≤ V ≤ 10⁶, V is unique, M = 0
• Testcases 6 ~ 8: 0 ≤ V ≤ 10⁶, V is unique
• Testcases 9 ~ 10: No additional restrictions

Output

After completing all operations, output each node's value in the linked list once, starting from the head.
If the linked list is empty, output "EMPTY!!!"

 

Please remember to print "\n" at the end.

 

^​Hint

You should use the Tortoise and Hare algorithm to pass testcases 6~10.

To complete this problem, the following cases should be taken care of:

• Case 1: delete the first node (head) of the linked list.
• Case 2: delete the first node and nodes at the start of the cycle.
• Case 3: delete the first node and nodes at the end of the cycle.
• Case 4: delete the first node, cycle start/end node, and self-loop node.

To check if you've handled these cases properly, testcases 6~10 are designed in following rules:

• Testcase 6: no cases above will occur.
• Testcase 7: Case 1 will occur.
• Testcase 8: Case 1~3 will occur.
• Testcase 9 and Testcase 10: Case 1~4 will occur.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14580.c

Partial Judge Header

14580.h

Tags

Discuss