Sample Input 1

2
5 May
30 Jul

Sample Output 1

Taurus
Leo

Sample Input 1

4 4
@..#
....
....
#..@
4 4
@..#
..#.
.#..
#..@
0 0

Sample Output 1

2
0

Sample Input 1

3 1

Sample Output 1

YES
1 2
1 3

Sample Input 2

3 2

Sample Output 2

NO

Sample Input 1

12
1 3
1 3
3 2
1 3
1 5
2 1
7 2
8 2
9 3
8 2
11 3
4
1 10
2 10
3 10
4
1 20
2 10
3 10
0

Sample Output 1

0
0
10

Sample Input 1

123-456+789
10
? 2 5
? 7 9
? 4 6
! 1 +
! 4 0
? 1 7
! 1 -
? 1 3
? 4 7
? 4 5

Sample Output 1

19
13
998244308
230456
998244330
456
4

Sample Input 1

2
10 10
1 2 10
0

Sample Output 1

100

Sample Input 1

2
4
6 3 5 3
5
invite
icpc
party
cat
cow
4
6 3 5 3
4
invite
party
cat
cow

Sample Output 1

2
0

Sample Input 1

2 2

Sample Output 1

6

Sample Input 2

1 5

Sample Output 2

13

Sample Input 1

9 2
1 4 1 2 2 4 1 2 1

Sample Output 1

11

Sample Input 1

7
4 1
3 1
2 1
1 1
1 2
1 3
1 4
4
0 0
0 2
2 0
2 2
0

Sample Output 1

9
1

Sample Input 1

2
6
1 1
1 3
2 2
2 3
3 1
3 2
3
1 1
1 2
2 1

Sample Output 1

YES
NO

Sample Input 2

2
5
1 1
1 3
2 2
3 1
3 3
5
1 1
1 3
2 3
3 1
3 3

Sample Output 2

NO
NO

Sample Input 1

2
1 1 3 3
0 1 1 1

Sample Output 1

4
1