The bipolar monster strikes again! And the peaceful Line city is his target. As the name suggests,
Line city consists of 𝑁 neighborhoods numbered 1, 2, 3, … , 𝑁 arranged from left to right in a line.
The bipolar monster makes bipolar operations on the town. An operation consists of choosing a
neighborhood X that is not destroyed yet and that is not the leftmost nor the rightmost with this
property, with the purpose of destroying it. However, as the monster is bipolar, right after
choosing 𝑋, he decides to destroy the 2 yet undestroyed neighborhoods immediate to the left and to
the right of 𝑋.
In other words, let’s assume that at some point, the neighborhoods that are not destroyed yet are, in
order from left to right 1 ≤ 𝑖1 < 𝑖2 < 𝑖3 < ⋯ < 𝑖𝐾 ≤ 𝑁. X should be one of these neighborhoods,
but not the leftmost nor the rightmost. Therefore, 𝑋 = 𝑖𝑗
for 𝑗 with 1 < 𝑗 < 𝐾. For this choice of 𝑗,
the monster will destroy the neighborhoods indexed 𝑖𝑗−1 and 𝑖𝑗+1
Our monster is not that much of a monster as you’d think – the 2 of its personalities don’t want to
destroy neighborhoods just for fun, they want to make their father proud. The monster knows what
exact final configuration of neighborhoods his father would like to see, and so he’d like to make
his choices of 𝑋 in such a way that the final configuration of neighborhoods left undestroyed will
please his father. His father’s favorite configuration is also a subsequence of the N cities 1 ≤ 𝑝1 <
𝑝2 < 𝑝3 < ⋯ < 𝑝𝑄 ≤ 𝑁.
Sometimes, parents’ expectations are a bit unrealistic, and so can be the case with monsters! It is
not even guaranteed that with the given operation (which is the only way the monster can destroy
cities, given his bipolarity) the desired subsequence of neighborhoods can be achieved. That’s why
the monster would like to know if he can make a proper choice of his moves so that he will
achieve the given subsequence. Not only that, but, as you probably guessed, he wants to know a
way of doing so, if possible.
You want to help the monster to make his father proud because he’s already been through enough
(it’s hard to be a bipolar monster). He will give you a list of several cities similar to Line city and
of the configurations his father wants to achieve for each such city (both the configuration and the
value of 𝑁 may differ from a city to another). For each city, you need to tell the monster if he can
carry out his plan and, if so, how it can do that.
On the first line of the input there will be a number 𝑇 – the number of cities the monster is
considering altering in order to make his father proud.
The next 2𝑇 lines contain the description of the cities and monster’s father’s desired final
configuration of the cities, in the following format:
𝑝1, 𝑝2, … , 𝑝q