During summer, Bob doesn't want to go out and socialize. He chooses to stay at home and play a game called Fans Only.
In the game, there are $$$N$$$ fans, $$$M$$$ extension sockets, and a master socket which is connected to the power source. The fans are numbered from $$$1$$$ to $$$N$$$. The extension sockets are numbered from $$$1$$$ to $$$M$$$, the $$$i$$$-th ($$$1 \le i \le M$$$) socket has $$$K_{i}$$$ slots, linearly ordered from left to right. For each extension socket, it is guaranteed that $$$K_{i} \ge 2$$$ with exactly one leftmost socket and one rightmost socket. The structure of an extension socket is shown below.
Each of the fans and extension sockets has a plug which can be plugged into an extension socket or the master socket. All the fans and extension sockets are assigned to a character either L, R or A which restricts where it can be plugged into.
- Fans/Extension sockets assigned to character L can only be plugged into the leftmost slot of the extension sockets or the master socket, but not other slots of an extension socket;
- Fans/Extension sockets assigned to character R can only be plugged into the rightmost slot of the extension sockets or the master socket, but not other slots of an extension socket;
- Fans/Extension sockets assigned to character A can plug into any slots of the extension sockets or the master socket;
In the game, there is only one master socket which is connected to the power source. Bob's goal is to find a way to operate all $$$N$$$ fans by connecting them to the power source directly or indirectly. Help Bob determine if it is possible. Note that it might not be necessary to plug in all the extension sockets.
The first line contains two integers $$$N$$$ $$$(1 \le N \le 10^5)$$$ and $$$M$$$ $$$(0 \le M \le 10^5)$$$.
The second line contains $$$N$$$ characters either L, R or A, separated by a space, indicating where the $$$i$$$-th fan can be plugged into.
The third line contains $$$M$$$ characters either L, R or A, separated by a space, indicating where the $$$i$$$-th extension socket can be plugged into.
The fourth line contains $$$M$$$ integers $$$K_i$$$ ($$$2 \le K_i \le 10^5$$$), indicating the number of sockets that the $$$i$$$-th extension socket has.
The only line should contain Possible or Impossible, as described in the statement above.
2 1 L L A 2
Impossible
2 1 L R A 2
Possible
3 2 A R A L R 3 2
Possible
For sample 1, Fan $$$1$$$ and Fan $$$2$$$ are both assigned to character L; they can only be plugged into the leftmost slot of the extension socket. However, the extension socket has only 2 slots, the leftmost and the rightmost. In this scenario, one of the fans cannot be connected to the master socket. Therefore, it is not possible to operate all the fans.
For sample 2, Fan $$$1$$$ and Fan $$$2$$$ are assigned to characters L and R respectively. As there is exactly one leftmost slot and one rightmost slot on the extension socket, both fans can be connected to the extension socket, and the extension socket can be connected to the master socket. Therefore, Fan $$$1$$$ and Fan $$$2$$$ can be operated.
For sample 3, Fan $$$1$$$ and Fan $$$3$$$ are both assigned to character A; Fan $$$2$$$ is assigned to character R. Extension socket $$$1$$$ and $$$2$$$ are assigned to characters L and R respectively. According to the figure above, one of the possible arrangements is plugging the extension socket $$$1$$$ into the leftmost slot of the extension socket $$$2$$$ and plugging the extension socket $$$2$$$ into the master socket. Fan $$$2$$$ must be plugged into the rightmost slot of one of the extension sockets, while the remaining $$$2$$$ fans can be plugged into any empty slots of the extension sockets.
