POEM

POEM

wapas

밤하늘에 $N$개의 서로 다른 정수가 가득하다.

가슴속으로 그 정수들을 살펴보니,

절댓값이 $2N$을 넘지 않는다.

$0$도 존재하지 않는다.

밤하늘의 외로운 수들을 위해, 나는

$M$개의 계약으로 $1$번부터 $N$번까지

수들에게 번호를 붙여준다.

계약은 4가지 형태로 주어진다.

$P$ $L$ $R$

$L$번 수부터 $R$번 수까지 순서대로 곱했을 때 양수이다(Plus).

$O$ $L$ $R$

$L$번 수부터 $R$번 수까지 순서대로 더했을 때 홀수이다(Odd).

$E$ $L$ $R$

$L$번 수부터 $R$번 수까지 순서대로 더했을 때 짝수이다(Even).

$M$ $L$ $R$

$L$번 수부터 $R$번 수까지 순서대로 곱했을 때 음수이다(Minus).

계약을 이행하며 번호를 붙이니,

밤하늘의 외로운 수들이 빛난다.

아아, 얼마나 아름다운가!

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

그다음 $M$개의 줄에 계약이 한 줄씩 주어진다. $i$번째 줄에는 $i$번째 계약이 주어진다.

계약은 $Q$, $L$, $R$ 세 값이 공백으로 구분되어 주어진다. $Q$는 P, O, E, M 중 하나이고, $L$과 $R$은 양의 정수이다.

첫 번째 줄에 모든 계약을 만족하는 $N$개의 수를 공백으로 구분하여 출력한다. $j$번째 수는 번호 $j$를 붙인 수이다.

모든 계약을 만족하도록 수를 나열할 수 없다면 0을 출력한다.

만족하는 나열이 여럿이면 그중 아무거나 하나를 출력한다.

• $1 \le N, M \le 100\,000$
• $1 \le L \le R \le N$