Description

Story Section

(You can skip this part if you know what convolution is.)

"You might think my eyes look scary, but don't worry. I'm just squinting because I couldn't see very well," the girl narrowed her beautiful eyes, turning towards me. "The truth is... I forgot my glasses."
"You forgot them?" I asked.
"Yeah... It's the first time in this month... how frustrating..."
Mie Ai, or Mie-san, is the girl whom I fell in love with. Not even once could I get her out of my mind. Seeing her being troubled by this situation, I decided to become her support, at least for today.
"Umm... Mie-san," I awkwardly spoke up, "if you don't mind, would you like me to help you?"
"Huh? You will?" her eyebrows raised. "How will you help me?"
"Well... I have a plan," I brought out a paper and a pencil. "Do you know what convolution is?"
"Convolution?" she repeated. "No, I have never heard of it."
"What about pixels? Have you heard about it before?"
"I think I have heard of it," she said. "Is it something to do with pictures, right?"
"Exactly. For computers, pictures are actually a grid of tiny squares of a specific color, called pixels," I started drawing a grid and filled it in with numbers. "The color is determined by the number in that pixel. For example, 0 means the pixel is completely black and the brightness goes up as the number goes up. When we reach 255, the pixel is completely white."
"But, Komura-kun... What does this have anything to do with convolution?"

"Let's say we have a smaller grid, each cell of which has a number inside. This is called a kernel," I placed a blue plastic piece on the paper. "When the kernel is placed over the grid, some number would be covered by the kernel, right? What we need to do is multiply each number in the kernel by the number that it is covering, and then add them all together."

"So this is what's called convolution?" Mie-san leaned over the paper, examining it closely.
"Not yet. We have to move the kernel over the whole grid while repeating the same thing--multiplying and adding," I slide the plastic over the paper. "After finishing this process, the output image should be completely filled with numbers. The output is called a convoluted image, while the whole process is called convolution."

Figure 1: The animation showing the algorithm in action

"So that's how it is... and how can I use this thing? It seems pretty pointless."
"It is, in fact, one of the crucial building blocks of computer vision. If we choose numbers in the kernel carefully, we can add effects, such as blurring, sharpening, and edge-highlighting, to a picture. We can even train the kernel to recognize more complex but tangible features such as eyes and ears using neural networks so that the computer can process the information like our brain does. Some applications in the real world include training self-driving cars to avoid pedestrians and medical devices that identify irregularities in X-ray films. Surely, it can help you too, Mie-san."

"Sounds interesting," she smiled. "By the way, you know how to make it, right?"
"Well... erm... that is a great question..."
"Komura-kun? What's wrong? You can code this right?"
"..."

Everyone... Please help me implement this convolution algorithm. I don't want to embarrass myself in front of my crush.

Figure 2: Example of effects of kernels on the output image

Question Section

If you are here, you probably know what convolution is already. So I'm going to make a summary of the program I need you to make.

I'm going to create a pair of glasses that takes in a grayscale image of width w and height h. I want you to create an algorithm that turns it into a convoluted image of width w-2 and height h-2 using a 3-by-3 kernel that contains a single-precision floating value in each pixel. Remember to round the numbers down to integers.

​

Input

In the first line, there are two positive integers, w and h, representing the width and height of the image. (3 ≤ w,h ≤ 300).

Following are 9 single-precision floating point numbers distributed into a 3 x 3 grid, representing the numbers in the kernel.

The remaining h lines consist of w integers each, representing the brightness value in a w x h grayscale picture. The brightness value in each pixel is a non-negative number b (0 ≤ b ≤ 255).

Output

The resulting convolved (w-2) x (h-2) image, consisting of numbers rounded to an integer with field width 4 (the format specifier is %4d), all followed by a space. At the end of each line, print an end-line character '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

TA Arithat is feeling upset because all of his k cups of Indomie were eaten during the test. To determine who is responsible, he has summoned n students to the classroom. As each student enters, they must follow a specific rule for knocking on the table:

1. When the first student arrives, they knock on the table once.
2. For subsequent students:
   • If the total number of students who have arrived so far is odd, the student must knock the table k times that of the previous student.
   • If the total number of students who have arrived so far is even, the student must knock the table k times more than the previous student.

After all students have knocked, the last student to arrive may knock on the door again using the same rule, and then everyone in the room will take turns knocking in reverse order of their initial entry.

For example, if there are 5 students named Alice, Bob, Charlie, David, and Eve, and k is 2, the knocking sequence would look like this:

(Alice enters, 1 student in total)
Alice: 1

(Bob enters, 2 students in total)

Alice: 1, Bob: 3, Alice: 1

 (Charlie enters, 3 students in total)

Alice: 1, Bob: 2, Charlie: 4, Bob: 2, Alice: 1

(David enters, 4 students in total)

Alice: 1, Bob: 3, Charlie: 5, David: 7, Charlie: 5, Bob: 3, Alice: 1

(Eve enters, 5 students in total)

Alice: 1, Bob: 2, Charlie: 4, David: 8, Eve: 16, David: 8, Charlie: 4, Bob: 2, Alice: 1

As the first student, your task is to keep a record of how many times each student knocked on the table. You do not need to include their names in the record.

Input

All test case contains two positive integer n and k. (1 ≤ n ≤ 32, 1 ≤ k ≤ 10)

Output

The record of how many times every person has knocked in each round. The number of times a student knocks on the table is to be separated by a space. At the end of each round, you must output an endline character '\n'.

It is guaranteed that all numbers are less than 2⁶³ - 1

Sample Input  Download

Sample Output  Download

Tags

Discuss