Hashiwokakero Bicolor
time limit per test
2 segundos
memory limit per test
256 megabytes
input
entrada padrão
output
saída padrão

O Hashiwokakero é um quebra-cabeça lógico japonês que literalmente significa "construa pontes!". O jogo é composto de um tabuleiro retangular quadriculado de tamanho arbitrário. Alguns quadrados são vazios e outros tem um círculo com um número entre 1 e 8, sendo esses chamados de ilhas. O objetivo é conectar todas as ilhas construindo pontes entre elas, seguindo algumas regras.

Laos estava brincando com esses puzzle e teve uma ideia de criar uma variação que chamou de Hashiwokakero Bicolor, com as seguintes regras:

Laos desenhou um exemplo de um tabuleiro de Hashiwokakero Bicolor que tem solução, mas ele ficou pensando se era possível fazer um programa de computador que pudesse lhe dizer isso.

Ajude Laos! Crie um programa que dado um tabuleiro de Hashiwokakero Bicolor, imprime se existe solução ou não.

Input

A primeira linha contém dois inteiros: $$$N$$$ $$$(1 \le N \le 40)$$$ e $$$M$$$ $$$(1 \le M \le 40)$$$. As $$$N$$$ linhas a seguir descrevem o tabuleiro.

Cada linha do tabuleiro é composta de $$$M$$$ sequências de dois caracteres. As posições vazias são representadas por dois caracteres '.' da seguinte forma: '..'. Se a posição não for vazia, ela é composto por um caractere $$$D$$$ $$$(1 \le D \le 8)$$$ que representa o dígito, e um caractere $$$C$$$, que pode ser igual a 'a' se a posição for azul, ou 'b' se a posição for laranja.

Output

Imprima 'YES' se existe uma solução para o tabuleiro, ou 'NO' se não existe.

Example

Input
7 7
2b3a..4b..2a..
1a........2b2a
..1b....1b3a3b
2b....8a..5b2a
3b..3a........
....2b....3a3b
3a....3b1a2b2a
Output
YES