Description

This is a partial judge problem OwO

Finally, Spongebob and Patrick have successfully escaped from the police capture. So it’s unnecessary for Patrick to cosplay as an usagi, aka Pekotrick. (To know what happened before, you can refer to 12885 - Pekotrick and Spongebob run away.)

In order to enjoy their life of leisure, they decided to go catch some jellyfish for fun. But due to their poor reading ability, they eventually go to the "Suicune" Field ????? ("Suicune" is also known as 水君 in Chinese.)

After arriving the Suicune Field, they observed that some Suicune would form a circle. And they always move regularly: two groups of consecutive Suicune would exchange their position without messing up the order inside a group.

Now you need to help Spongebob and Patrick record the information of Suicune circle. Formally there are N Suicune. For convenience, we always number all the Suicune from 1 to N in clockwise order. In the beginning, we know the Combat Power of the i-th Suicune is v_i.
Then there are Q events. In the i-th event, two groups of consecutive Suicune would exchange their position. And the number of Suicune of these two groups is len_i. One group is the len_i consecutive Suicune which start from the a_i-th Suicune(in clockwise order). Another group is the len_i consecutive Suicune which start from the b_i-th Suicune(in clockwise order). They will exchange their position simultaneously. Note we always number all the Suicune from 1 to N in clockwise order. So after one event, you may need to re-number all the Suicune.

And sometimes there may be a Suicune which is in the two groups simultaneously in some events. For this situation, we just ignore all the this kind of events(i.e Suicune would not exchange their position in those strange events).

In the end, tell Spongebob and Patrick the Combat Power of all the Suicune (in clockwise order).

Sample #2 Explanation

Let's take Sample #2 as an example. In Sample #2, N = 5 and Q = 1.

The first event: the 1st, the 2nd and the 3rd Suicune exchange their postion with the 2nd, the 3rd and the 4th Suicune. But the 2nd Suicune (or the 3rd Suicune ) is in the two groups simultaneously. So we just ignore this event(i.e the two groups don't exchange their position).

Finally the Combat Power of all the Suicune are still the same : 4 8 7 6 3.

Partial Code

Let's solve this problem with a circular linked list.

main.c

#include <stdio.h>
#include "function.h"
#define MAXN 100005
int arr[MAXN];
int main() {
    int N;
    scanf("%d", &N);
    for(int i=1;i<=N;i++)
        scanf("%d", &arr[i]);

    Node *head = NULL;
    createLinkedList(&head, N, arr);

    int Q;
    scanf("%d", &Q);
    for(int i=1;i<=Q;i++) {
        int a,b,len;
        scanf("%d %d %d", &a, &b, &len);
        swapTwoSegment(&head, N, a, b, len);
    }

    for(int i=1;i<=N;i++) {
        if(i > 1)    printf(" ");
        printf("%d", head->val);
        head = head->next;
    }
    printf("\n");
    return 0;
}

function.h

typedef struct node {
    struct node* next;
    int val;
} Node;
void createLinkedList(Node **head, int N, int *arr);
void swapTwoSegment(Node **head, int N, int a, int b, int len);

You need to implement the two functions: createLinkedList and swapTwoSegment.

Input

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

The second line contains N integers v₁, v₂, ..., v_N (1 ≤ v_i ≤ N) – the Combat Power of each Suicune.

The third line contains one integer Q (1 ≤ Q ≤ 100) – the number of events.

Then Q lines follow. The i+3-th line contains three integer a_i, b_i and len_i (1 ≤ a_i, b_i ≤ N, 1 ≤ 2 x len_i ≤ N) – the number of the starting Suicune of two groups and the number of Suicune in these two groups.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample #1 below
• For the first six testcases: there must not be such a Suicune which is in the two groups simultaneously in each event.

Output

After all the events output the Combat Power of all the Suicune(in clockwise order).

 

Note: there are two sample below. "# Sample Input 1/2" and "# Sample Output 1/2" are not the part of input and output.

They are just for marking that the following content corresponds to which sample.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13135.c

Partial Judge Header

13135.h

Tags

Discuss

Description

After catching Suicune, 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 four 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)
4. reverse the order of all the people in the a_i-th row

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

 

Hint for reverse:

1. Easy way , but you can only get 2 more correct answers.

But, you should think another way to accelerate your performance to get AC.

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 two integer type_i, a_i. If type_i isn't equal to 4, then a integer b_i follows(1 ≤ type_i ≤ 4, 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i) – they are the corresponding information for each moving.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample #1 below
• For the first three testcases: 1 ≤ N, Q ≤ 10³, the sum of all the sz_i ≤ 10⁴, all the type_i ≠ 4
• For the first six testcases: all the type_i ≠ 4
• For the first eight testcases: the number of the fourth type of moving ≤ 100

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.

 

Note: there are two sample below. "# Sample Input 1/2" and "# Sample Output 1/2" are not the part of input and output.

They are just for marking that the following content corresponds to which sample.

Sample Input  Download

Sample Output  Download

Tags

Discuss