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

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

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

Discuss