문제

자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 우회전이 불가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로를 통과할 수 있다.

자동차들이 동시에 교차로를 통과하면 충돌할 수 있기 때문에, 효율적인 도로 교통 흐름을 위해서는 자동차끼리의 충돌을 방지할 수 있도록 자동차가 적절히 멈춰 있도록 하되, 너무 오래 멈춰 있지 않도록 소프트웨어를 적절하게 작성해야 한다.

이 문제에서 각 도로의 맨 앞에 있는 자동차는 자신을 기준으로 오른쪽에 위치한 도로에 차량이 있으면 1초 동안 출발하지 않고, 차량이 없으면 즉시 교차로를 통과한다. 정확한 설명을 위해 아래와 같은 상황을 생각하여 보자.

1번 차량이 C 위치에, 2번 차량이 B 위치에 있다. 두 차량이 동시에 출발하게 되면 왼쪽 그림과 같이 교차로 위에서 충돌할 우려가 있다. 1번 차량을 기준으로 오른쪽에 있는 도로인 B 위치의 도로에 차량이 있기 때문에, 1번 차량은 1초간 출발하지 않고, 2번 차량은 교차로를 통과한다.

A 위치에 있는 차량의 오른쪽에 있는 도로는 D 위치의 도로이고, B 위치에 있는 차량의 오른쪽에 있는 도로는 A 위치의 도로이고, C 위치에 있는 차량의 오른쪽에 있는 도로는 B 위치의 도로이고, D 위치에 있는 차량의 오른쪽에 있는 도로는 C 위치의 도로이다.

위와 같이 1번 차량이 다른 차량이 지나갈 때까지 대기하는 동안 새로운 차량이 C 위치에 계속 진입할 수 있다. 차선이 하나밖에 없기 때문에, 맨 앞에 있는 차량이 지나가기 전까지는 해당 위치의 차선에 적체된 차량이 계속 늘어날 수 있다. 예를 들어 위의 상황에서 1초 뒤에 3번 차량이 B번 위치에, 4번 차량이 C번 위치에 진입할 경우, 아래와 같이 C번 위치에 1번 차량과 4번 차량이 대기하게 된다.

안전을 위해 각 위치마다 1초에 한 대씩만 교차로를 통과할 수 있다. 위의 그림과 같이 하나의 차선에 1번 차량과 4번 차량이 서 있고 이후에 차량이 새로 진입하지 않는다면, 1초 뒤에 1번 차량이 교차로를 통과하고, 다시 1초 뒤에 (즉 전체적으로 2초 뒤에) 2번 차량이 교차로를 통과할 것이다.

A, B, C, D 위치에 동시에 차량이 한 대 이상씩 있다면, 교착 상태에 빠져 어떤 차량도 교차로를 통과할 수 없게 된다.

앞으로 대의 차량이 교차로를 통과하기 위해 A, B, C, D 위치에 진입할 것이다. ()번 차량은 초 때에 위치에 진입하여, 해당 차선에 있는 줄 맨 뒤에 있을 예정이다. 혼선을 방지하기 위해, 같은 시각에 각 위치에 진입할 수 있는 차량은 최대 한 대이다.

매초마다, 모든 차량이 진입한 직후, 각 위치의 맨 앞에 있는 차량은 오른쪽 차선에 차량이 없는지 확인한 뒤, 차량이 없다면 교차로를 통과한다.

각 차량이 교차로를 통과하는 시각이 언제인지 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 이 주어진다.

다음 개의 줄 중 ()번째 줄에는 와 가 공백 하나를 사이로 두고 주어진다.

• 모든 ()에 대해:
  • 는 A, B, C, D 중 하나이다.

• 이고 이면, 이다.

출력

개의 줄을 출력한다.

이 중 ()번째 줄은 번 차량이 도로를 통과한다면 교차로를 통과하는 시각, 교차로를 통과하지 않는다면 -1이어야 한다.

서브태스크

노트

예제 3번의 경우 다음과 같이 진행된다.