점 연결

"점 연결"은 혼자 하는 게임입니다. 2보다 큰 두 정수 $g$와 $r$을 정한 뒤, 정사각형 꼭짓점 네 곳에 점을 찍습니다. 위쪽 두 점은 초록, 아래쪽 두 점은 빨강입니다. 초록 점과 빨간 점을 정사각형 안에 더 놓되, 처음 네 점을 포함해 어떤 세 점도 한 직선 위에 있지 않게 합니다. 초록 점의 총 개수가 $g$, 빨간 점의 총 개수가 $r$이 될 때까지 반복합니다.

판이 준비되면 점들을 연결합니다. 다음 조건을 만족하면 같은 색의 두 점을 선분으로 이을 수 있습니다.

• 연결할 두 점의 색이 같아야 합니다.
• 두 점을 잇는 선분이, 끝점을 제외하고는 이미 그어진 다른 선분과 교차하지 않아야 합니다.

점 $u$와 $v$가 같은 연결 요소에 있다는 것은, 이미 그어진 선분만으로 $u$에서 $v$까지 이동할 수 있다는 뜻입니다.

초록 점 $g-1$개의 선분으로 모든 초록 점을 하나의 연결 요소로 만들고, 빨간 점 $r-1$개의 선분으로 모든 빨간 점을 또 다른 연결 요소로 만들면 승리합니다. 문제 조건대로 점을 배치했다면 항상 승리하는 방법이 존재함을 증명할 수 있습니다.

한 변의 길이가 $s$인 정사각형 판에 초록 점 $g$개, 빨간 점 $r$개가 주어집니다. 좌표는 정수 쌍 $(x_i, y_i)$입니다. 초록 점은 1부터 $g$까지 번호가 매겨지며, $(0,s)$의 왼쪽 위 점이 1, $(s,s)$의 오른쪽 위 점이 2, 나머지 내부 점은 3부터 $g$까지입니다. 빨간 점은 1부터 $r$까지 번호가 매겨지며, $(0,0)$의 왼쪽 아래 점이 1, $(s,0)$의 오른쪽 아래 점이 2, 나머지 내부 점은 3부터 $r$까지입니다.

그림은 모든 초록 점이 하나의 연결 요소로, 모든 빨간 점이 다른 연결 요소로 묶인 예입니다. 세 점이 한 직선 위에 있지 않고, 두 선분이 끝점에서만 만납니다.

초록 점 $g$개와 빨간 점 $r$개의 좌표가 주어질 때, 초록 선분 $g-1$개와 빨간 선분 $r-1$개를 그려 모든 초록 점을 하나로, 모든 빨간 점을 하나로 연결하고, 선분끼리 서로 교차하지 않게 하는 프로그램을 작성하세요.

• 1번째 줄: 정수 $g$.
• 다음 $g$줄: 공백으로 구분된 두 정수 $x_i, y_i$. 1번부터 $g$번까지 각 초록 점의 좌표.
• $(g+2)$번째 줄: 정수 $r$.
• 다음 $r$줄: 공백으로 구분된 두 정수 $x_i, y_i$. 1번부터 $r$번까지 각 빨간 점의 좌표.

출력은 $(g-1)+(r-1)$줄로, 그은 선분마다 한 줄씩 출력합니다.

각 줄에는 공백으로 구분된 정수 두 개와 문자 하나를 출력합니다. 두 정수는 선분으로 연결한 두 점의 번호이고, 문자는 초록이면 g, 빨강이면 r입니다.

선분을 출력하는 순서와, 각 선분에서 두 끝점을 적는 순서는 아무거나 됩니다.

• $3 \le g \le 50\,000$: 초록 점 개수.
• $3 \le r \le 50\,000$: 빨간 점 개수.
• $0 < s \le 200\,000\,000$.