Description

Given a n×m grid maze which consists of walls (#), floors (.), start (A), and end(B). You can walk in four directions: up, down, left and right, but you cannot pass the walls. Please output a path to walk from the start to the end with minimum steps, or it is impossible to go from the start to the end.

Input

The first line contains two integers n and m, being the number of rows and columns of the grid maze.

The following n lines describes the maze. Each line has m characters which is one of #, ., A, or B.

There is exactly one A and B in the input.

Restrictions

• 1 ≤  n, m  ≤ 1000

Output

If it is possible to go from the start to the end, print "YES" in the first line, the number of minimum steps in the second line.

If it is impossible, please print "NO" in the first line.

Remember there should be a ‘\n’ at the end of the last line of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Gilbert is a gardener who loves planting flowers and trees. He also enjoys using tree data structures to solve programming problems, such as segment tree and treap. However, he recently felt that programming was too exhausting and decided to focus on gardening.
By chance, he planted an "expression tree" that only operates with operations: +, -, and *. He was excited to discover that each expression tree has its own beauty value, which depends on the outcome of the expression tree's calculation mod by 998244353 (the remainder when divided by 998244353, which is the % operator in C++). For example, the beauty of the expression tree "0 * (3 - 4)" is 0 % 998244353 = 0.

As a gardener, Gilbert wants to enhance the beauty of this expression tree. He plans to do this by selecting two nodes that do not have an ancestor-descendant relationship and swapping their subtrees. Since Gilbert is lazy, he hopes to perform this swap no more than once. However, he is unsure how to swap to maximize the overall beauty of the tree. He has asked for your help and will provide you with the preorder expression of this expression tree. Please tell him the highest possible beauty of the expression tree after performing at most one swap.

Example:

Choosing to swap the subtrees of these two nodes can maximize the beauty of the tree.

About mod operation with negative number: https://math.stackexchange.com/questions/2179579/how-can-i-find-a-mod-with-negative-number

Input

The first line of the input is an integer N(3 <= N <= 500), being the length of the prefix expression of the expression tree.

The next line is the expression tree (in prefix expression). The expression contains only +, -, * and digits. All the numbers in the expression are integers between 0 and 9.

Output

Output the maximum beautify of the expression tree after performing at most one swap.

Note that you should have a '\n' in the end.

Hint:

If you have no idea how to implement, please take it as your reference.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define mod 998244353 // Define a modulo for the beauty calculation.

// Define a node structure for the expression tree.
typedef struct _Node {
    int val; // {0 ~ 9: number, -1: +, -2: -, -3: *}
    int ans;
    struct _Node *lc, *rc; // Left child, right child.
} Node;

char s[505] = {}; // Input string representing the preorder expression of the tree.
Node *arr[505] = {}; // Array to store pointers to nodes for easy access.

// Function to build the expression tree from the input string.
Node *build() {
}

// Function to evaluate the expression tree and calculate its beauty.
int eval(Node *r) {
}

// Depth-First Search function to check if target node is in the subtree rooted at 'now'.
bool dfs(Node *now, Node *target) {
}

// Function to check if two nodes have an ancestor-descendant relationship.
bool check(int a, int b) {
}

// Function to swap the subtrees rooted at nodes a and b.
void swap(int a, int b) {
}

// Main function.
int main() {
}

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have a spreadsheet and some cells are inserted with formula.  A cell without formula has initial value 0.  For example, cell B4 has formula C8 + 763 and cell B5 has value 0.

However, some cells have buggy formula.  The formula of several cells might depend on each other and results in reference error.  For example, cell A1 has formula B1 + 2, cell B1 has formula C1 + 2, cell C1 has formula A1 + 2, then the spreadsheet reports reference error.

If a cell has formula depending a cell with reference error, itself encounters reference error as well.  For example, cell C1 has reference error, cell C4 has formula C1 + 2, then C4 has reference error.

Given a spreadsheet, please output results of all cells.

Input

The first line contains two integer $N, M$: the number of cells in the spreadsheet and the number of cells with formula.

The cells are labeled with 1, 2, ..., N (instead of the usual way we see in spreadsheet applications).

The following M lines describes the formula, for each line is either:

- A x1 y - Cell x₁ has value y
- B x1 x2 y - Cell x₁ has formula: cell x₂ + value y
- C x1 x2 x3 y - Cell x₁ has formula: cell x₂ + cell x₃ + value y
- D x1 x2 x3 x4 y - Cell x₁ has formula: cell x₂ + cell x₃ + cell x₄ + value y

Constraints

- 1 ≤ M ≤ N ≤ 10^₅
- 1 ≤ x₁, x₂, x₃, x₄ ≤ N, 1 ≤ y ≤ 10⁶ for all formula
- x₁ for all formula are distinct
- The result for each cell without reference error does not exceed 10¹⁸

Output

For each cell please output "#REF!" if it has reference error, otherwise output its value.

Sample Input  Download

Sample Output  Download

Tags

Discuss