Description

你有玩過 Star Battle Puzzle 嗎？Star Battle Puzzle 是一個解謎遊戲，每一道謎題都會以一個空的 $9\times 9$ 盤面開始，該盤面會被切割成若干個區塊。玩家的目的是在一些空格填入一些「星星」，滿足：

每一行都有恰兩個星星
每一列都有恰兩個星星
每一個區塊都有恰兩個星星
任兩個星星都不得八方位相鄰

下圖是一道空的盤面及其解答的示意圖：

現在，請你撰寫一支程式，在讀入一個已經填好星星的 Star Battle Puzzle 盤面後，輸出該盤面是否有被完整解決。意即填入的星星是否有滿足所有指定條件。

Input Format

輸入首先會是空盤面的資訊，共有九行，每行九個字元，每個字元皆為數字 $\texttt{1}$ 至 $\texttt{9}$ 其中之一，代表該格隸屬於的區塊編號。

緊接著是填入星星的方式，共有九行，每行九個字元，每個字元 . 或 *，其中 . 代表未填入任何東西、* 代表填入一顆星星。

保證給定的空盤面由字元 $\texttt{1}$ 至 $\texttt{9}$ 組成
保證給定的空盤面的共有九個區塊，且每個區塊四方位連通
保證給定的填入星星方式由字元 . 和 * 組成

Output Format

若輸入的填入星星方式滿足所有條件，輸出 $\texttt{Valid}$；否則只要違反任何一個條件，輸出 $\texttt{Invalid}$。

Sample Input 1

121333344
121334444
121111144
111111144
551116644
511176666
518777966
588877996
888887996
.*...*...
...*...*.
.*...*...
...*....*
*.....*..
....*...*
..*...*..
*...*....
..*....*.

Sample Output 1

Valid

Sample Input 2

121333344
121334444
121111144
111111144
551116644
511176666
518777966
588877996
888887996
.*...*...
...*...*.
.*......*
...*.*...
*.....*..
....*...*
..*...*..
*...*....
..*....*.

Sample Output 2

Invalid

Sample Input 3

121333344
121334444
121111144
111111144
551116644
511176666
518777966
588877996
888887996
.*.......
...*...*.
.*...*...
...*....*
*.....*..
....*...*
..*...*..
*...*....
..*....*.

Sample Output 3