Dynamic Table Programming

ID 31781. Pawn game

There is a pawn in the lower left cell of the NxN chessboard. Two players take turns moving it, and each player can move it one space up or one space to the right. The numbers a₁, a₂, …, a_N are written on the diagonal of the board. When the pawn hits the diagonal, the game ends and the payoff of the first player is equal to the value of the number written in the square with the stopped pawn. Write a program to determine the guaranteed payoff of the first player.

ID 38350. Determine the winner

Vasya and Petya are playing the following game. They take a deck of 36 cards. Each card has a number from 1 to 9 written on it and each card is colored in one of 4 colors so that there are exactly 9 cards of each color and they are numbered from 1 to 9. The cards are shuffled and 18 cards are dealt to the players.

Then the players take turns making moves. In one move, a player can put one card on the table according to the following rules. The card with the number 5 can be laid out on the table at any time. A card with a different number can be laid out only if a card of the same color has already been laid out on the table, on which a number is written 1 more or 1 less than on this card (it does not matter whether this card was laid out by you or your opponent, and whether it was placed on the previous move or earlier). If a player can lay out at least some card, he must make a move. If a player cannot lay out a single card, he skips a turn.

The first person to put all their cards on the table wins.

Write a program that, based on information about who got what cards, determines who will win if both players play optimally.

Input
The input file contains 18 pairs of numbers describing the cards that the first player got. Each card is described by two numbers — color number (from 1 to 4) and the number that is written on the card (from 1 to 9). The second player, respectively, got all the other cards.

Imprint
In the output file print a single number (1 or 2) — the number of the player who will win if both players play optimally.
 

Examples

ID 38472. Energetic turtle

Given a grid with N + 1 rows and M + 1 columns. The turtle is on cell (0, 0) and wants to get to cell (N, M). The turtle can only go up or to the right. There are traps in K cells on the grid. If the turtle goes to one of these cages, it will roll over. The turtle has the strength to stand up no more than T times. Count how many different ways the turtle can get into the cage (N, M). Since this number can be very large, print the remainder after dividing it by Z.

Input
The first line of the input file contains 5 integers: N, M, K, T and Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T  20, 1 ≤ Z ≤ 10 ⁹). Each of the next K lines contains the coordinates of the corresponding cell with the trap X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). It is guaranteed that all cells with traps are different and there are no traps in cells (0, 0) and (N, M).

Imprint
Output the desired number.

Examples

ID 38477. K-th path

You have a table with N rows and M columns. Each cell of the table contains one lowercase letter of the English alphabet. Consider all possible paths from the upper left corner to the lower right corner, if you are only allowed to go to the right and down. The concatenation of letters in traversal order makes up a string. Let's say that this string is a path value. Now consider all such paths and sort their values ​​in alphabetical order. Your task is to find the value of the Kth path in this sorted list.

Input
The first line contains two integers N - the number of rows and M - the number of columns of the given table (1 ≤ N, M ≤ 30). Each of the following N lines contains exactly M lowercase letters of the English alphabet. The last line of the input file contains an integer K (1 ≤ K ≤10¹⁸). It is guaranteed that for K the answer always exists.

Imprint
The first and last line of the output file must contain one line - the answer to the problem.

Explanations for example
aefdgk, aefdgk, aefdjk, aefijk, aehijk
 

Examples

ID 38607. cute patterns

BrokenTiles plans to expand into the backyards of wealthy clients with patterns of black and white tiles, each measuring 1 x 1 meter. It is known that the yards of all wealthy people have the most fashionable for today shape of a rectangle N x M meters. However, when drawing up a financial plan, the director of this organization had two serious problems: firstly, each new client, obviously, wants the pattern laid out in his yard to be different from the patterns of all other clients of this company, and secondly, this pattern should be cute.

A study has shown that a pattern is pretty if it does not contain a 2 x 2 meter square completely covered with tiles of the same color. To draw up a financial plan, director Vasya needs to find out how many customers he can serve before cute patterns of this size run out. Help him!

Input
Enter two positive integers N and M (1 ≤ N · M ≤ 30).

Imprint
Output a single number –  number of different cute patterns that can be laid out in an N x M yard. Patterns that are made from each other by shifting, rotating or reflecting are considered different.
 

Examples

ID 38640. Number of routes in a rectangular table

In a rectangular table NxM , there is a checker in the upper left cell. In one move, it is allowed to move a checker to an adjacent cell either to the right or down (it is forbidden to move to the left and up). Count how many options there are to move the checker to the lower right cell.

Input
Two numbers N and M are entered - the dimensions of the table (1<=N<=10, 1<=M<=10).

Imprint
Output the desired number of options.

Examples

ID 38686. Binomial coefficients

For binomial coefficients (the number of combinations from n to k), the recurrent formula is well known: \(C^k_n=C^{k-1}_{n-1}+C^ {k}_{n-1}\), \(C^0_n = C^n_n=1\).
Input
Enter 2 numbers - n and k.

Imprint
You need to output  value  \(С^k_n\) .
 

Examples

ID 44037. Accelerators for Santa Claus

Santa Claus must visit N cities overnight. He has a two-dimensional plan for the location of all cities. The plan is drawn in Cartesian system of coordinates, in which point (0, 0) indicates the place where Father Frost starts. Each city on the plan is marked with a point with the coordinate  ;(Xi, Yi). Also on the map are marked M points with coordinates (Pi, Qi) , in which accelerators are located. In order to have time to deliver all the gifts, Santa Claus can use an accelerator that doubles his speed (or maybe not use it).

On New Year's Eve Santa Claus starts from the starting point, visits all N cities and returns.

Father Frost's initial speed is 1. Find the shortest time it takes for Santa Claus to visit all the cities and return back. We will neglect the time at which he lays out all the gifts!

Examples