만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

와인병 배치

시간 제한2초메모리 제한2048 MB

요약
모든 비평가가 요청한 r과 w가 어떤 연속 구간의 빨간 와인 수와 흰 와인 수와 같도록 길이 n의 R/W 배열을 만들고, 불가능하면 IMPOSSIBLE을 출력합니다.
난이도

쉬움10점 중 3점

유형
그리디, 수학, 구현
정답자
아직 제출이 없습니다

문제

가브리엘라는 mm명의 평론가가 참석하는 유명한 와인 시음 행사를 준비하라는 지시를 받았다. 전시될 와인은 nn가지 종류로, 각각 레드 와인 또는 화이트 와인이다.

와인은 테이블 위에 한 줄로 놓인 nn개의 병에 담겨 나온다. 편의를 위해 각 평론가는 연속한 병 구간에서 시음한다. 즉, 어떤 1≤a≤b≤n1 \le a \le b \le n에 대해 aa, a+1a + 1, …\dots, bb번 위치의 병만 맛본다. 구간은 평론가마다 다르며, 평론가는 자신의 선호에 따라 그 자리에서 구간을 고른다. 실제로 ii번째 평론가(1≤i≤m1 \le i \le m)는 정확히 rir_i개의 레드 와인과 wiw_i개의 화이트 와인을 맛보고 싶다고 요청했다.

가브리엘라는 레드 와인과 화이트 와인을 각각 몇 병 준비할지, 어떤 순서로 놓을지 아직 정하지 않았다. 모든 평론가의 요청을 만족하는 배치(즉, 레드 와인 또는 화이트 와인 nn병의 수열)를 찾아라. 그러한 배치가 없으면 없다고 밝혀라.

입력

각 테스트는 여러 테스트 케이스로 이루어진다. 첫 줄에는 정수 tt(1≤t≤1001 \le t \le 100)가 주어진다. 이는 테스트 케이스의 수이다. 이어서 tt개의 테스트 케이스 설명이 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 nn과 mm(1≤n≤1001 \le n \le 100, 1≤m≤1001 \le m \le 100)이 주어진다. nn은 와인 병의 수, mm은 평론가의 수이다.

다음 mm개 줄에는 각각 두 정수 rir_i, wiw_i(0≤ri,wi≤1000 \le r_i, w_i \le 100, ri+wi≥1r_i + w_i \ge 1)가 주어진다. 이는 ii번째 평론가가 맛보고 싶어 하는 레드 와인과 화이트 와인의 수이다.

출력

각 테스트 케이스에서 해가 하나 이상 존재하면, R과 W로 이루어진 길이 nn의 문자열을 출력한다. jj번째 문자(1≤j≤n1 \le j \le n)는 배치의 jj번째 병에 든 와인의 종류를 나타낸다(R은 레드, W는 화이트).

해가 여러 개면 아무거나 출력한다. 해가 없으면 문자열 IMPOSSIBLE을 출력한다.

예제1

  1. 예제 1

    입력
    3
    5 3
    1 0
    3 2
    2 2
    4 3
    2 1
    1 1
    0 3
    3 2
    0 2
    0 3
    
    예상 출력
    RWRRW
    IMPOSSIBLE
    WWW