An artist prepared a pixel art drawing for depicting animals in black and white. These drawings should be displayed on a gigantic pixelated, rectangular screen, with $K$ rows (ordered from $0$ to $K -1$, from top to bottom) and $L$ columns (ordered from $0$ to $L -1$, from left to right): displaying drawings on such screens is your job.
When you initialize the screen, it displays only white pixels. Then, its pixels should be controlled individually by switches, and pressing the switch of a pixel $P$ ought to change the color of $P$, either from black to white or from white to black. However, the screen has a defect: pressing the switch of the pixel $P$ also changes the color of those pixels that have an edge in common with $P$, i.e., those pixels that are adjacent horizontally or vertically (but not diagonally). Yet, it might still be possible that, by adequately choosing which switches you press, even this defective screen can display the drawing you were handed.
Can you manage to display that drawing? If yes, which set of switches should you press?
Limits
If there is no way to display the desired drawing by pressing switches, your output should contain one line with the word "IMPOSSIBLE" and nothing else. Otherwise, your output should contain $K$ lines, each one containing $L$ symbols "A" or "P" and separated by spaces:
Note that the order in which switches are pressed is not important, and that it is never necessary to press twice the same switch. Thus, a solution can be fully described by the set of switches pressed. There might be several solutions, i.e., several adequate sets of switches. In that case, your output should just represent one such solution.
*Sample Explanation 1*
Whenever you press a switch, the colors of both pixels changes. Hence, they always have the same color, and the drawing cannot be displayed.
*Sample Explanation 2* You can indeed check that, if you press the switches associated to the red pixels of the left picture, you will obtain the picture depicted on the right.
## Input
Line 1 contains two integers $K$ and $L$, separated by spaces. For all $i$ such that $0 <= i < K$, line $i + 2$ contains $L$ symbols "B" or "W", separated by spaces: if the $j$-th symbol (with $0 <= j < L$) is a "B", then the pixel that will be displayed on row $i$ and column $j$ should be black; otherwise, it should be a white pixel. Limits $1 <= K times L <= 100000$.
## Output
If there is no way to display the desired drawing by pressing switches, your output should contain one line with the word "IMPOSSIBLE" and nothing else. Otherwise, your output should contain $K$ lines, each one containing $L$ symbols "A" or "P" and separated by spaces: For all $i$ and $j$ such that $0 <= i < K$ and $0 <= j < L$, if the $j$-th symbol on line $i + 1$ is a "P", then you should press the switch associated with the pixel on row $i$ and column $j$; otherwise, you should avoid that switch.
[samples]
## Note
Note that the order in which switches are pressed is not important, and that it is never necessary to press twice the same switch. Thus, a solution can be fully described by the set of switches pressed. There might be several solutions, i.e., several adequate sets of switches. In that case, your output should just represent one such solution.*Sample Explanation 1*Whenever you press a switch, the colors of both pixels changes. Hence, they always have the same color, and the drawing cannot be displayed.*Sample Explanation 2* You can indeed check that, if you press the switches associated to the red pixels of the left picture, you will obtain the picture depicted on the right.
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ c', c, s, f, p, q \in \mathbb{Z} $ be parameters with $ c' \ge c \ge f $, $ s, p, q \ge 1 $.
- Let $ n \in \mathbb{Z} $ be the number of contestants in the scoreboard.
- Let $ P = \{ (u_i, F_i, L_i, S_i, \text{score}_i, \text{penalty}_i) \mid i \in \{1, \dots, n\} \} $ be the set of contestants, where:
- $ u_i $: username (unique, alphanumeric + underscore),
- $ F_i $: first name,
- $ L_i $: last name,
- $ S_i $: school,
- $ \text{score}_i \in \mathbb{Z}^+ $: score,
- $ \text{penalty}_i \in \mathbb{Z}^+ $: time penalty,
- No two contestants have same score and penalty.
Define ranking: contestants sorted **descending** by score, then **ascending** by penalty (tiebreaker).
Define lists:
- $ \text{Shortlist} \subseteq P $: top $ c $ contestants by rank.
- $ \text{Waitlist} \subseteq P $: next $ s $ contestants after shortlist (ranks $ c+1 $ to $ c+s $).
- $ \text{Invited} \subseteq \text{Shortlist} $: subset of shortlist with invitation status.
- $ \text{Confirmed} \subseteq \text{Invited} $: invited who accepted.
- $ \text{Finalists} \subseteq \text{Confirmed} $: top $ f $ confirmed participants.
- $ \text{NonFinalists} \subseteq \text{Confirmed} \setminus \text{Finalists} $: confirmed but not finalists.
- $ \text{WaitlistConfirmed} \subseteq \text{Waitlist} $: waitlisted who accepted.
- $ \text{Substitutes} \subseteq \text{WaitlistConfirmed} $: waitlisted accepted who may replace absent finalists.
Let $ \text{Cap} \in \mathbb{Z} $ be current capacity for finalists, initialized to $ c' $, non-decreasing.
**Constraints**
1. $ 1 \le t \le 10^4 $
2. $ 1 \le n \le 10^5 $, total $ \sum n \le 10^5 $
3. $ 2 \le e \le 10^5 $, total $ \sum e \le 10^5 $
4. $ 1 \le c', c, s, f, p, q \le 10^5 $, $ c' \ge c \ge f $
5. All usernames, names, schools satisfy string constraints.
6. No two contestants share same (score, penalty).
7. All string comparisons are case-insensitive.
8. Lexicographic ordering: space < 'a'-'z' < '0'-'9'
**Events**
Each event is one of:
- `INVITE u`: invite contestant with username $ u $ (if in shortlist).
- `ACCEPT u`: accept invitation (if invited and not declined).
- `DECLINE u`: decline invitation (if invited and not accepted).
- `PROMOTE u`: promote contestant $ u $ from waitlist to shortlist (if in waitlist and capacity > c).
- `CAPACITY x`: set $ \text{Cap} = x $, $ x \ge c $.
- `PRINT NAMETAGS`: terminate event processing.
**Queries**
- `QUERY SHORTLIST i`: return username at rank $ i $ in shortlist (1-indexed).
- `QUERY WAITLIST i`: return username at rank $ i $ in waitlist.
- `QUERY FINALISTS i`: return username at rank $ i $ in finalists.
- `QUERY NONFINALISTS i`: return username at rank $ i $ in non-finalists.
- `QUERY SUBSTITUTES i`: return username at rank $ i $ in substitutes.
**Objective**
For each event:
- If valid → output $ 1 $, process it.
- If invalid → output $ 0 $.
For each query:
- If list has at least $ i $ elements → output username at rank $ i $.
- Else → output `DOES NOT EXIST`.
After `PRINT NAMETAGS`:
Output sorted list (by last name $ \to $ first name $ \to $ username, case-insensitive lexicographic) of all **confirmed** participants (finalists + non-finalists), in format:
`FIRSTNAME LASTNAME,SCHOOL,STATUS`
where `STATUS` is `MEDALS? YES` if participant is in top $ p $ of finalists, else `MEDALS? NO`.
**Note**: Finalists are selected from confirmed participants, ranked by original elimination rank (score then penalty). Medals are awarded to top $ p $ finalists. Substitutes are waitlisted accepted who replace absent finalists only if capacity allows.