눈 이불

플리커에서 가져온 이미지

어느 날 Nesi는 HR로 차를 몰고 내려가려고 했지만, 눈이 매우 많이 내렸다. 그의 집 앞 도로 양쪽 차선에 차들이 몇 대 갇혀 있으며, 양쪽 차선을 모두 이용하고 역주행까지 하더라도 어떻게든 그 도로를 통과할 수 있을지 알 수 없다. 설상가상으로 차들이 오가고 있어서, 언제 출발할 수 있을지 전혀 알 수 없다.

그의 집 앞 도로는 두 행과 $n$개의 열로 이루어진 표로 나타낼 수 있으며, 각 칸 $(x,y)$은 비어 있거나 갇힌 차를 포함한다.

Nesi는 도로의 초기 상태를 알려 주며, 차가 와서 갇히거나 갇힌 차가 빠져나가 떠나는 것처럼 변화가 일어날 때마다 그 사실을 알려 준다. 그 사이사이에 Nesi는 그 시점에 도로를 통과할 수 있는지 묻는다.

점수

그룹 | 점수 | 제한

1 | 25 | $n,k \leq 100$

2 | 5 | $k = 1$이고, 질의는 Q 형식이다

3 | 30 | 아래쪽 행의 모든 칸에는 갇힌 차가 있으며, 이 차들은 절대 빠져나가지 않는다(모든 질의에서 $x=1$)

4 | 40 | 추가 제한 없음

입력의 첫 줄에는 도로의 길이와 질의의 수를 나타내는 두 정수 $n$과 $k$가 주어진다($2\leq n, k \leq 2\cdot 10^5$). 다음 두 줄에는 도로의 초기 상태를 나타내는 $n$개의 문자가 각각 주어지며, o`'는 갇힌 차를, .`'는 빈칸을 나타낸다. 이어서 각각 하나의 질의를 포함하는 $k$개의 줄이 주어지며, 각 질의는 다음 중 하나이다.

• U $x$ $y$: 칸 $(x,y)$을 갱신한다. 그 칸에 차가 갇혀 있었다면 그 차가 빠져나가는 중이며, 그 칸에 차가 없었다면 차가 그곳에 갇히는 중이다. ($1\leq x\leq 2$, $1\leq y \leq n$)

• Q: Nesi는 이 시점에 도로를 통과할 수 있는지 알고 싶어 한다.

Nesi가 통과할 수 있는지 물을 때마다 한 줄을 출력한다. Nesi가 가장 왼쪽 열의 어느 곳에서든 출발하여 다른 차와 한 번도 충돌하지 않고 칸들을 통해 자신의 차를 오른쪽, 왼쪽, 위쪽, 아래쪽으로 이동시켜(대각선으로는 이동하지 않는다) 가장 오른쪽 열에서 끝낼 수 있다면 Jebb을 출력하고, 불가능하다면 Neibb을 출력한다.