Description

Source : ACM International Collegiate Programming Contest Asia Regional Contest, Tsukuba, 2016/10/16 

You are given an ordered sequence of integers, (1,2,3,...,n). Then, a number of requests will be given. Each request specifes an integer in the sequence. You need to move the specied integer to the head of the sequence, leaving the order of the rest untouched. Your task is to find the order of the elements in the sequence after following all the requests successively.

Sample Output Explanation : In Sample Input 1, the initial sequence is (1; 2; 3; 4; 5). The first request is to move the integer 4 to the head, that is, to change the sequence to (4; 1; 2; 3; 5). The next request to move the integer 2 to the head makes the sequence (2; 4; 1; 3; 5). Finally, 5 is moved to the head, resulting in (5; 2; 4; 1; 3).

Input

The input consists of a single test case of the following form.

n m

e₁

:

e_m

The integer n is the length of the sequence ( 1 <= n <= 200000 ). The integer m is the number of requests ( 1 <= m <= 100000 ). The following m lines are the requests, namely e₁,...,e_m, one per line. Each request e_i ( 1 <= i <= m ) is an integer between 1 and n, inclusive, designating the element to move. Note that, the integers designate the integers themselves to move, not their positions in the sequence.

Output

Output the sequence after processing all the requests. Its elements are to be output, one per line, in the order in the sequence.

There should be a new line at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Megumin, a talent explosion magic archwizard, spends a lot of time studying explosion magic spells. For two magic spells A and B, she found that she can combine them together to create a powerful magic spell. Moreover, if the last k characters of A matches the first k characters of B, they can be merged to obtain a more powerful spell. Megumin finds out that the shortest combination of the two spells has maximum power.

For example, if A = "xxxababa" and B = "babayyy", there are severals ways to combine them together:

1. "xxxababababayyy", by simply concatenating A and B, sharing no common characters.

2. "xxxabababayyy", by sharing "ba", the last 2 characters of A and the first 2 characters of B.

3. "xxxababayyy", by sharing "baba", the last 4 characters of A and the first 4 characters of B.

Among all ways of combination, "xxxababayyy" has the maximum power.

Given two magic spells A and B, please output the combination of A and B with maximum power.

Implementation Hints

1. Use strlen() to retrieve length of a string. Remember to #include <string.h>

2. Be careful when using strlen(), or your program might run slowly.

Input

The first line is an integer T, meaning that the input has T test data. Each test data contains a single line.

In each test data, there are two magic spells A and B. Is is guaranteed that A and B only contains lower case alphabets (a-z).

Input consists of two lines. The first line contains A and the second line contains B. It is guaranteed that A and B only contains lower case alphabets (a-z).

• 1 <= T <= 10

• 1 <= |A|, |B| <= 1000

Output

For each test data, please output the answer in one line.  Remember to add new line character ('\n') in the end of each test data.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A Convolutional Neural Network (CNN) is a type of artificial neural networks that is primarily used for processing and analyzing visual data, such as images and video frames. CNNs have become widely popular in computer vision tasks due to their ability to automatically learn and extract meaningful features from input images. They consist of multiple layers, including convolutional layers, pooling layers, and fully connected layers, which work together to detect and recognize patterns in the data.

Today, Stiff Waist Beast wants to implement a small CNN, which processes an input image that is represented as a matrix of pixels with the following steps:

1. Horizontally flip the input image to enable the CNN to handle images with varying orientation.

2. Apply convolution using a filter to the flipped image.

The convolution is defined as follows:

Given an n * n image A and an m * m filter B, the resulting feature map after convolution is another (n - m + 1) * (n - m + 1) matrix C, where each element of C is computed as 

Finally, Stiff Waist Beast is curious about the number of pixels in the resulting feature map whose values exceed a given threshold k (for fun only ^^).

As a poor student, there are still many tasks waiting for Stiff Waist Beast to handle in the association. He asks you to finish this task.

Input

The first line contains an integer T, representing that there will be T testcases.

The first line of each testcase has three integers n, m, k.

Each of the following n lines has n integers, a_ij, representing image A.

And each of the following m lines has m integers, b_ij, representing filter B.

1 <= T <= 10, 1 <= n <= 500, 1 <= m <= min(n, 5), 0 <= a_ij, k < 256, -5 <= b_ij <= 5.

Output

Print an integer: the number of elements in the resulting feature map C whose values exceed the given threshold k.

Don't forget to print '\n' in the end!

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Story

(The following story is irrelevant to the problem description.)

Red Cape Flying Cat is a sophomore cat majoring in Computer Science at NTHU. He withdrew from "Calculus II" during his freshman year.

Due to some unexpected circumstances, he was unable to enroll in required courses such as "Computer Architecture" or "Probability", and he couldn't even get into "Graph Theory", the course he wanted to take the most. With no credits to his name, he has returned to "Introduction to Programming (II)" to learn, pretending as if he has plenty of credits.

Although he has already taken "Introduction to Programming (II)" once, he used AI to complete all his assignments last semester, so he has no idea how to solve this problem. However, Red Cape Flying Cat is very well-connected and knows you—a student also taking "Introduction to Programming (II)" who completes every assignment entirely on your own without using AI. Please help him complete this assignment.

Problem Statement

Red Cape Flying Cat has an r x c matrix consisting only of characters @ and ..

Red Cape Flying Cat wants to perform q operations on this matrix in the given order. There are three types of operations:

• 1: Transpose the entire matrix across the main diagonal.

• 2 idx shift: Perform a cyclic shift on the idx-th row to the right shift times.

• 3 idx shift: Perform a cyclic shift on the idx-th column downwards shift times.

Definition of the “single cyclic shift” operation for types 2 and 3: every element moves one position in the specified direction, and the element that moves out of the boundary is moved back to the beginning of the row or column. You can refer to the sample case for a better understanding.

Note that after a type 1 operation, the number of rows and columns may change. All subsequent operations are based on the new dimensions.

After all operations are completed, please output the final state of the matrix.

Sample Explanation

The following provides an explanation for the first test case in the sample input.

Input

The first line of the input contains a single integer t (1 <= t <= 20) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers r and c (1 <= r, c <= 50) — the number of rows and the number of columns of the matrix.

The following r lines each contain a string of c characters. The j-th character of the i-th string represents the element at the i-th row and j-th column of the matrix. Each character is either @ or ..

The next line contains a single integer q (0 <= q <= 50) — the number of operations.

The following q lines describe the operations. Each line starts with an integer representing the type of operation (1, 2, or 3). If the type is 1, there are no additional integers. If the type is 2 or 3, it is followed by two integers idx and shift (1 <= shift <= 10^9), representing the index of the row/column and the number of times to shift.

Let the current matrix size be r' x c'. For a type 2 operation, it is guaranteed that 1 <= idx <= r'. For a type 3 operation, it is guaranteed that 1 <= idx <= c'.

Output

For each test case, output the final state of the matrix after all operations are completed. Let r' and c' be the final number of rows and columns. Output r' lines, each containing a string of c' characters representing the matrix.

Don't forget to add a line break at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss