2D arrays

ID 27224. Bovine Genomics #3

ID 37042. Diagonal padding

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  0 1 3 6 10 14 18 22 26 30
  2 4 7 11 15 19 23 27 31 34
  5 8 12 16 20 24 28 32 35 37
  9 13 17 21 25 29 33 36 38 39

ID 37046. 12.25b

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  1 5 9 13 17
  2 6 10 14 18
  3 7 11 15 19
  4 8 12 16 20

ID 37048. 12.25g

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  4 8 12 16 20
  3 7 11 15 19
  2 6 10 14 18
  1 5 9 13 17

ID 37047. 12.25v

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  5 4 3 2 1
 10 9 8 7 6
 15 14 13 12 11
 20 19 18 17 16

ID 37049. 12.25h

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 16 17 18 19 20
 11 12 13 14 15
  6 7 8 9 10
  1 2 3 4 5

ID 37050. 12.25h

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 17 13 9 5 1
 18 14 10 6 2
 19 15 11 7 3
 20 16 12 8 4

ID 37051. 12.25 and

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 20 19 18 17 16
 15 14 13 12 11
 10 9 8 7 6
  5 4 3 2 1

ID 37052. 12.25k

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 20 16 12 8 4
 19 15 11 7 3
 18 14 10 6 2
 17 13 9 5 1

ID 37059. 12.25d

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  1 2 3 4 5
 10 9 8 7 6
 11 12 13 14 15
 20 19 18 17 16

ID 37060. 12.25

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  1 8 9 16 17
  2 7 10 15 18
  3 6 11 14 19
  4 5 12 13 20

ID 37073. 12.25l

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 20 19 18 17 16
 11 12 13 14 15
 10 9 8 7 6
  1 2 3 4 5

ID 37074. 12.25m

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  5 4 3 2 1
  6 7 8 9 10
 15 14 13 12 11
 16 17 18 19 20

ID 37075. 12.25n

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 17 16 9 8 1
 18 15 10 7 2
 19 14 11 6 3
 20 13 12 5 4

ID 37076. 12.25o

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

  4 5 12 13 20
  3 6 11 14 19
  2 7 10 15 18
  1 8 9 16 17

ID 37077. 12.25p

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 16 17 18 19 20
 15 14 13 12 11
  6 7 8 9 10
  5 4 3 2 1

ID 37078. 12.25r

Numbers n and m are given. Create an array A[n][m] and fill it as shown in the example.

Input: The program receives two numbers n and m as input.
Output: The program should output the resulting array, putting exactly 3 characters for each number.

Examples

 20 13 12 5 4
 19 14 11 6 3
 18 15 10 7 2
 17 16 9 8 1

ID 7128. Championship table - 1

A table of some championship is given. The elements of the main diagonal are 888.  Each element of the array that is not on the main diagonal can be either a single or double digit number, the record of which is formed by numbers indicating the number of goals scored (the first digit of the number) and the number of missed (the second digit of the number) in this match . 
For example: 32 - three scored, two missed.
0 - zero scored, zero missed
5 - zero scored, five conceded

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Output: The program should output N lines of 2 numbers each: the total number of goals scored and the total number of goals conceded by each team

ID 7127. Championship table - 2

A table of some championship is given. The elements of the main diagonal are 8.  Each element of the array that is not on the main diagonal can take the following values: 3 - if this team won the game, 0 - if it lost, 1 - if the game ended in a draw.

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Output: The program should print N lines of 3 numbers each: the number of wins, the number of draws and the number of losses for each team. The first line matches the first   command, etc.

ID 7126. Minimum on diagonals

In an NxN square array, where N is an odd number. Swap the smallest element among those on the main and secondary diagonals with the element located in the lower left corner of the array. If there are several smallest elements, then change the one with the row and column numbers less.

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.
Output: The program should display the modified array

ID 7125. Largest on the diagonals

In an NxN square array, where N is an odd number. The largest element among those standing on the main and secondary diagonals is interchanged with the element standing at the intersection of these diagonals. If there are several largest elements, then change the one with the row and column number less.

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.
Output: The program should display the modified array

ID 7124. The sum of the maximum and minimum

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Output: The program should print a single number - the sum of the maximum element of the main diagonal and the minimum element of the secondary diagonal

ID 7123. Sum on the diagonals

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Input: The program should output
1) the word YES - if the sum of the elements located on the main diagonal is greater than the sum of the elements located on the secondary diagonal
2) word NO - if condition 1 is not met

ID 7122. Arithmetic mean on the secondary diagonal

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Output: The program should print a single number - the arithmetic mean of the elements of the side diagonal of a two-dimensional array.

ID 7121. Arithmetic mean on the main diagonal

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Output: The program should print a single number - the arithmetic mean of the elements of the main diagonal of a two-dimensional array.

ID 7120. Sum of Diagonal Elements

Input: The program receives as input the number N <= 15, which is the number of rows and columns in the array. Next, the input stream contains N lines of N numbers that are elements of the array.

Output: The program should output a line containing space-separated numbers that are the sum of those two elements of each line that belong to the main and secondary diagonals

ID 7119. symmetrical array

Check if a 2D array is symmetrical about the main diagonal. Main diagonal — one that goes from the upper left corner of the two-dimensional array to the lower right.

Input: The program takes as input N <= 15, which is the number of rows and columns in the array. Next in the input stream are n lines of N numbers, which are elements of the array.

Output: The program should output the word yes for a symmetrical array and the word no for asymmetric array.

ID 6025. Processing a column in a matrix - 2

Given a two-dimensional array A[N][M] ( 2<=N<=20; M 2<=M<=20).
In the first line, enter the number of rows separated by a space - a number from 0 to N-1, and the number of columns - a number from 0 to M-1.
The second line contains the number s (0<=s<=20)
Next comes the input of array elements line by line
Determine the sum of all elements of the s-th column of the array.

Examples

ID 6029. Finding the required string

 n athletes compete in the hammer throw. Each of them made  m throws. (n<=20, m<=20)
The winner is the athlete who has the maximum sum of results for all throws. 
If we renumber the athletes with numbers from 0 to n-1, and the attempts of each of them – from 0 to m-1, then the program receives an array A[n][m] as input, consisting of non-negative integers (0<A[n][m]<500). The program must determine the line number with the maximum sum of numbers and display this amount and the line number for which this sum is reached.

Input data: The program receives as input two numbers n and m, which are the number of rows and columns in the array. Next in the input stream are n lines of m numbers, which are elements of the array.

Output data: Program should output  2 numbers: the amount and line number for which this amount is reached. If there are several such lines, then the number of the smallest of them is displayed. 

Examples

ID 6030. Maximum in matrix - 1

 n athletes compete in the hammer throw. Each of them made  m throws. The winner of the competition is the athlete who has the best result in all throws. Thus, the program must find the value of the maximum element in the given array, as well as its indices (i.e., the number of the athlete and the number of the attempt).

Input: The program receives as input two numbers n and m (1<=n<=20;  1<=n<=20), which are the number of rows and columns in array. Next in the input stream are n lines of m numbers, which are elements of the array.

Output data: The program prints the value of the maximum element, followed by the row number and the column number in which it occurs. If there are several maximum elements in the array, then you need to print the minimum number of the line in which such an element occurs, and if there are several such elements in this line, then you need to display the minimum number of the column. 

ID 37169. Game "Life". Easy option

In some cells of the square \( N\ х\ N\) microorganisms live (no more than one in one cell). The following happens every second:
– all microorganisms that have less than 2 neighbors die of boredom (neighbors are microorganisms that live in cells that have a common side or top);
– all microorganisms with more than 3 neighbors die from overcrowding;
– on all empty cells, in which microorganisms lived in exactly three adjacent cells, new microorganisms appear.
All changes occur simultaneously, that is, for each cell, its fate is first clarified, and then changes occur in all cells at once.
It is required to determine from this configuration what it will turn into after \(T\) seconds.

ID 6026. Processing a row in a matrix - 2

Given a two-dimensional array A[N][M] ( 2<=N<=20; M 2<=M<=20).
In the first line, enter the number of rows separated by a space - a number from 0 to N-1, and the number of columns - a number from 0 to M-1.
The second line contains the number  k
Next comes the input of array elements line by line
Determine the arithmetic mean of the elements of the k-th row of the array.

Examples

ID 6027. Processing a row in a matrix - 1

Given a two-dimensional array A[N][M] ( 2<=N<=20; M 2<=M<=20).
In the first line, enter the number of rows separated by a space - a number from 0 to N-1, and the number of columns - a number from 0 to M-1.
The second line contains the number k
Next comes the input of array elements line by line
Determine the number of elements from the last row that are multiples of k.

Examples

ID 6028. Processing a column in a matrix - 2

Given a two-dimensional array A[N][M] ( 1<=N<=20; M 1<=M<=20).
In the first line, enter the number of rows separated by a space - (rows of the array are numbered from 0 to N-1), and the number of columns - (columns of the array are numbered from 0 to M-1)
Next comes the input of array elements line by line
Determine the number of two-digit numbers from the last column.

Examples

ID 36994. Matrix search

Write a program that determines how many times an element equal to K  occurs in a matrix.

Input
The first line contains the dimensions of the matrix separated by a space: the number of rows N and the number of columns M  (\(1 <= N , M <= 100\)). The following N lines contain matrix rows, each – by M natural numbers separated by spaces. The last line contains an integer K.

Imprint
The program should output the number of matrix elements equal to K.
 

Example

ID 36995. Minimum and maximum in the matrix

Write a program that finds the minimum and maximum elements in a matrix. If the matrix has several identical minimum (maximum) elements, you need to find the indices of the first such element in the order of traversal along the lines: from left to right, from top to bottom.

Input 
The first line contains the dimensions of the matrix separated by a space: the number of rows N and the number of columns M  (\(1 <= N , M <= 100\)). The following N lines contain matrix rows, each – by M natural numbers separated by spaces.

Imprint 
On the first line, the program should print the indexes of the minimum element (row and column), and then – its meaning. Numbering of rows and columns starts from one. All numbers are separated by spaces. The second line displays information about the maximum element in the same format.
 

Example

ID 36998. Output columns with a maximum

Write a program that finds columns in a matrix that have an element equal to the maximum.

Input data 
The first line contains, separated by a space, the dimensions of the matrix: the number of rows N and the number of columns M (\(1 <= N , M <= 100\)). The following N lines contain matrix rows, each – by M natural numbers separated by spaces.

ID 27238. The line with the minimum amount

Write a program that finds the row with the minimum sum in a matrix.

Input
The first line contains the dimensions of the matrix separated by a space: the number of rows N and the number of columns M  (\(1 <= N, M <= 100 \)). The following N lines contain matrix rows, each – by M natural numbers separated by spaces.

Imprint
The program should display all elements of the found string with the minimum sum, separating them with spaces. If there are several rows with the same minimum sum, you need to select the row with the minimum index from them.
 

Examples

ID 36996. Counting by amount

Write a program that determines how many K -digit numbers are in the matrix, the sum of the digits of each of which is a multiple of R .

Input
The first line contains, separated by a space, the dimensions of the matrix: the number of rows N and the number of columns M (\(1 <= N , M <= 100\)). The following N lines contain matrix rows, each – by M natural numbers separated by spaces. Then the numbers K and R .

ID 27237. Magic square?

ID 27235. Custom filling - 1. Diagonals

ID 27236. Custom filling - 2. Snake

Input
The input string contains the numbers N and M separated by a space.

Imprint
The program should display the matrix filled in the specified way.

Example

ID 27234. Simple task

Given a two-dimensional array N*M (\(0<N,M<=20\)).
Array element values ​​are entered from the keyboard
Output in the first line all the corner elements of the array, starting from the upper left corner and moving clockwise.

Input
The first line specifies the size of the array. N - number of rows, M - number of columns (\(0<N,M<=20\) )
Next come N lines of M numbers in each line - elements of a two-dimensional array (each element modulo no more than 50)

Imprint
Output, one space apart, all the corner elements of the array, starting from the upper left corner and moving clockwise.
 

Example

ID 37026. square matrix

Given a number n. Create a two-dimensional array of size nxn and fill it according to the following rule. The numbers 0 should be written on the main diagonal. On the two diagonals adjacent to the main one, the numbers 1. On the next two diagonals, the numbers 2 etc.

Input
The input is a single number n (n<=10).

Imprint
Display the completed matrix.
 

Example

ID 37030. side diagonal

Given a number n. Create an nxn array and fill it with the following rule:

The numbers on the diagonal going from the top right to the bottom left corner are 1.
Numbers above this diagonal are 0.
Numbers below this diagonal are 2.

Display the resulting array. Separate numbers in a line with one space.

Example

ID 37032. symmetrical array

Given a number n and a two-dimensional array of size nxn. Check if this 2D array is symmetrical about the main diagonal. Print the word “YES” if the two-dimensional array is symmetrical, and the word “NO” - otherwise.

Input
The first line contains a number n - the size of a two-dimensional array (n <= 10). Next come n lines of n numbers each - elements of a two-dimensional array.

Imprint
Print the word "YES" if the array is symmetric, or "NO" - otherwise
 

Example

ID 37033. Diagonal below main

Given a square two-dimensional array of size nxn and a number k. Print the elements of the kth diagonal below the main diagonal (i.e. if k=1, then you need to print the elements of the first diagonal lying below the main one, if  k=2, then the second diagonal, etc.).

The k value can be negative, for example, if k=−1, then you need to print the value of the first diagonal lying above the main one. If k=0, then print the elements of the main diagonal.

Input data 
The program receives a number n (n <= 10) as input, followed by the elements of the array  n lines of n characters per line, then on a new line, number k (all elements and value k modulo no more than 100) .

Examples

ID 37034. Diagonal exchange

Given a square array. Swap the elements on the main and side diagonals, with each element remaining in the same column (i.e., in each column, you need to swap the element on the main diagonal and on the side diagonal).

Input
The input is the number n  - size of the square array (n <= 10). Next come n lines of n numbers each - array elements.

Imprint
Display the array after conversion.
 

Example

ID 37038. quadrants

Fill the square array with integers as shown. There are zeros on the main and side diagonals, these diagonals divide the array into four parts. Units are written in the upper part, twos are written in the right, threes are written in the bottom, fours are written in the left.

Input
The input is a single number n - the size of a square array (n <= 100).

Imprint
Display the completed square matrix.
 

Examples

ID 37083. Replacing a column with array elements

Given a matrix of size NxM and an array of numbers of size N. In this matrix, replace all elements of the column with the maximum sum of elements with elements of the given array of numbers. If there are several such columns, then replace the elements in the column with the lower index.

Input
The first line contains numbers N and M (\(0<N,M<=10\)) . Next come N lines of M numbers each. Each modulo number is no more than 100. The last line contains N array numbers.

Imprint 
Display the transformed matrix, allocating three character spaces for each element. Each number must be followed by a space character.
 

Example

 52 16 61 76
  5 5 33 69
 37 34 14 26

ID 37085. String exchange

Given a matrix of size NxM and two numbers k1 and k2. Swap the lines with indices k1 and k2.

Input
The first line contains numbers N and M (\(0<N,M<=10\)) . Next come N lines of M numbers each. Each number modulo no more than 100. Following a new line are two numbers k1, k2 (\(0<k1 ,k2<=N\)).

Imprint
Display the transformed matrix, allocating three character spaces for each element.
 

Example

 33 76 69 59 58
 48 93 27 9 76
 72 50 18 79 74
 19 65 53 90 77

ID 37087. Removing rows

A two-dimensional array stores the results (time in minutes) shown by each of the N drivers in each of the 10 Formula 1 races. (in the zero line - the results of the first rider, in the first line - the second, etc.). After the tenth stage, the racer with the serial number K  dropped out of the competition. The panel of judges decided to remove the results of this participant from the table.
Modify the array accordingly and print it to the screen.

By deleting a string in a two-dimensional array, we mean:
1) exclusion of this line from the array by shifting all lines following it one up;
2) assigning the value 0 to all elements of the last row (or reducing the number of rows by 1).

Input
The first line specifies the number N (\(0<N<=30\)). Next come N lines of 10 numbers each. Each number modulo no more than 100. Followed by a new line number K (\(1<=K<= N\)).

Imprint 
Display the transformed matrix, allocating three character spaces for each element.
 

Example

 38 43 82 95 20 100 99 83 77 42
 94 92 74 30 93 75 99 6 79 68
 62 97 14 40 70 31 3 84 33 74
 99 30 91 15 41 54 87 31 71 74

ID 37087. Removing rows

A two-dimensional array stores the results (time in minutes) shown by each of the N drivers in each of the 10 Formula 1 races. (in the zero line - the results of the first rider, in the first line - the second, etc.). After the tenth stage, the racer with the serial number K  dropped out of the competition. The panel of judges decided to remove the results of this participant from the table.
Modify the array accordingly and print it to the screen.

By deleting a string in a two-dimensional array, we mean:
1) exclusion of this line from the array by shifting all lines following it one up;
2) assigning the value 0 to all elements of the last row (or reducing the number of rows by 1).

Input
The first line specifies the number N (\(0<N<=30\)). Next come N lines of 10 numbers each. Each number modulo no more than 100. Followed by a new line number K (\(1<=K<= N\)).

Imprint 
Display the transformed matrix, allocating three character spaces for each element.
 

Example

 38 43 82 95 20 100 99 83 77 42
 94 92 74 30 93 75 99 6 79 68
 62 97 14 40 70 31 3 84 33 74
 99 30 91 15 41 54 87 31 71 74

ID 37088. Removing columns

A two-dimensional array stores the results (time in minutes) shown by each of the \(N\) cyclists at each of the 12 events ( in the zero column - the results of the first stage, in the first - the second, etc.) The results of the K-th stage were invalidated by the panel of judges and were removed from the table.
Modify the array accordingly and print it to the screen.

By deleting a column in a two-dimensional array, we mean:
1) exclusion of this column from the array by shifting all columns following it by one to the left;
2) assigning the value 0 to all elements of the last column (or reducing the number of columns by 1).

Input
The first line specifies the number N (0<N<=30). Next come N lines of 12 numbers each. Each number modulo no more than 100. Following a new line is the number K (1<=K<=12).

Imprint
Display the transformed matrix, allocating three character spaces for each element.
 

Example

 65 2 22 41 18 80 15 35 20 21 27
  7 28 35 15 27 87 95 73 45 26 28
  1 99 11 11 13 80 78 3 53 76 73
 87 37 11 72 33 59 79 61 53 80 67

ID 37084. Cycle line by line

Shift each row of the given rectangular matrix NxM cyclically to the right by the number of positions equal to the row number (numbering of rows and columns starts from 0). Display the transformed matrix.

Input
The first line contains two numbers N and M (\(0 < N,M <= 10\)). Next come N lines of M numbers in each - matrix elements (each element is no more than 100 modulo).

Imprint
Output the modified matrix. For each element in the output, allocate exactly 3 characters (familiar spaces).

Make a right shift K positions as a subroutine.
 

Example

 47 63 22 75
 70 69 69 12
 13 31 70 90

ID 37086. Column swap

Given a matrix of size NxM and two numbers k1 and k2. Cycle leftward between columns k1 and k2 (including columns k1 and k2, i.e. The k1 column must be in place of the k2 column, the k2 column in the place of the k2-1 column, etc. .).

Input
The first line contains numbers N and M (\(0<N,M<=10\)) . Next come N lines of M numbers each. Each number modulo no more than 100. Following a new line are two numbers k1, k2 (\(0<= k1<=k2< M\)).

Imprint
Display the transformed matrix, allocating three character spaces for each element.
 

Example

 32 94 56 12
 72 51 15 60
  4 97 43 38

ID 37089. Insert columns

The two-dimensional array contains annual grades for ten subjects of each of the N students of the class (in the zero column - grades in the first subject, in the first - in the second, etc.), but by mistake they forgot to enter into the array grades for one more subject, which should be in the K column. Modify the array so that it is properly populated. 

By adding a column to a two-dimensional array, we mean:
1) increase the number of array columns by 1;
2) shift of all columns after K-th by one to the right;
3) assigning given values ​​to the elements K-th column.

Input
The first line specifies the number N (0<N<=30). Next come N lines of 10 numbers each. Each number in the range 2 to 5. Next line is the number K (1<=K<=10< /code>). Further, in the last line (without skipping lines) there is N numbers, the grades of the corresponding student in the new subject.

Imprint
Display the transformed matrix, separating each element with a single space.
 

Example

5 5 3 4 2 4 1 3 3 4 4 
5 3 3 1 2 3 4 3 2 4 3 
3 2 4 5 4 2 1 4 2 2 4 
5 1 3 5 1 1 1 5 3 4 1 
3 3 4 2 1 5 3 3 5 2 1

ID 37082. Changing the line with the maximum

In a NxM matrix, replace with the value -1 all the elements of those rows that contain the maximum element.

Input
The first line contains two numbers N and M (\(0 < N,M <= 10\)). Next come N lines of M numbers each - matrix elements (each element is less than 100).

Imprint
Output the modified matrix. For each element in the output, allocate exactly 3 characters (familiar spaces). Each number must be followed by a space character.
 

Example

 15 68 54 79 89
 91 57 21 70 24
 14 22 5 26 76
 -1 -1 -1 -1 -1
 50 62 50 58 1

ID 38140. Comfort for cows

Farmer John's pasture can be represented as a huge 2D grid of cells (a huge chessboard). Initially, the pasture is empty.
Farmer John will add N (1≤N≤10⁵) cows to the pasture one by one. The i-th cow occupies a cell (x_i,y_i) that is different from the cells occupied by all other cows (0≤x_i, y_i≤1000).

A cow is said to be "comfortable" if she has exactly three other cows horizontally and vertically. Farmer John wants to count how many cows are comfortable in his pasture. For each i in the interval 1…N, print the total number of cows that are comfortable after the i-th cow is added to the pasture.

Input: 
The first line contains a single integer N. Each of the following N lines contains two space-separated integers indicating the (x,y) coordinates of the cow's cell. It is guaranteed that all cells are distinct.
Output: 
The i-th line of the output should contain the total number of cows that are comfortable after adding the i-th cow to the pasture.
 

Examples

ID 38194. Chess board

From the chessboard along the borders of the cells, a connected (not falling apart) figure without holes was cut out. It is required to determine its perimeter.

Input
First enter the number N (1 ≤ N ≤ 64) – the number of excised cells. In the next N lines, enter the coordinates of the sawn cells, separated by a space (line and column number – numbers from 1 to 8). Each sawn cell is indicated once.

Imprint
Print one number – the perimeter of the sawn figure (the side of the cell is equal to one).

Examples

ID 38202. Chess domino

A set of chess dominoes consists of 32 2x1 tiles, each of the squares of which is colored black or white (some of the tiles consist of two white squares, some of them are two black ones, and some of them are one white and one black). A set of such dominoes is laid out on a chessboard. It is allowed to rotate dominoes by 180 degrees (swap their squares), leaving each domino in its place. It is required to find out whether it is possible to rotate some of the dominoes in such a way that each horizontal row contains squares of only one color.


Input
Enter 8 lines of 8 numbers. Each number corresponds to the number of the domino that covers the given cell. The number is positive if the domino square is white and negative – if black.


Imprint
It is required to output one word – YES or NO (in capital letters).

Examples

ID 38222. magic square

A magic square is a table containing the numbers 123…  once, so that the sum of the numbers in each row and in each column is equal. We will tell you about one of the methods for constructing magic squares (it is called Siamese). It is only suitable for building squares with an odd side (3355…) .

Let's put the number 1 in the top cell of the central column. Next, we will move diagonally to the right and up, placing the numbers 234… . If we have gone beyond the table up, then we need to go to the bottom cell of the same column and continue from it. If we went beyond the right border, we need to go to the left cell of the line where we were supposed to get. If we went both up and to the right at the same time, then we need to go to the lower left cell of the square.

If there is already a number in the next cell on our way, then instead of going "right-up"; you need to make a move “down” (again, if we go beyond the boundaries of the square, we need to go to the top cell of the same column). Examples for squares 33 and 55 are shown in the pictures.



Input
The input is one natural odd number N, not exceeding 30 – square size.

Imprint
Print the numbers written in a square. It is not necessary to align the numbers by columns. Please note: it is required to display the magic square obtained by applying the specified method.

Examples

ID 38252. Ant farm

For the last birthday, Oleg was presented with an ant farm and three large ants for her. The farm is a field of a.thinsp;.times..b cells. The cell with coordinate (1, 1) is in the upper left corner. Soon he noticed that moving around his enclosure, the ants leave footprints of different colors on the white sand. For several months, Oleg watched his farm and, finally, was able to strictly describe what was happening in the enclosure.

Cells come in four colors:

• white (this means that the cell is not colored by any of the ants, indicated by the number 0)
• red (this is — the color of the first ant's footprint, denoted by the number 1)
• yellow (this is — the color of the track of the second ant, indicated by the number 2)
• green (this is — the color of the trail of the third ant, indicated by the number 3)

• paints it your own color
• rotates 90°  to the right and takes a step forward

• erases the trace from it (that is, paints the cell white)
• rotates 90º to the left and takes a step forward

ID 38259. Minesweeper with hints

During spring break, Olya thought about her behavior for a long time and decided to study more in the fourth quarter. But already the first biology lesson in the new quarter destroyed all Olya's good intentions. Olya is bored, just unbearably bored. Having nothing to do, she started playing the famous Minesweeper game on her phone.

Just in case, let's recall what this game is about. The game takes place on a field measuring N × M cells, some of which are "mined". The goal of the game is to open all the cells that do not contain mines.

The player opens the cells, trying not to open the cell with a mine. Opening a cage with a mine, he loses. If there is no mine under the open cell, then a number appears in it, showing how many cells adjacent to the newly opened one are “mined”. Cells are considered neighbors if they have a common side or a common vertex. Cells that the player considers "mined" can be marked with a flag to avoid accidentally opening them.

Olya plays the Minesweeper version with built-in hints. One of the prompts, "Show Errors", works like this. If there are more flags in the neighborhood of a cell in which a certain number is written than can be adjacent to this cell (that is, more flags than the number written in the cell), all the flags around this cell are highlighted in yellow. This hint cannot find other errors, otherwise it would not be interesting to play at all.

Your task — according to the current state of the playing field, determine which flags will be highlighted in yellow after the hint is launched.

Input
The first line contains two numbers N and M separated by spaces — height and width of the table respectively (1 ≤ N ≤ 15, 1 ≤ M ≤ 15). The next N lines contain M characters each. These lines set the playing field. The following notation is used:

F — checkbox;

* — closed cage;

A number from 0 to 8 — open cell. The number itself indicates how many mines are in the cells adjacent to this one.

Imprint
In the first line print the number of checkboxes that will be highlighted in yellow, and in the next N lines print for each such flag its coordinates — the row number and then the column number in which the checkbox is located. Flags can be displayed in any order.

If there are no highlighted flags, print a single number 0
 

Examples

ID 38336. Island

A map of the island is drawn on checkered paper (the cells of the island are shaded). At the same time, the island is a checker-convex figure, that is, each horizontal or vertical line on the map either does not intersect the island, or intersects it along a segment (the intersection line does not contain breaks). Also, the island is a connected figure, that is, any two cells of the island are connected by a path, every two neighboring cells of which have a common side.

A cell is considered adjacent to an island if it does not belong to the island, but shares a side or corner with one of the island's cells. For example, on the following map, the cells of the island are shaded, and the cells adjacent to the island are marked with asterisks.


The plane must fly around the island in the adjacent cells without invading the territory of the island. The program should create a flight route for the aircraft. The plane starts flying around the island in one of the neighboring cells with the island and must visit all the cells adjacent to the island exactly once. In this case, the aircraft can move from one cell to another cell only if these cells have a common side.

Imprint
The program receives as input two numbers N and M, written in separate lines, — number of rows and columns of the island map (3 ≤ N ≤ 100, 3 ≤ M ≤ 100). Next is a map of the island — N lines, each containing M characters. Each map symbol can be either the character ".", which means a cell that does not belong to the island, or the character "#", which means a cell of the island. In this case, the island does not touch the edge of the map.

Let's introduce a coordinate system on the map. The first coordinate is the line number, the lines are numbered from top to bottom with numbers from 1 to N. The second coordinate — column number, columns are numbered from left to right with numbers from 1 to M.

Input
The program should display the coordinates of the map cells in the order they were flown by the aircraft. Each output line must contain two numbers x and y — aircraft coordinates separated by a space (1 ≤ x ≤ N, 1 ≤ y ≤ M). The plane must visit each cell adjacent to the island exactly once. Every two consecutive cells in the output must have a common side. Any possible route around the island can be displayed.

Examples

6
7
.......
.......
.......
.###...
.###...
.......

ID 38360. Beam of light in the dark realm

The Dark Kingdom is an NxM labyrinth, some cells of which are surrounded by mirror walls, and the rest — empty. The entire labyrinth is also surrounded by a wall of mirrors. In one of the empty cells of the labyrinth, a traffic light was placed that emits rays in 4 directions: at 45 degrees relative to the walls of the labyrinth. It is required to depict the trajectory of these rays.

When the beam comes to the corner through which the mirror walls pass, it goes further as shown in the pictures (the cells that are surrounded by mirror walls are shown in gray). The ray behaves in a similar way when it comes to the border of the maze.


Input
The first line of the input file contains two natural numbers N and M — the number of rows and columns in the maze (each of the numbers is not less than 1 and not more than 100). The next N lines contain exactly M characters in each — labyrinth map. The symbol * (asterisk) denotes a cell surrounded by mirrored walls, . (dot) — empty cell, symbol X (capital Latin letter X) — the cell in which the traffic light is located (there is exactly one such cell).

Imprint
In the output file print N lines with M characters in each — image of a labyrinth with trajectories of rays. Here, as before, * (asterisk) should denote cells surrounded by mirrored walls, . (dot) — empty cells through which light rays do not pass, / (slash) — cells through which the beam of light passes from the lower left corner to the upper right (or back — from the upper right to the lower left), \ (backslash) — the cells through which the ray passes from the upper left corner to the lower right (or vice versa), and the symbol X (capital Latin letter X) — cells through which rays pass along both diagonals.

Examples

3 5
X....
.....
.....

XXXXX
XXXXX
XXXXX

3 3
...
..X
...

/X\
X.X
\X/

ID 38377. Flag

Innokenty works at a flea market, selling all sorts of rubbish and unusual things to visitors. Recently, he found an old rectangular bedspread in his warehouse. As it turned out, this blanket has a mesh shape, that is, the blanket consists of nm colored patches, divided into n rows and m columns.

The colored shreds attracted the attention of Innokenty, and he immediately figured out how to make money on his find. If you cut out a sub-rectangle from the bedspread, consisting of three colored stripes, then this sub-rectangle can then be sold as the flag of some country. In particular, Innokenty believes that the subrectangle will be sufficiently similar to the flag of some country if it consists of three same-color stripes of the same height, located one under the other. Of course, the color of the upper strip must not match the color of the middle strip, and the color of the middle must not match the color of the bottom.

Innokenty does not yet know from which part of the bedspread he will cut the flag, but he definitely decided that he would cut the flag only along the lines of the grid, while the bedspread should in no case be rotated. Help Innokenty and count the number of different sub-rectangles that can be cut out of the bedspread and sold as a flag. Subrectangles that form the same flags, but the covers located in different places, are considered different.



Input
The first line contains two integers n and m (1 ≤ n, m ≤ 1000 ) — the number of rows and columns in the bedspread.

Each of the next n lines describes the next line of the veil and consists of m lowercase Latin letters from « a " to « z », where the same colors correspond to the same letters, and different colors — different letters.

Imprint
In a single line print a single integer — the number of subrectangles that are flags.

Note

Examples

ID 38471. Hyper minimum

You have a 4-dimensional array X, each index of which can take values ​​from 1 to N. You must construct a new 4-dimensional array Y , whose elements must take the following values: Y [i₁, i₂, i₃, i₄] = min(X[j₁, j₂, j₃, j₄]), where 1 ≤ i_k ≤ N .minus; M + 1, i_k ≤ j_k ≤ i_k + M − 1 and M -  given number.

Input
The first line of the input file specifies N and M (1 ≤ M ≤ N). The remaining lines of the file contain the elements of the array X. The number of elements will not exceed 1500000 and they themselves will be integers not exceeding 10⁹ in absolute value. They are in such order that you can read them using pseudocode:

for i = 1 to N:
for j = 1 to N:
for k = 1 to N:
for l = 1 to N:
read X[i, j, k, l]

Imprint
Output the required array Y in the same format as the array X was given.
 

Examples

ID 38434. Game with chips

You are one of the developers of a new computer game. The game is played on a rectangular board consisting of W×H cells. Each cell can either contain or not contain a chip (see picture).
An important part of the game is to check if two pieces are connected in a way that satisfies the following properties:
1.    The path must consist of segments of vertical and horizontal straight lines.
2.    The path must not cross other tokens.
In this case, part of the path may be off the board. For example:

Examples

5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0

4 4
XXXX
.X..
..X.
X...
1 1 3 1
0 0 0 0

ID 38796. Competitions

There are n athletes competing in the hammer throw. Each of them made m throws. The winner is determined by the best result. Determine the number of contestants who shared first place, that is, determine the number of rows in the array that contain the highest value.

Input
The program receives as input two numbers n and m, which are the number of rows and columns in the array. Next, the input stream contains n lines of m numbers each, which are elements of the array.

Imprint
The program should output  one number - the number of winners of the competition.

 Examples

ID 38836. Multiplication table

Two numbers n and m are given. Create a two-dimensional array A[n][m], fill it with the multiplication table A[i][j]=i*j and display it on the screen. In this case, nested loops should not be used, the entire filling of the array must be done in one loop.
Input
The program receives as input two numbers n and m – the number of rows and columns, respectively.

Imprint
The program should output  the resulting array. Separate numbers with one space.
 

Examples

ID 38842. Pascal's triangle

Two numbers n and m are given. Create a two-dimensional array of dimension  nxm and fill it according to the following rule:
- numbers in row 0 or column 0 are equal to 1 (A[0][j]=1, A[i][0]=1);
- the values ​​of the remaining elements of the array must be equal to the sum of the elements one column to the left and one line above this element. 

Input
The program receives two numbers n and m as input.

Imprint
Display the resulting array.
 

Examples

3 3

1 1 1
1 2 3
1 3 6

ID 38875. Spiral

The robot moves along the checkered plane and draws a spiral. Initially, it is in cell (0, 0) and is directed towards increasing the first coordinate.
Then it acts according to the following algorithm: it makes d moves forward, then it turns left and again makes d moves forward. After that, it turns  to the left and multiplies the value of d by k. The robot then repeats the described process. The robot stops after a total of exactly n moves.
It is required to display a picture showing the cells visited by the robot.

Input
The input is integers n, d and k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

Imprint
Let the minimum rectangle of cells containing all the cells visited by the robot have height h and width w. On the first line print the numbers h and w separated by a space. The next h lines should contain w characters each, print "*" for the cell visited by the robot and "." for the unvisited.

Examples

5 5
*****
*...*
*.***
*....
**...

ID 33220. Matrices. Introduction

Declare in the program three matrices with initial values
        - a 5 by 6 matrix A, in which the first element of each row is equal to the row number, the remaining elements of the row are zeros
        - matrix B  size  10 by 10 filled with zeros
        - a 2 by 2 matrix C, where each element is equal to the sum of the row number and the column number

ID 27171. Zlatopolsky 12.5

Input
The first line contains the number of rows (1<=N<=20) and the number of columns (M 1<=M<=20) of the two-dimensional array separated by a space.
Next comes N lines with M elements per line - the elements of a two-dimensional array. All elements of a two-dimensional array modulo does not exceed  50.
Next comes the number k (1<=k<=N) 

Imprint
Display the kth line on the screen (assuming that the numbering of the array elements starts from 1, i.e. k=1 for the first line).
Display all elements on one line with 1 space between elements

ID 27170. Zlatopolsky 12.3

Input
The first line contains the number of rows (1<=N<=20) and the number of columns (M 1<=M<=20) of the two-dimensional array separated by a space.
Next comes N lines with M elements per line - the elements of a two-dimensional array. All elements of a two-dimensional array modulo does not exceed  50.
Then, separated by a space, there are two numbers k and h (1<=k<=N, 1<=h<=M) 

Imprint
Display the element located at position h in string k (assuming that the numbering of array elements starts from 1, i.e. for the upper left element of the array, it is considered that k=1 and h=1).

ID 27169. Zlatopolsky 12.2b

Input
The first line contains the number of rows (1<=N<=20) and the number of columns (M 1<=M<=20) of the two-dimensional array separated by a space.
Next comes N lines with M elements per line - the elements of a two-dimensional array. All elements of a two-dimensional array modulo does not exceed  50.

Imprint
Display the element located in the upper left corner.

ID 27168. Zlatopolsky 12.2a

Input
The first line contains the number of rows (1<=N<=20) and the number of columns (M 1<=M<=20) of the two-dimensional array separated by a space.
Next comes N lines with M elements per line - the elements of a two-dimensional array. All elements of a two-dimensional array modulo does not exceed  50.

Imprint
Display the element located in the lower right corner.

ID 27167. Zlatopolsky 12.1b

Input
The first line contains the number of rows (1<=N<=20) and the number of columns (M 1<=M<=20) of the two-dimensional array separated by a space.
Next comes N lines with M elements per line - the elements of a two-dimensional array. All elements of a two-dimensional array modulo does not exceed  50.

Imprint
Display the element located in the lower left corner.

ID 27166. Zlatopolsky 12.1a

Input
The first line contains the number of rows (1<=N<=20) and the number of columns (M 1<=M<=20) of the two-dimensional array separated by a space.
Next comes N lines with M elements per line - the elements of a two-dimensional array. All elements of a two-dimensional array modulo does not exceed  50.

Imprint
Display the element located in the upper right corner.

ID 7118. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 7117. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 7116. Error

Given a natural number N (N<=15). Fill and display a square two-dimensional array of size NxN according to the following rule:

1 0 0 0 0 
1 1 0 0 0 
1 1 1 0 0 
1 1 0 0 0 
1 0 0 0 0 

Examples

1 0 0 0 0 
1 1 0 0 0 
1 1 1 0 0 
1 1 0 0 0 
1 0 0 0 0 

ID 23073. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 23072. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 7115. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 7114. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 7113. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 7112. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:
- the numbers on the diagonal going from the lower left to the upper right corner are equal to 1; 
- numbers below this diagonal are 0;
- numbers above this diagonal are 2.

Each element of the array is separated from another by one space, each line of the array is displayed on a new line
Sample Input and Output

ID 7111. Error

A natural number N is given (N<=15). Fill and display a square two-dimensional NxN array according to the following rule:

ID 37092. 12.41

The two-dimensional array stores information about the salary N of a person for each of the 12 months of the year (the rows contain information about people, the columns contain information about months). Write a program to calculate the total amount paid to employees for the K-th month of the year (months are numbered from 1).

Input  
The first line contains the number N (0< N <= 25). Followed by N lines of 12 numbers each (each number is a natural number, no more 150). The last line is a number K (1 <= K <= N).

Imprint 
Display the answer to the problem.

Examples

ID 37091. 12.39

There are N rows in the auditorium, each of which has M seats (seats). Information about tickets sold is stored in a two-dimensional array, row numbers correspond to row numbers, and column numbers correspond to seat numbers. If a ticket is sold for one seat or another, then the corresponding element of the array has the value 1, otherwise it has the value 0. Write a program that determines the number of sold tickets for seats in the Kth row.

Input: The first line contains two numbers N (0<N<=15) and M (0<M<=25)
Next come N lines of M numbers each (each number is 0 or 1)
The last line contains the number K (1<=K<=N)
Output: print the answer to the problem

Examples

ID 37090. Processing a row in a matrix - 3

The two-dimensional array stores information about the scores obtained by pentathletes in each of the five sports (in the zero line - information about the scores of the first athlete, in the first - the second, etc.). The total number of athletes \(N\). Determine the total points scored by the \(K\)th athlete.

Input: The first line contains a number \(N\) (\(0<N<=20\)). 
Next come N lines with 5 numbers each - the points received by the athletes (each number is a natural number, not more than 50)
The last line specifies a number \(K\)
Output: display the answer to the problem

Examples

ID 37097.

In the theatre there are N rows, each of which has M seats (seats). Information about the tickets sold is stored in a two-dimensional array, the line numbers of which correspond to the row numbers, and the column numbers to the seat numbers. If a ticket for a particular place is sold, then the value 2 is written to the array, if it is booked - 1, otherwise - 0. Identify the places that are most often booked and / or bought by the audience.

Input data: the first line sets the numbers N and M (0 <= N, M <= 25)
Next comes N lines of M numbers in each. Each number can be 0, 1 or 2
Output: display the numbers of all places (in one line, after one space), which are sold or booked most often.

Example:

ID 37095.

In the theatre there are N rows, each of which has M seats (seats). Information about the tickets sold is stored in a two-dimensional array, the line numbers of which correspond to the row numbers, and the column numbers to the seat numbers. If a ticket for a particular place is sold, then the value 2 is written to the array, if it is booked - 1, otherwise - 0. Identify the places that are most often booked and / or bought by the audience.

Input data: the first line sets the numbers N and M (0 <= N, M <= 25)
Next comes N lines of M numbers in each. Each number can be 0, 1 or 2
Output: display the numbers of all places (in one line, after one space), which are sold or booked most often.

Example:

ID 37094. 12.98a

Information about the number of residents in each of the M apartments of each floor of a 12-storey building is stored in a two-dimensional array (in the zero line - information about the apartment on the first floor, in the first - on the second, etc.). Determine on which floor the least number of people live. Print this number and the numbers of all such floors.

Input:  number M is given in the first line (0<M<=25)
Then there are 12 lines of M numbers each (an integer not exceeding 10)
Output:

Examples

ID 37093. 12.98b

Information about the number of residents in each of the M apartments of each floor of a 12-storey building is stored in a two-dimensional array (in the zero line - information about the apartment on the first floor, in the first - on the second, etc.). Determine on which floor the most people live. Print this number and the numbers of all such floors.

Input:  number M is given in the first line (0<M<=25)
Then there are 12 lines of M numbers each (an integer not exceeding 10)
Output:

Examples

ID 6031. Finding the required string - 2

 n athletes compete in the hammer throw. Each of them made  m throws. The player with the highest throw wins. If there are several of them, then the one with the best sum of results over all attempts wins. If there are several such, the athlete with the lowest number is considered the winner. Determine the number of the winner of the competition.

Input: The program receives as input two numbers n and m (20<=n,m<=20), which are the number of rows and columns in the array. Next in the input stream are n lines of m numbers, which are elements of the array.

Output data: The program should output a single number - the number of the winner of the competition. Don't forget that  lines  (athletes) are numbered from 0.

ID 23390. Under the side diagonal

Given a two-dimensional array of size nxn (n<=10). Form a one-dimensional array from the elements of the given array located under the secondary diagonal.

Input 
The program receives as input the number n <= 10, which is the number of rows and columns in the array. Next, the input stream contains n lines of n numbers that are elements of the array.
 

Imprint 
The program should output a one-dimensional array, the elements of which are the values ​​of the two-dimensional array elements (separated by a space), located UNDER the secondary diagonal.
 

Examples

ID 23389. Under the main diagonal

Given a two-dimensional array of size  nxn (n<=10). Form a one-dimensional array from the elements of the given array located under the main diagonal.

Input 
The program receives as input the number n <= 10, which is the number of rows and columns in the array. Next, the input stream contains n lines of n numbers that are elements of the array.
 

Imprint 
The program should output a one-dimensional array, the elements of which are the values ​​of the two-dimensional array elements (separated by a space), located UNDER the main diagonal.

Examples

ID 23388. Above the side diagonal

Given a two-dimensional array of size nxn (n<=10). Form a one-dimensional array from the elements of the given array located above the secondary diagonal.

Input 
The program receives as input the number n <= 10, which is the number of rows and columns in the array. Next, the input stream contains n lines of n numbers that are elements of the array.

Imprint 
The program should output a one-dimensional array whose elements are the values ​​of the two-dimensional array elements (separated by a space) located ABOVE the secondary diagonal.  

Examples

ID 23387. Above the main diagonal

Given a two-dimensional array of size nxn (n<=10). Form a one-dimensional array from the elements of the given array located above the main diagonal.

Input  
The program receives as input the number n <= 10, which is the number of rows and columns in the array. Next, the input stream contains n lines of n numbers that are elements of the array.

Imprint
 The program should output a one-dimensional array whose elements are the values ​​of the two-dimensional array elements (separated by a space) located ABOVE the main diagonal.

Examples

ID 42441. Third planet from the Sun

n spaceships have been sent to the third planet from the Sun to collect various objects for study. Each ship carried m containers of various sizes. After studying the planet, n·m instances were selected. The command staff decided to take several copies of the largest volume. It is necessary to determine what volume the largest instance must have so that it can be taken out of the planet, as well as the number of ships and their numbers on which the largest instances can be placed. All ships are numbered starting from zero.

Input
The first line contains two integers n and m: n is the number of ships sent to the third planet (1 <= n <= 100 ), m - the number of containers on each ship. The following n lines contain m numbers, each of which shows the volume of the container (1 <= m <= 100, each number is non-negative no more than 100).  

Imprint
Print in the first line - the number of spaceships that can bring the largest copy, separated by a space - the maximum amount that can be taken from the planet. On the next line print space-separated numbers of ships (numbered from zero) on which the largest copy can be loaded.
 

Examples

3 3
1 2 3
3 5 4
5 2 2

25
1 2

ID 42449. Spiral filling

Given a number n. Create an array A[2*n+1][2*n+1] and fill it in a spiral, starting with the number 0 in the center cell  ;A[n+1][n+1]. The spiral goes up, then twists counterclockwise.

Input
The program receives a number as input  n.

Imprint 
The program should output the resulting array, using exactly 3 characters for each number.
 

Examples

 12 11 10 9 24
 13 2 1 8 23
 14 3 0 7 22
 15 4 5 6 21
 16 17 18 19 20

ID 22012. maximum line

ID 44602. 2D vector

Create a two-dimensional array of size n×m and fill it with natural numbers from 1 to n >xm vertically (see example).

Input

Two natural numbers are given: n and m, not exceeding 10¹⁰.

Output

Output a filled two-dimensional array

 

Examples

3 4

1 4 7 10
2 5 8 11
3 6 9 12

ID 44616. saddle point

Saddle point – is the element of the matrix that is both the largest in its column and the smallest in its row. Write a program that finds the indices of all saddle points of a matrix. The numbering of rows and columns of the matrix starts from one.

The first line contains space-separated dimensions of a rectangular matrix N and N (number of rows and number of columns, 1  <=  ;N, M <=  100). The following N lines contain matrix rows, each – by M natural numbers separated by spaces.
 

The program should output the indexes of all saddle points of the matrix in row order (top to bottom, left to right). The row number and column number of each saddle point are separated by spaces. The numbering starts from one. If there is no saddle point in the matrix, you need to print the number 0.

Examples

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
9 17 18 19 20

3 1

ID 44617. Sorting strings

Write a program that rearranges the rows of a matrix so that the values ​​in the K column are in descending order. Rows whose values ​​in the  K column are equal must be output in the same order in which they were in the original matrix.
 

The first line contains space-separated dimensions of the matrix: the number of rows N and the number of columns M ( 1 <= N  ;, M <= 100 ). The following N lines contain matrix rows, each – by M natural numbers separated by spaces. The last line is the column number K .
 

The program should output the resulting matrix, in which the rows are rearranged so that the values ​​in the K column are in descending order.
 

Examples

4 5
21 22 23 24 25
26 12 18 29 33
11 37 31 14 39
16 17 18 5 20
1

26 12 18 29 33
21 22 23 24 25
16 17 18 5 20
11 37 31 14 39

ID 44618. Color conversion

The brightness of the pixels in the picture is encoded with numbers from 0 to 255 in the form of a matrix. Convert the picture to black and white using the following algorithm:

4 4
12 14 67 45
32 87 45 63
69 45 14 11
40 12 35 15

37.8750
0 0 255 255
0 255 255 255
255 255 0 0
255 0 0 0

ID 44677. Theater visit

Students of the theater club of the school love to visit the theater. Once again, they went to the theater, in which n rows of m seats in each. The leader of the circle came for tickets and wants to buy tickets for all students in the same row to the adjacent seats. 
Based on the available information about the sold tickets for the performance, determine whether the leader will be able to buy tickets for all students and himself in the same row. 
Information about sold tickets is stored in a two-dimensional array (ones mean that a ticket is sold for a given seat, zero means that a seat is free). The leader of the circle together with the children needs k tickets.

The first line of the input contains numbers n, m, k <= 100. In the following n lines of the input, the m numbers (0 and 1) separated by spaces.

Print YES or NO depending on the answer to the problem question.

Examples

3 4 2
0 1 0 1
1 0 0 1
1 1 1 1

YES

ID 44711. Queen's Journey

Alice often plays chess. Moreover, since she loves to travel to other galaxies, she knows many varieties of this ancient game.  Sometimes she just solves puzzles created on the chessboard.  Alice's chessboard can have a variety of sizes, not just 8×8.

4 4 7
10 20 0 100
30 0 0 40
0 0 0 0
45 42 0 70

1 2 0 8
3 0 0 4
0 0 0 0
6 5 0 7

2 4 4
10 20 30 40
0 50 0 0

Wrong Board

2 2 2
12
4 3

Wrong Board

ID 44712. Ralph loves donuts

Thug Ralph has been living in a slot machine for 30 years, and you can see him on the screen of that machine. 
Today, Ralph is walking around a screen that displays a  rectangular image divided into N x N cells. In each cage there is a plate with his favorite pancakes & nbsp; (all plates have a different number of pancakes). Ralph starts moving from the lower left cell of the rectangle. After eating all the pancakes in the current cell, he moves one cell to the right or one cell up, always choosing the cell with more pancakes in the plate (there are no plates with pancakes outside the rectangle ). Eventually Ralph comes to the top right cell. You also have to determine how many pancakes Ralph ate while traveling around the screen. Ralph also ate pancakes in the initial and final cages with great pleasure.

The program receives an integer as input in the first line N – image size (2 <= N <= 10). The following N lines set space-separated numbers denoting the number of pancakes on the plates, starting from the top row and ending with the bottom one. All numbers – various, natural, not exceeding 100.

Print one number - the number of pancakes that Ralph will eat when he gets to the top right cell.

 

Examples

2
37 82
23 52

157

ID 44715. Parallel programming

Misha is engaged in parallel programming. Today he is writing a program for the performer "Kvadratik". Performer "Kvadratik" lives on a checkered field of size   N x M, the size of one cell is 1x1. As he moves, he paints over the cell he has visited. The cell on which he started moving and on which he stopped is also painted over. 
Misha installed on the field K "Kvadratikov". Each "Square" will move in the direction indicated by Misha and stop when he reaches the end of the field. After the movement of all "Squares" is over, Misha wants to know how many cells of the field turned out to be painted over. Since the task of counting is not related to parallel programming, and the size of the field can be very large, Misha asked you to write a program to count such cells.
 

The program takes several lines as input. The first line contains integers M and N - sizes of the "Square" artist field (1 <= M, N <= 10⁶). The second line contains the number K - the number of "Squares" on the field (0 <= K <= 10³). Then there are K lines, each of which describes the position of a certain "Square" and the direction in which it will move. The format of each of these strings is: two integers separated by one space and one character  {N, E, S< /code>, W} - initial coordinates and direction of movement of the corresponding "Square". A character is separated from numbers by exactly one space. 
The following directions of movement    N - up, S - down, W - left, E< /code> - right.

8 5
4
4 4S
6 2W
6 3 N
6 4S

13

ID 26981. error

Input

Imprint

Examples

2 0 0 0
2 0 0 0
2 0 0 0
0 0 0 0

4

2 0 0 0
2 0 0 0
2 0 0 0
2 0 0 0

8

2 2 4 0
0 0 0 0
0 0 0 0
0 0 0 0

4

2 2 4 0
0 2 2 2
0 2 4 0
2 4 4 0

16

Notes

ID 18783. Diagonals

Examples

ID 22007. Pulling out the low

Examples

ID 18788. Going for gold - 1

ID 18789. Going for gold - 2

One day the king decided to reward one of his wise men for a good job. He led him into a rectangular room measuring NxM, in each cell of which lay several kilograms of gold. The king allowed the sage to go around several cells (moving from the cell where the sage is now to one of the four neighboring cells) and collect all the gold that gets in his way.
A sage is allowed to pass over the same square more than once. At the same time, he takes gold from it  only once - when he passes through the cell for the first time.

You are given the route of the sage. It is required to determine how many kilograms of gold he collected.

Input
The input data contains the plan of the room and the route of the sage. First, the number of rows N, then the number of columns M (1<=N<=20,1<=M<=20).
Then N lines are written with M numbers in each - the number of kilograms of gold that lies in this cell (a number from 0 to 50).
Next, the number X is written - how many cells the sage walked around. Next, the coordinates of these cells are recorded (the coordinates of a cell are two numbers: the first determines the row number, the second determines the column number, the upper left cell on the plan has coordinates (1,1), the lower right one - (N,M)). 

ID 22014. Going for gold - 3

Examples

ID 44942. The sum of positive and negative

Given a two-dimensional array A with dimension NxM. Write a program that adds to the elements of each row such a new element that the sum of the positive elements of the string becomes equal to the modulus of the sum of the negative elements of the string.

Input
The first line of the input contains two space-separated natural numbers N and M ( 0 < N, M <= 25). Next come N lines of M positive integers in each - elements of the matrix A (each element of the matrix does not exceed 10<sup>5< /sup>).

Imprint
Display the resulting array A of dimension Nx(M+1) on the screen. All elements of a line must be separated by a single space.</sup>
 
 

Examples

ID 45716. Main diagonal sort

Write a program that rearranges the elements of a square matrix located on the main diagonal in ascending order. The remaining elements of the matrix should remain in place.
 

The first line contains a single number N the size of a square matrix ( 1 <= N <= 100 ). The following N lines contain matrix rows, each – by N natural numbers separated by spaces. 
 

The program should output the resulting matrix, in which the elements of the main diagonal are arranged in ascending order.
 

Examples

5
1 11 11 5 10 
2 9 2 10 2 
12 9 10 9 15 
6 15 14 1 11 
11 12 4 9 3 

1 11 11 5 10 
2 1 2 10 2 
12 9 3 9 15 
6 15 14 9 11 
11 12 4 9 10

ID 45241. Sort by sum of digits

Given an array of integers. Sort the array by non-increasing sum of digits of each number. If the sum of the digits of two numbers is equal, the numbers must follow in descending order.

Input
The program receives as input in the first line a natural number n - the size of the array. The second line contains n integers ai - array elements (1 <= n <= 103, 1  ;<= ai <= 104).

Imprint
Output the resulting array.
 
 

Examples

ID 45717. Side diagonal sort

Write a program that rearranges the side-diagonal elements of a square matrix in descending order, starting from the upper right corner. The remaining elements of the matrix should remain in place.
 

The first line contains a single number N the size of a square matrix ( 1 <= N <= 100 ). The following N lines contain matrix rows, each – by N natural numbers separated by spaces. 
 

The program should output the resulting matrix, in which the elements of the main diagonal are arranged in ascending order.
 

Examples

5
12 4 8 13 13 
1 12 1 4 15 
2 3 5 2 3 
6 5 13 12 14 
14 9 15 4 12 

12 4 8 13 14 
1 12 1 13 15 
2 3 5 2 3 
6 5 13 12 14 
4 9 15 4 12

ID 45719. Sorting a two-dimensional array

Write a program that sorts a two-dimensional array of integers. In this case, the smallest number should be in the first element of the first line, and the largest in the last element of the last line.

The first line contains space-separated dimensions of a two-dimensional array: the number of rows N and the number of columns M ( 1 <=  N , M <= 100 ). The following N lines contain the strings of a two-dimensional array, each – by M natural numbers separated by spaces. 
 

The program should output a sorted two-dimensional array.
 

Examples

5 6
13 5 1 8 4 14 5 
5 13 10 9 3 7 7 
3 3 9 6 3 7 5 
10 8 11 2 1 1 13 
1 12 13 15 9 11 4 

1 1 1 1 2 3 3 
3 3 4 4 5 5 5 
5 6 7 7 7 8 8 
9 9 9 10 10 11 11 
12 13 13 13 13 14 15