You are hereProgramming Problems / 2017 AIPO National Finals Problems

2017 AIPO National Finals Problems


By admin - Posted on 09 March 2017

Problem 1: Piratesarrghh.jpg

Pirates talk a funny way. They say word where the letters are repeated more than they need to be. We would like know which letter appears the most frequently in a Pirate word.

For example: In the word “arrrrrghh”, the letter “r” appears 5 times while “h” appears twice.

Write a program that reads a pirate word from the terminal and writes the letter that occurs most frequently.

It is guaranteed that only one letter is the most repeated. That is, words like “aipo” won’t appear because no single letter wins.

Input

The input will consist of two lines.

The first line will contain the size of the word and the second the word to process.

The word will only contain lowercase letters from a to z. The size of the word will be at most 1000 characters. No spaces or other symbols will appear.

Output

Print a single line with the character that appears the most and the number of occurrences.

 

Example 1

Input

10

arrrrrrghh

Output

r 6

Example 2



Input

9

shhhiiver

Output

h 3

Example 3



Input

20

oxlbelhfikrzxcgxpfcy

Output

x 3

 

Problem 2: Password check

Dublin City University wants to prevent students and staff from using weak passwords. The Security Department has commissioned you to write a program that checks that some passwords meet all the quality requirements defined by the Password Guidelines Council.

These requirements are as follows. A password is considered strong enough if it has the following properties:

  • At least one lowercase letter.

  • At least one uppercase letter.

  • At least one digit

  • At least one symbol from the set +_)(*&^%$#@!./,;{}

  • Minimum length is 12.

Examples:

  • The password “Aa1_” (without the quotes) meets the first 4 requirements but its length is less than 12.

  • The password “Aa1234567890_” is perfectly fine.

Input

You’ll have to process a batch of password in every test case.

The first line will contain an integer N with the number of passwords to process.

Each password will be presented in two lines. The first line will contain an integer S with the size of the password. The next line will contain a sequence of S characters, the password to check.

 

The password will only contain the letters from a to z (both lowercase and uppercase) the digits from 0 to 9 and the following symbols: “+_)(*&^%$#@!./,;{}” without the quotes.

The maximum size of a password will be 30 characters. Each test case will contain at most 100 passwords to process.

Output

For each password write a line with the word “valid” if the password meets that quality requirement or “invalid” otherwise.

 

Example 1



Input

2

4

Aa1_

13

Aa1234567890_

Output

invalid

valid

Example 2



Input

5

18

UtQ.iNlLgT;{f,.GR!

29

yr)Z,pHQ+No,ZfP_z12D2l1*MSTfk

23

.p7hV/Es^aahW%B.1JJouO;

9

c7V!*$1lW

26

a^pBAAxCohQlBv7qDpVeOB%Min

Output

invalid

valid

valid

invalid

valid

 

 

Problem 3: Paint bucket

One of the most time-saving operations when drawing on a computer (for example using Photoshop) is the “bucket fill”  operation.

 

When you select this tool and click on a (target) pixel of the image it will fill all the pixels that have the same color than the target pixel and are connected to it. Two pixels are connected if they share a side or if they are connected through a path of connected pixels.

 

Let’s see an example: In the following image, if we select the “fill” operation in an image editor program and click on the center of the image (orange pixel). The whole region will be painted orange. Notice that the pixels are not connected diagonally so two corners of the image remain white.

 

 

Your task is: Given a matrix of digits representing the pixels, simulated what would be the result of a “fill” operation on given pixels. Thus, the colors will be represented with a number from 0 to 9.

 

Let’s see another example, now using digits instead of pixels. We have the following image:

 

0000000

0111000

0111010

0000000

 

If we “fill” at position Y = 0, X = 0 with color 3, all the 0s get painted of color 3. Because all of them are recursively connected.

 

The result will be:

 

3333333

3111333

3111313

3333333

 

Input

The first line will contain two integers R and C representing the number of rows and columns of the image.

The next R lines will contain C digits each representing the initial colors of the pixels.

The last line will contain 3 integers Y, X and K representing the row and column where we want to apply the “fill” operation and the color to use.

The images will be smaller than 1000 x 1000 pixels.

The colors are limited to a single digit from 0 to 9.

Output

Print the resulting image after applying the operation in the same format as the input.

Example 1



Input

4 7

0000000

0111000

0111010

0000000

0 0 3

Output

3333333

3111333

3111313

3333333

Example 2



Input

9 9

000000000

011101110

011101110

011011110

000111000

011110110

011101110

011101110

000000000

4 4 2

Output

000000000

011102220

011102220

011022220

000222000

022220110

022201110

022201110

000000000

 

 

Problem 4: Counting paths

Every afternoon, Jack runs from his house to John's. Their houses are in an open field of size N x M. Jack is trying to use a different path each day but he is not sure how many different ways to reach John's house exist.

 

We will represent the field using a grid of N rows and M columns like the following:

 

....
..X.
....

Jack lives in the top-left position and John in the bottom-right. Jack wants to use a different route every day but does not want to waste time he will only walk down and/or right. Also, some parts of the fields have obstacles such as rocks or houses and Jack cannot go through them (they are marked with an X in the grid).

In the previous field, the 4 valid routes are:





****
..X*
...*
*...
*.X.
****
*...
**X.
.***
**..
.*X.
.***

Notice that all the valid routes will always have the same length (N + M - 1).

The number of possible paths can be very large so print the result modulo 1000000007 (10^9 + 7).

Input

The first line will contain two integers N and M. The rows and columns of the map.

Each of the following N lines will contain M characters. If the character is a dot (.), this position is empty. If the character is an X, it means that there is an obstacle and Jack cannot use this cell.

The top-left and bottom-right cells will never have an obstacle on them.

Limits

2 <= N <= 200

2 <= M <= 200

 

Output

Print the number of possible path between the top-left and bottom-right positions. Remember to print the result modulo 1000000007.

In most languages the modulus operator is %.

 

Examples



Input example 1

3 4

....
..X.
....

Output example 1

4

Input example 2

3 3

.X.
X..
...

Output example 2

0

Input example 3

5 5

.....
.....
.....
.....
.....

Output example 3

70

Input example 4

30 20

....................
....................
....................
....................
....................
....................
....................
....................
....X...............
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
............X.......
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................

Output example 4

833886024

Note that the actual result is 6768833933400 but we need to print the value modulo 1000000007 and 6768833933400%1000000007 equals 833886024.

 

Problem 5: Knight

In Chess, the knight is the weirdest of all the pieces. To begin with, the piece is actually a horse without any human riding it. The second reason is its movement pattern. It can move 2 cells forward and one to the side. Below you can see all the possible destinations of a knight.

 



With a movement pattern so weird, it is complicated to know what’s the shortest path between two board squares. Can you write a program that computes the minimum number of movements needed to move a knight from one square to another? Remember that a chessboard has 8 rows and 8 columns. Also in the standard notation, the columns are represented by letters from a to h.

Input

The input will contain 2 lines. The first line will be the starting position of the knight and the second line will specify its final position.

 

Output

Output a single integer specifying the minimum number of moves for the knight to get from it’s starting position to it’s final position on the board.

 

Examples



Input

h1

a8

Output

6

Input

b1

b1

Output

0

Input

e2

e4

Output

2

 

Problem 6: Tiling

Domino tiles (or dominoes) are rectangular pieces of size 2x1. Each square contains a number from 1 to 6. These pieces are used to play a game but in this problem we are going to use them for something different.

 

We can build rectangles of certain width W and height 3 using dominoes. We are wondering how many ways of creating such rectangles are possible.

Below you can see the three possible ways of creating a rectangle of width 2 and height 3.

As you see there are many ways of tiling the rectangle. For example this is a possible solution with width 12:

Your task is to write a program that computes the number of possible ways of tiling a rectangle of width W and height 3.

 

Input

A single line with an integer W. The width of the rectangle.

The value of W will be between 1 and 1000.

 

Output

A single line with the number of possible ways. The numbers can be large so print the solution modulo 1000000007 (109 + 7).

 

Examples



Input

2

Output

3

Input

8

Output

153

Input

30

Output

299303201

Input

3

Output

0

Input

56

Output

485646032

In the last test case, the actual result is 8155103542731753 by we have to print it modulo 109 + 7.

 

Problem 7: Debug

Seán is trying to debug a piece of his code. First he creates an array of N integers and fills it with zeros. Then he repeatedly calls the following procedure which he has written in C++:

 

void something( int jump ) {

 int i = 0;

 while( i < N ) {

   seq[i] = seq[i] + 1;

   i = i + jump;

 }

}

As you can see, this procedure increases by one all elements in the array whose indices are divisible by jump.

Seán calls the procedure exactly K times, using the sequence X1 X2 X3 ... Xk as arguments.

After this, Seán has a list of Q special parts of the array he needs to check to verify that his code is working as it should be. Each of this parts is defined by two numbers, L and R (L R) the left and right bound of the special part. To check the code, Seán must compute the sum of all elements of seq between and including L and R. In other words seq[L] + seq[L+1] + seq[L+2] + … + seq[R]. Since he needs to know the answer in advance in order to check it, he asked you to help him.

Input

The first line of input contains two integers, N (1 ≤ N ≤ 106), size of the array, and K (1 ≤ K ≤ 106 ), number of calls to something Seán makes.The second line contains K integers: X1 X2 X3 ... Xk , arguments passed to the procedure. (1 ≤ Xi < N).

Next line contains one integer Q (1 ≤ Q ≤ 106), number of special parts of the array Seán needs to check.

Next Q lines contain two integers each Li and Ri (0 ≤ LiRi < N), bounds of each special part.

Output

The output should contain exactly Q lines. The ith line should contain the sum of the elements seq[Li] + seq[Li +1] + seq[Li +2] + … + seq[Ri].

 

Examples




Input Example 1

10 4

1 1 2 1

3

0 9

2 6

7 7

Input Example 2

11 3

3 7 10

3

0 10

2 6

7 7

Input Example 3

1000000 6

12 3 21 436 2 19

2

12 16124

692 29021

Output Example 1

35

18

3

Output Example 2

8

2

1

Output Example 3

16422

28874

Example 1 description: The procedure is called with arguments 1, 1, 2, 1. After that the array contains values {4, 3, 4, 3, 4, 3, 4, 3, 4, 3}. Sum of indices 2 to 6 (inclusive) is 4+3+4+3+4 = 18.

Example 2 description: After the procedure calls, the array is {3, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}.

 

Problem 8: Boom!

Tadhg has found an interesting tape in his school chemistry lab. The tape is divided into N segments of equal length, and can easily be bent between two segments, but only by exactly 180 degrees.

 

One side of the tape is completely covered with a very volatile chemical. If the chemical comes in contact with itself, it reaches critical mass and explodes.

 

The other side of the tape is not completely covered yet. Only the first A segments and last B segments are covered, with the exact same chemical.

 

Write a program that will calculate the number of different ways Tadhg can bend the tape so that it does not explode. He can bend the tape more than once and two ways are different if there is at least one bevel between segments that is not bent in one and is bent in the other.

Since the solution can be huge, print the result modulo 10301.

The following example illustrates all 6 possible ways for N=4, A=1 and B=1. For clarity, the tape is only bent 90 degrees on the illustration. Tadhg would actually bend it 180 degrees.

kaboom-example.png

Note: The unbent stage counts as 1 position

 

Input

The first and only line of input contains three natural numbers N, A and B (A>0, B>0, A+BN ≤ 1000), total number of segments, number of covered segments from the left and from the right respectively.

 

Output

The first and only line of output should contain the number of possible ways to bend the tape modulo 10301.

 

Examples




Input Example 1

4 1 1

Input Example 2

5 2 2

Input Example 3

6 1 2

Output Example 1

6

Output Example 2

1

Output Example 3

7