SAMPLE INPUT:

2 7 7 1 2 a 1 3 a 2 4 b 3 5 a 5 6 a 6 7 a 7 4 a 4 3 1 2 z 2 3 x 3 4 y SAMPLE OUTPUT:

0 1 1 5 2 3 4 0 1 2 -1