팔찌 | cho.sh

빨강, 파랑, 그리고 초록 세 가지 색을 가진 구슬들이 원형으로 끼워진 마법의 팔찌가 있다. 팔찌의 구슬에는 다음과 같은 조작을 할 수 있다:

각 조작 전후, 합치거나 쪼갠 구슬과 주변의 다른 구슬들 간의 상대적 위치는 변하지 않는다. 돌리거나 뒤집어서 구슬의 구성이 같은 팔찌는 동일한 팔찌이다. 두 팔찌가 주어졌을 때, 충분한 조작을 거쳐 한 팔찌를 다른 팔찌와 동일하게 바꿀 수 있는지 알아보자.

첫 줄에 첫 번째 팔찌에 들어 있는 구슬의 수 $N$ 이 주어지고, 이어서 구슬들의 색을 나타내는 길이 $N$ 의 문자열이 주어진다.

다음 줄에 두 번째 팔찌에 들어 있는 구슬의 수 $M$ 이 주어지고, 이어서 구슬들의 색을 나타내는 길이 $M$ 의 문자열이 주어진다. ( $1\le N,M\le 1000$ )

각 문자열은 R, B 또는 G로 구성되어 있다(각각 빨강, 파랑, 초록을 의미한다).

첫 번째 팔찌를 두 번째 팔찌로 바꿀 수 있으면, 첫째 줄에 그러기 위해 필요한 조작의 수 $k$ 를 출력한다. $k$ 는 최소일 필요는 없지만, $10000$ 이하여야 한다(가능한 입력의 경우 항상 $10000$ 회 이하로 가능하다는 것이 증명되어 있다).

이어서 둘째 줄부터 $k$ 개의 줄에 걸쳐, $i$ 번째 줄에 $i$ 번째 조작을 출력한다. 첫 번째 팔찌의 구슬 색을 차례로 $c\_1,\cdots ,c\_N$ 이라고 할 때, 가능한 조작은 다음과 같다:

$1$ $a$ $b$ : $a$ 번째 구슬과 $b$ 번째 구슬을 합친다. $1\le a,b\le N$ 이어야 하며, $b=a+1$ 이거나, $a=N$ 이고 $b=1$ 이어야 한다. $c\_a$ 와 $c\_b$ 는 서로 달라야 한다.
- $b=a+1$ 인 경우, 조작 이후 팔찌의 구슬 색은 순서대로 $c\_1,\cdots ,c\_{a-1},c',c\_{a+2},\cdots ,c\_N$ 이 된다.
- $a=N$ 이고 $b=1$ 인 경우, 조작 이후 팔찌의 구슬 색은 순서대로 $c',c\_2,\cdots ,c\_{N-1}$ 이 된다.
단 $c'$ 은 합쳐진 구슬의 색이다. 이후 $N$ 은 $1$ 감소한다.
$2$ $a$ $x$ $y$ : $a$ 번째 구슬을 색 $x$ , $y$ 의 두 구슬로 분리한다. $0\le a\le N+1$ 이어야 하며, $x$ , $y$ 는 R, B, G 중 하나여야 한다. $x$ , $y$ , $c\_a$ 는 서로 달라야 한다.( $a=0$ 과 $a=N+1$ 은 편의를 위해 존재하며, 새로 생긴 두 구슬을 $1$ 번째와 $N+1$ 번째 위치에 놓는 조작을 의미하는 것으로, 정확히는 $a$ 번째 구슬을 분리하는 것이 아니다.)
- $1\le a\le N$ 인 경우, 조작 이후 팔찌의 구슬 색은 순서대로 $c\_1,\cdots ,c\_{a-1},x,y,c\_{a+1},\cdots ,c\_N$ 이 된다.
- $a=0$ 인 경우 $1$ 번째 구슬을 분리하며, 조작 이후 팔찌의 구슬 색은 순서대로 $y,c\_2,\cdots ,c\_N,x$ 가 된다.
- $a=N+1$ 인 경우 $N$ 번째 구슬을 분리하며, 조작 이후 팔찌의 구슬 색은 순서대로 $y,c\_1,\cdots ,c\_{N-1},x$ 가 된다.
이후 $N$ 은 $1$ 증가한다.

모든 조작이 끝난 후 남는 첫 번째 팔찌의 구슬 배열은, 두 번째 팔찌를 적당히 돌리고 뒤집어서 나올 수 있는 배열이어야 한다.

첫 번째 팔찌를 두 번째 팔찌로 바꿀 수 없는 경우는 첫째 줄에 $-1$ 을 출력한다.