Two Knights' Poem

Time limit1sMemory limit256 MB

Summary

Decide whether two knights moving in chess-knight steps on a 40-key keyboard can type each given poem, using the other knight on Shift for capitals.

Level: Medium6 of 10
Topics: BFS, Graph
Solved: No attempts yet

Problem

Two chess knights write short one-line poems together. They also got hold of a laptop to type on. The laptop keyboard has 4 rows of 10 keys, 40 keys in all. 30 of them are symbol keys, 4 are Shift keys, and 6 are Space keys.

On an ordinary keyboard Shift and Space are single wide keys. Here each one counts as several separate keys that all have the same effect.

The layout is this.

Row 1:  q   w   e   r   t   y   u   i   o   p
Row 2:  a   s   d   f   g   h   j   k   l   ;
Row 3:  z   x   c   v   b   n   m   ,   .   /
Row 4:  Sh  Sh  Sp  Sp  Sp  Sp  Sp  Sp  Sh  Sh

Sh is a Shift key and Sp is a Space key. The upper value of a letter key is its capital letter, and the upper values of ;, ,, ., / are :, <, >, ? in that order.

The knights type the poem by making moves, one knight at a time, that are legal for a chess knight. A knight moves two squares vertically and then one horizontally, or one square vertically and then two horizontally. From the d key, for example, a knight can reach q, z, t, b, the second Shift key from the left, and the second Space key from the left.

One knight always starts on the left-most Shift key and the other always starts on the right-most Shift key. Either knight may move first, and either knight may make several moves in a row. The two knights cannot occupy the same key.

Each move of a knight types at most one character onto the poem. A knight that lands on a symbol key or a Space key types one character. A knight that lands on a symbol key types the upper value of that key when the other knight is standing on a Shift key, and the lower value otherwise. A knight that lands on a Space key always types one space, whether or not the other knight is on a Shift key. A knight that lands on a Shift key types nothing.

Input

The input holds several test cases. Each test case is one line holding one poem. A poem is 1 to 100 characters long and uses only characters the symbol keys can produce, plus spaces. No poem starts or ends with a space. The last line of the input is a single asterisk (*).

Output

For each poem output 1 if the knights can type it and 0 if they cannot. Print one number per line, with no spaces and no blank lines.

Examples2

Example 1

Input

S,veA,eVE,aU
S,veA,eVE,aUc
CAlmimg eventa
CAL
*

Expected output

Example 2
Input
```
S
C
<
L
Q
a
z
?
*
```
Expected output
```
1
1
1
1
0
0
0
0
```