Description

In this problem, you have to implement a 2D convolution operation with zero-padding and stride.

Convolution is an operation that you elementwise multiply the sub-region in the original image(A larger 2D array) and the provided kernel(A smaller 2D array) and the summation of the multiplied values will be the new values in the output map(The size may be different from the original image). The multiplication follows a sliding window, so once we reach the bottom-right, we'll get a brand new 2D map.

Once you understand how to do simple convolution, another trick in convolution is that you can pad the original map with zeros, which is called zero-padding.

Last, we can decide the step size of the sliding window, which is called stride.

To sum up, you'll be given a 2D image and a 2D kernel, you are asked to do the convolution with the given padding size and stride.

Note that you only have to do the convolution in the valid region.

Input

The first line contains 2 integers, the height and the width of the 2D image, respectively. (1 <= height, width <= 1024)

Next, you have to read the whole 2D image.

The following line contains 2 integers, the height and the width of the 2D kernel, respectively. (1 <= height, width <= 10)

Then, you have to read the whole 2D kernel.

The last line will be the the size of stride and padding, respectively. (0 <= size of stride and padding <= 10)

All the values mentioned above are integers.

It is guaranteed every value of 2D images <= 255 and and 2D kernel is <= 10

Output

Please print the calculated 2D map.

The elements are separated by whitespace and you have to print '\n' at the end of each row.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ai is a super idol with the perfect smile.

All of her fans said that there was a star in her eye.

One day, a piece of shocking news claimed that she had become the mother of twins!

To prove this news, an easy way is to find if there is also a star in the baby's eye.

Also, because Ai's children must have the brightest star in their eyes, we need a program to automatically calculate the brightness of a star with a given picture.

Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the brightness is the summation of:

(1) A[X][j], for all 0<=j<N  (The values in the Xth row)

(2) A[i][Y], for all 0<=i<N  (The values in the Yth column)

(3) 

    A[X+i][Y+i], for all -N<=i<N if 0<=(X+i)<N and 0<=(Y+i)<N

    A[X+i][Y-i], for all -N<=i<N if 0<=(X+i)<N and 0<=(Y-i)<N

    (The values of two diagonals from the centers)

Note that when calculating the brightness, the value of the center points is calculated only once. 

Please help her fans find the truth, or they may become very angry @@.

Hint.

If you cannot pass all the testcases, you can try to use extra arrays to record some information when you read the input data.

By doing so, you can immediately determine whether a point is a star.

Input

In this problem, with a given image (square matrix), you have to solve T solutions.

There are four parts of the input:

(1) The number of testcases, T. 1<=T<=200000

(2) The size of the square matrix, N. 1<=N<=1024

(3) An N*N matrix separated by a newline character. 0<=The values in the matrices<=N.

(4) T pairs of center points composed of 2 integers, representing the position of the center points.

Output

The brightness of each star in the matrix.

It is guaranteed that the brightness can be represented using unsigned long long datatype.

Note that you need to print "\n" in the end of each answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Domo is a brilliant dog hacker, he wants to find out the password of your computer.

This time, he successfully obtained the compressed file containing the password, all he needed to do was unzip it.

Input

The input consists of multiple zipped strings (1 ≤ number of strings ≤ 100), separated by a newline character.

In each string (1 ≤ the length of string ≤ 1000), the [integer] is guaranteed to consist of a number N (0 ≤ N ≤ 100) without any leading zero. There are only uppercase and lowercase letters, digits, and single quotes in the string.

Notice that 0 can appear in the string, but the string can't be unzipped.

Output

Output the corresponding password for every string. It's guaranteed that the length of every unzipped string is less than 1000000.

Remember to print a newline character at the end of every password.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I don't have any pictures of Domo, so here is my cat. His name is Shiro

He sleep on my book to prevent me from studying, what a nice cat

You wan't to find the perfect bed for Shiro, so that he will not sleep on my book again

Given array A, the perfect bed is determined by the highest sum value from subarray between index i and j,

For example given array below:

The highest value is 7, which from index 2 to 6, as the sum is 4 + (-1) + (-2) + 1 + 5 = 7

Input

There are T test cases

each test case has an integer N on the first line and then followed by N integers in the next line: a₀, a₁​, a₂​, ..., a_N-1​

1 <= T <= 100

1 <= N <= 50000

-10⁹ <= a_i <= 10⁹

Output

For each testcase, print the maximum points of subarray, following by newline character

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Here is a Frieren picture to brighten your day!

There are N numbers, each number is positive and multiplier of K,
for e.g. if N = 10 and K = 3, the array should be [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]

However, Mr. 景璞 change one of the number to -1, and then scrambled the order
for e.g. the array become [30, 21, 9, -1, 3, 24, 27, 15, 12, 18]

Your task is to find what number was changed
in the example above, the missing one will be 6

Note: To pass all test cases, you need to consider the Memory Limit and Time Limit
Hint: 10⁵ of long long will take around 0.8 MB of memory

Input

There are T testcases

Each testcase has integer N, followed by a_0, a₁, a₂, ..., a_N-1 in the next line, and then K

1 <= T <= 50

1 <= N <= 10⁵

1 <= K <= 10⁶

-1 <= a_i <= N * K

For the first 3 testcases, N <= 2000

Output

For each testcase, output the missing number, followed by '\n'

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this question, we want to shoot the ball from a certain coordinate in D direction and determine the final position of the ball

The ball will go in the given direction until it leaves the map or collides with a wall. In the latter case, the ball will change its direction based on its original direction and the wall's arrangement, namely:

• Going Left:
  • Meet /: Change direction to Down
  • Meet \: Change direction to Up
• Going Right:
  • Meet /: Change direction to Up
  • Meet \: Change direction to Down
• Going Up:
  • Meet /: Change direction to Right
  • Meet \: Change direction to Left
• Going Down:
  • Meet /: Change direction to Left
  • Meet \: Change direction to Right

For example in the sample input:

However, the ball can also stuck in the map forever.

Input

The first line will be H, W, and D, representing the Height, Width of the map, and Direction

The next line will be HxW map, containing either '/', '\', '.', and 'S'

• / representing a wall from bottom left grid to top right grid
• \ representing a wall from top left grid to bottom right grid
• . representing an empty space
• S representing the starting point of the ball. It is guaranteed that there will be exactly one S in all test cases.

1 <= H, W <= 100

D is a string, the possibilites are "Left", "Right", "Up", and "Down"

Output

Print the last coordinate before the ball leaves the border map (outside of the array) with format row and column, separated by a space.

If it is not possible to go out from the array, print "Stuck QQ"

Don't forget the new line character after the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss