Description

ZIP is an archive file format that supports lossless data compression. There are many way to zip compress data nowadays, such as RLE, LZW,Huffman Coding ans so on, Today your friend think out a method similiar as RLE(run length encoding) to compress data. 

He ask you to help him implement the zip algoithm program and analysis the compress rate of the method. As the best friend of you, you decided to try your best to finish the progeam.

Note : Fix time complexity problem modified by 2019/10/12

Input

S_1

S_2

...

S_N

Given the sequence contain only English letter or digit.

(2 <= the length of each sequence < 1000, and the input testcases are less than 1000)

Note that: the sequence is case-sensitive and the testcase is end of EOF character.

Output

Print out the zip string and the compression rate, each line followed by a newline character. (If the compression rate less than 1.0 then print out "compress rate:6.3f" with the result, otherwise print out "the string can't zip")

Note that : Using float not double.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a board with N rows and M columns, the rows are numbered from 1 to N from top to bottom, and the columns are numbered from 1 to M from left to right. Each element has one diagonal wall which either runs from top-left corner to bottom-right corner, or runs from top-right corner to bottom-left corner. Now given Q queries, you have to output which column the ball will fall out at the bottom row if you put it on top of the board at specific column. (The ball will naturally fall down due to gravity.)

The following figure is a sample. If you drop the ball at column 2, the ball will fall out at the left side. If you drop the ball at column 5, the ball will be stuck in the board. If you drop the ball at column 3, the ball will eventually fall out at column 2.

Input

First line contains two integers which represent n, m respectively. (1 <= n, m <= 500).

The following N lines which have M characters in each line represent the board. '/' means the wall runs from top-right corner to bottom-left corner, and '\' means the wall runs from top-left corner to bottom-right corner.

Next line contains an integer Q which denotes the number of querys. (1 <= Q <= 100).
Then, the following Q line, each line has one integer which represents the starting column to drop the ball.

Output

For each queries:
If the ball fall out at the right side, you should output "Right!".
If the ball fall out at the left side, you should output "Left!".
If the ball stuck at the board, you should output "Stuck QQ".
Otherwise, you should output "Position: x". x represents which column the ball fall out at the bottom row.
Remember to output '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Domo is a brilliant dog. When he finds a perfect bed for him, he will fall asleep immediately.

A subarray (a sequence of consecutive elements in an array) is a perfect bed for Domo if it satisfies the following two conditions.

1. the length of this subarray is L.

2. The numbers in the middle are greater than the numbers on both sides the left most and the right most of the subarray. In other words, a_i < a_j for all pairs of i and j (i ∈ {0, L-1}, 0 < j < L-1)

For example, a subarray [3, 5, 5, 3] is a perfect bed of length 4 for Domo, but [4, 5, 3, 2] isn't (since a[2] < a[0]).

Given an array and an integer L, your task is to find the perfect bed for Domo. If there are multiple perfect beds for Domo, print them all in order by the index of the first element of the subarray.

Check the sample input/output for more details, but be careful not to wake Domo up. He will let you get zero points on this question if he wakes up accidentally.

Input

The first line contains two integers N and L (3 ≤ N ≤ 1000, 3 ≤ L ≤ 10) - the length of the given array and the length of the subarray, respectively.

The second line contains N integers a₀, a₁, ..., a_n-1 (0 ≤ a_i ≤ 1000)

Output

The subarray of which describes the perfect bed for Domo.

If there are multiple perfect beds, print them all one per line.

If there is no perfect bed for Domo, print "Domo".

Note that you should print a newline character at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dio, an evil vampire, does all kinds of evil and nobody can fight against him.

However, there's a brave man, JoJo, standing out and using all his ability to defeat him.

Everyone appreciate JoJo's great achievement and the world becomes safe and peace again.

Unfortunately, since Dio is a vampire, he revives himself again and tries to make more chaos......

We have known that there is a star-shaped birthmark on Dio's neck. To make sure that Dio is not able to enter our country, in the airport, we will use a special technique to scan a part of the visitors' skin and transfer the raw image to gray scale (0-255, 0 means black and 255 means white).

Given an image (square matrix) A[N,N], if point P(X,Y) is the center of a star, the following condition will be satisfied:

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

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

(3) 

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

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

    (The values of two diagonals from the centers are all 255)

For example, a star looks like:

In this problem, given T  square matrices wth size N, you are asked to find out how many stars in each matrix respectively.

Hint.

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

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

Input

There are three parts of the input:

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

(2) The size of the square matrices, N. 1<=N<=2048

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

Output

The number of stars in each matrix.

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy

~ 《Never Gonna Give You Up》

In this problem, given 2 matrix, A[N, M] and B[M, N]. You are asked to calculate C = (A x B)^T (the transpoed matrix of A multiplies B).

How to calculate A x B:

How to transpose a matrix:

Note that every elements in A, B, and C can be represented by datatype int.

Input

There are three parts of the input:

(1)1<=N<=2100

(2)1<=M<=2100

(3)A[N,M] and B[M,N] separated by a newline charcter. -100<=The values in the matrix<=100.

Output

C = (A x B)^T (the transpoed matrix of A multiplies B).

Note that you have to print whitespaces between each elements and a newline character in the end of each rows.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The savoury smell of boiling soup drifted upstairs. The periodic sound of the knife chopping the potato made me comfortable. What will the breakfast be? I think while slowly strolling down the stairs. The light was shining through the door gap. Silently, I entered the kitchen, sneaked behind my boyfriend, and covered his eyes.

“Hey! Guess who?” I asked.

“Oh… who could it be…? Pekora-chan?” He replied

“Jeez, come on! You’re always like this!”

“Haha, sorry! I’ll stop joking around!”

“Now, can you guess who I am?”

“…”

“You didn’t forget my name, did you…?”

I gave him the last chance to say my name, one letter at a time, and I’ll keep track of the number of letters he successfully made so far.  If he makes a mistake, I will warn him by outputting “no” until he’s back on the right track. At any point, instead of saying a letter, he could either choose to say the character ‘/’ and delete the last letter but my temper will decrease by 1 unit or say the character ‘!’ and restart all over but my temper will go down by two units. If he could say my name correctly before my temper reached zero, I will say “DAISUKI!” and let him go immediately. Otherwise, I’ll say “SAYONARA” and punish him.

 You must help me make sure I didn’t make any mistakes. If you don’t help me, you’ll be the next.

Input

The first line is a string, the girl’s name, which wouldn’t exceed 10000 characters in length.

The second line is her initial temper n ( 1 ≤ n ≤ 10⁹)

The last line is his guess as a string of alphabets and special characters which you need to scan until EOF.

Output

If the scanned character is '/' or '!', print out nothing but modify the string accordingly. Otherwise, output the number of correct characters when no mistakes are made and the string “no” when there are, both with the trailing newline character.

If the boy successfully guessed the girl’s name at any point, output “DAISUKI!” after the number of correct characters and stop the program immediately. Otherwise, output “SAYONARA”.

Sample Input  Download

Sample Output  Download

Tags

Discuss