E. Mini Minesweeper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A game of Mini Minesweeper is played on an $$$8 \times 8$$$ grid. At the start of the game, each square of the grid is either hidden or revealed. Exactly $$$M$$$ of the hidden squares contain mines; the others are empty. Written on each revealed square is a number between $$$0$$$ and $$$8$$$ inclusive: the number of hidden cells adjacent to the square (in the four orthogonal and four diagonal directions) that contain a mine.

You are helping your friend debug their Mini Minesweeper implementation, and so you need to write a checker for the initial board state. The checker should analyze the board and decide: is there a possible placement of the $$$M$$$ mines in hidden squares so that all of the numbers written on the revealed squares correctly identify the number of adjacent mines?

Input

The first line of input contains a positive integer $$$M \leq 64$$$: the number of mines distributed throughout the hidden squares of the game board.

The following eight lines contain eight characters each and describe the initial game board. Each character is either #, indicating a hidden square, or a digit 0 through 8, indicating a revealed square with that digit written on it.

Output

Print VALID if there exists some placement of $$$M$$$ mines in the hidden squares so that every number written on a revealed square correctly identifies the number of neighboring mines. Print INVALID otherwise.

Examples
Input
27
#######3
4##54###
####3###
4#7544#2
2####211
14##3#00
#3#42#11
##2#11#1
Output
VALID
Input
2
00000000
00000000
00000000
00111000
001#1000
00113110
00001#10
00001110
Output
INVALID
Input
1
00000000
00000000
00000000
00111000
001#1000
00112110
00001#10
00001110
Output
INVALID
Input
32
########
########
########
########
########
########
########
########
Output
VALID
Note

Mines cannot be placed outside of the $$$8 \times 8$$$ grid. Numbers written on revealed corner squares count the number of mines in the three squares adjacent to that corner, and similarly for numbers written on revealed edge squared.

If there are fewer than $$$M$$$ hidden squares, the board is INVALID.