Hide

Problem S
Snjóteppa

Languages en is
/problems/snjoteppa/file/statement/en/img-0001.jpg
Image from flickr.com

One day Nesi was going to drive to Reykjavík University, but it had snowed quite a bit. Some cars have gotten stuck in both lanes of his street and he’s unsure if he can make it out of the street, even using both lanes and driving against traffic. Even worse is the fact that cars are coming and going, so he has no idea when he can leave.

His street can be modeled as a grid with two rows and $n$ columns, but each cell $(x, y)$ can either be empty or be occupied by a car that’s stuck.

Nesi tells you the initial state of the street and each time a change occurs, like a car getting stuck or unstuck, he lets you know. In between he asks you whether he can make it out of the street at that point in time.

Input

The first line of the input contains two integers $n$ and $k$ ($2\leq n, k \leq 2\cdot 10^5$), the length of the street and the number of queries. The next two lines each contain $n$ letters, denoting the initial state of the street, ‘o’ denoting a stuck car and ‘.’ denoting an empty cell. Then there are $k$ lines, each containing a query which is of one of two forms:

  • U $x$ $y$: Update cell $(x, y)$; if a car was stuck there it has become unstuck, if there was no car there before then a car got stuck there ($1\leq x\leq 2$, $1\leq y \leq n$).

  • Q: Nesi wants to know if he can make it out of the street as is.

Output

Each time Nesi asks whether he can make it out of the street, print a single line containing Jebb if he can start somewhere in the leftmost column, drive his car to the right, left, up and down through the cells (not diagonally) and end up in the rightmost column without hitting another car. If he can’t print Neibb.

Scoring

Group

Points

Constraints

1

25

$n,k \leq 100$

2

5

$k = 1$ and the query will be of the type Q.

3

30

All cells in the lower row will contain a stuck car and they will never become unstuck ($x=1$ in all queries).

4

40

No further constraints.

Sample Input 1 Sample Output 1
5 5
...o.
.....
U 2 3
Q
U 1 3
U 2 3
Q
Neibb
Jebb
Sample Input 2 Sample Output 2
5 7
ooooo
.....
Q
U 1 1
U 1 2
Q
U 1 2
U 1 1
Q
Jebb
Jebb
Jebb
Sample Input 3 Sample Output 3
3 4
...
...
U 1 1
U 1 2
U 1 3
Q
Jebb