Stamp Rally

Stamp Rally

Stamp Rally

The Japan Amusement Group (JAG) is planning an event at a theme park that imitates an island country. In this event, each time a participant crosses a bridge, the stamps decided for each bridge are stamped in order on the stamp book. The prepared stamp is one of the following seven types.

a () [] + *

It is clear if you walk across the bridge from the start to the goal and the sequence of stamps stamped is the correct formula. However, the direction of crossing the bridge is fixed, and it is not possible to cross in the opposite direction. You can cross the same bridge many times, and if you finally reach the goal point, you may continue to collect stamps after reaching the goal point. The correct formula is defined by BNF below.

:: = | "+" :: = | "*" :: = "a" | "(" ")" | "[" "]"

Since I decided the start goal and the stamp for each bridge, I tried it with the people concerned, but no one appeared to clear it. Perhaps it cannot be cleared with this setting.

Since the start / goal and bridge information is given, write a program to judge whether it can be cleared.

Input

The input consists of 50 or less datasets. Each data set is represented in the following format.

n m s t a1 b1 c1 ... am bm cm

The first line of the dataset consists of four integers n, m, s, and t separated by a single whitespace character. n is the number of islands, and we can assume that 1 ≤ n ≤ 200. Each island is numbered from 1 to n. m is the number of bridges and we can assume that 1 ≤ m ≤ 100,000. s is the starting island number and t is the goal island number. Sometimes the start and finish are on the same island. Each of the following m lines consists of two integers separated by one space character and one character. ai and bi represent the crossing from island ai to island bi by the i-th bridge, and ci represents the stamp stamped by the i-th bridge. There may be multiple bridges between two islands, or there may be bridges within one island.

The end of the input is indicated by a single line of four zeros.

Output

For each dataset, output "Yes" if it can be cleared, and "No" if it cannot be cleared on one line.

Sample Input

4 5 1 4 1 2 ( 1 3 a 2 4 a 3 4) 3 2 + 4 4 1 2 13 ( 3 4 a 4 1 + 3 2 a 3 4 1 1 1 2 a 2 2 + 2 3 a 3 1 a 5 8 1 5 1 1 [ 1 2 ( twenty one * 2 2 a 2 3 a 3 3) 3 4] 4 5) 2 14 1 1 1 2 a 1 2 ( 1 2) 1 2 [ 1 2] 1 2 + 1 2 * 2 1 a twenty one ( twenty one ) twenty one [ twenty one ] 2 1 + twenty one * 0 0 0 0

Output for Sample Input

Yes No No Yes No

Example

Input

4 5 1 4 1 2 ( 1 3 a 2 4 a 3 4 ) 3 2 + 4 4 1 2 1 3 ( 3 4 a 4 1 + 3 2 a 3 4 1 1 1 2 a 2 2 + 2 3 a 3 1 a 5 8 1 5 1 1 [ 1 2 ( 2 1 * 2 2 a 2 3 a 3 3 ) 3 4 ] 4 5 ) 2 14 1 1 1 2 a 1 2 ( 1 2 ) 1 2 [ 1 2 ] 1 2 + 1 2 * 2 1 a 2 1 ( 2 1 ) 2 1 [ 2 1 ] 2 1 + 2 1 * 0 0 0 0

Output

Yes No No Yes No

inputFormat

Input

The input consists of 50 or less datasets. Each data set is represented in the following format.

n m s t a1 b1 c1 ... am bm cm

The first line of the dataset consists of four integers n, m, s, and t separated by a single whitespace character. n is the number of islands, and we can assume that 1 ≤ n ≤ 200. Each island is numbered from 1 to n. m is the number of bridges and we can assume that 1 ≤ m ≤ 100,000. s is the starting island number and t is the goal island number. Sometimes the start and finish are on the same island. Each of the following m lines consists of two integers separated by one space character and one character. ai and bi represent the crossing from island ai to island bi by the i-th bridge, and ci represents the stamp stamped by the i-th bridge. There may be multiple bridges between two islands, or there may be bridges within one island.

The end of the input is indicated by a single line of four zeros.

outputFormat

Output

For each dataset, output "Yes" if it can be cleared, and "No" if it cannot be cleared on one line.

Sample Input

4 5 1 4 1 2 ( 1 3 a 2 4 a 3 4) 3 2 + 4 4 1 2 13 ( 3 4 a 4 1 + 3 2 a 3 4 1 1 1 2 a 2 2 + 2 3 a 3 1 a 5 8 1 5 1 1 [ 1 2 ( twenty one * 2 2 a 2 3 a 3 3) 3 4] 4 5) 2 14 1 1 1 2 a 1 2 ( 1 2) 1 2 [ 1 2] 1 2 + 1 2 * 2 1 a twenty one ( twenty one ) twenty one [ twenty one ] 2 1 + twenty one * 0 0 0 0

Output for Sample Input

Yes No No Yes No

Example

Input

4 5 1 4 1 2 ( 1 3 a 2 4 a 3 4 ) 3 2 + 4 4 1 2 1 3 ( 3 4 a 4 1 + 3 2 a 3 4 1 1 1 2 a 2 2 + 2 3 a 3 1 a 5 8 1 5 1 1 [ 1 2 ( 2 1 * 2 2 a 2 3 a 3 3 ) 3 4 ] 4 5 ) 2 14 1 1 1 2 a 1 2 ( 1 2 ) 1 2 [ 1 2 ] 1 2 + 1 2 * 2 1 a 2 1 ( 2 1 ) 2 1 [ 2 1 ] 2 1 + 2 1 * 0 0 0 0

Output

Yes No No Yes No

样例

4 5 1 4
1 2 (
1 3 a
2 4 a
3 4 )
3 2 +
4 4 1 2
1 3 (
3 4 a
4 1 +
3 2 a
3 4 1 1
1 2 a
2 2 +
2 3 a
3 1 a
5 8 1 5
1 1 [
1 2 (
2 1 *
2 2 a
2 3 a
3 3 )
3 4 ]
4 5 )
2 14 1 1
1 2 a
1 2 (
1 2 )
1 2 [
1 2 ]
1 2 +
1 2 *
2 1 a
2 1 (
2 1 )
2 1 [
2 1 ]
2 1 +
2 1 *
0 0 0 0

Yes
No
No
Yes
No

</p>