Description

Wise found out that Belle is not doing her job managing their video store Random Play, and instead she's doing something else. Turned out Belle is actually playing a brain game called Counting Queen, but with a special twist.

You are given an N×N chessboard that already has some queens on it. The already placed queens are in different rows. Place exactly one queen in every row that does not yet contain a queen, so that no two queens on the board attack each other. Two queens attack each other if they share a row, a column, or a diagonal. We guarantee that all the initally placed queens are valid

Your mission is to help Belle count how many different ways there are to do this, so she can go back to work and stop procrastinating. Two ways are different if at least one queen is placed in a different column.

To recall, a queen in chess can move horizontally, vertically, and diagonally. We want to count all possible number of ways to place the queens on the chessboard given that there is already some pre-placed queens

In the sample, we start with a 4×4 board and a pre-placed queen at (0,1), using zero-based coordinates. In row 1, the only safe position is (1,3). With these two queens in place, the only safe position in row 2 is (2,0). Finally, the queen in row 3 must be placed at (3,2).

This arrangement places exactly one queen in each row, with no two queens sharing a column or diagonal. It is the only valid completion that preserves the pre-placed queen, so the answer is 1.

Input

• The first line contains an integer N, the size of the grid. (1 ≤ N ≤ 12)
• The second line contains an integer K, the number of pre-placed queens. (0 ≤ K ≤ N)
• Each of the next K lines contains two integers r and c, the row and column of a pre-placed queen. (0 ≤ r, c < N)

Output

Print a single integer: the number of valid ways to place a queen in each remaining row.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After building the Assembly Runner, Belle is so confident that she decided to challenge herself a little by creating a whole language of her own and even giving it a quite... exquisite name: Brainfah.

Brainfah is a very simple but Turing Complete programming language, which means it can theoretically compute any computable problem.

The language uses a simple machine model consisting of:

• An array of $30000$ memory cells, with each cell starting at zero.
• A pointer that moves left or right across the cells, starting at cell $0$.
• Eight single-character commands that manipulate the cells and pointer.
• The program will stop when it reach after the last command.

Brainfah's 8 symbols:

• >: Move the memory pointer to the next cell to the right.
• <: Move the memory pointer to the next cell to the left.
• +: Increase the value in the current cell by one.
• -: Decrease the value in the current cell by one.
• .: Output the ASCII character of the value in the current cell.
• ,: Read a character input into the current cell.    
• [: Jump forward to the matching ] if the current cell is zero.
• ]: Jump back to the matching [ if the current cell is not zero.

Example program

Example explanation

The program does the following:

• Move the pointer to the second cell
• Add $9$ to the second cell
• For each count in the second cell, add $8$ to the first cell, totalling $9*8 = 72$ count, which is the ASCII code for H
• Print the ASCII character with code in the first cell, which is $72$
• Read the input B into the second cell, which turns into $66$
• Add $1$ to the second cell
• Print the ASCII character with code in the second cell, which is $67$

 

Hints

• You can use print without adding new line characters by print(str, end="")
• You can convert a number to its ASCII character by using character = chr(number)
• You can convert a character to its ASCII number by using number = ord(character)

Input

• The first line will contain the source code for the program
• The second line will contain the input for the program. You have to append a null character \0 to the end of this input string for the program to work properly.
• All testcases will have a non-empty second line, even if the program doesn't require it.
• The program is guaranteed to be correct. It will not print out cells with negative value.

Testcases

• Testcase $1$-$3$: Programs will only contain the symbols >, <, +, -, ., , 
• Testcase $4$-$7$: No restriction.

Output

The output of the program. Do not print the new line character \n if it's not what the source code output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Clarification

The error "Restricted Function" is cause because if you keep appending an item to an array, it will reach a limit and the OJ system will cause an error.

This is mostly caused by students who put each of the queries into an array before processing them at the end. Instead, you can just get the queries and print out the output before moving on to the next query, without storing them in an array. This is fine because OJ separated the input and output system.

Another solution is to initialize the whole array beforehand and update it without using append.

Because the old way of finding Roscaelifer was too bothersome, a new way of locating this floating city was proposed.

Given an N × N matrix of integers and T queries, each query specifies a point (X, Y).

For each query, calculate the brightness of the point by adding the following four values:

1. The maximum value in row X.

2. The maximum value in column Y.

3. The sum of all elements on the top-left to bottom-right diagonal passing through (X, Y).

4. The sum of all elements on the top-right to bottom-left diagonal passing through (X, Y).

The center element A[X][Y] is included in both diagonal sums. It is also considered when finding the maximum of its row and column. These four values are added independently; do not subtract the center element.

Hint: You can use extra arrays to record information while reading the matrix, allowing you to answer each query efficiently.

 

 

Input

• An integer T, representing the number of queries (1 ≤ T ≤ 10000).
• An integer N, representing the matrix size (1 ≤ N ≤ 250).
• N lines, each containing N integers (0 ≤ A[i][j] ≤ N).
• T lines, each containing two integers (X, Y), representing a queried position (0 ≤ X, Y < N).

Coordinates use 0-based indexing

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss