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 x1 has value y
- B x1 x2 y - Cell x1 has formula: cell x2 + value y
- C x1 x2 x3 y - Cell x1 has formula: cell x2 + cell x3 + value y
- D x1 x2 x3 x4 y - Cell x1 has formula: cell x2 + cell x3 + cell x4 + value y
Constraints
- 1 ≤ M ≤ N ≤ 105
- 1 ≤ x1, x2, x3, x4 ≤ N, 1 ≤ y ≤ 106 for all formula
- x1 for all formula are distinct
- The result for each cell without reference error does not exceed 1018
Output
For each cell please output "#REF!" if it has reference error, otherwise output its value.