28302번 - 팔찌 스페셜 저지

문제

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

• 색이 다른 이웃한 두 구슬을 나머지 하나의 색을 가진 구슬 하나로 합칠 수 있다.
• 하나의 구슬을 나머지 두 색을 하나씩 가지는 구슬 둘로 쪼갤 수 있다.

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

입력

첫 줄에 첫 번째 팔찌에 들어 있는 구슬의 수 $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$을 출력한다.

제한

힌트