Problem: contest (2018 finals)

The 2018 Hacker Cup finals are underway! The contest is being held in a room
with 2 rows of **N** desks each, with finalists sitting at some of them.

One of the finalists, Alex, is sitting at the leftmost desk in the front row.
Another finalist, Borys, is sitting at the rightmost desk in the front row.
Unfortunately, both of them find themselves distracted by the contest room's
environment — Alex is a bit too hot on his side of the room, while Borys is a
bit too cold. If only they could switch places! Unfortunately, this would be
against the rules, but if they work together with some other contestants,
perhaps they can manage it without the contest organizers noticing...

The initial state of each row of desks can be represented by a string of **N**
characters, with the _i_th character corresponding to the _i_th desk from the
left in that row. Each character is one of the following:

  * `A` \- Alex's desk (guaranteed to appear exactly once, as the leftmost desk in the front row) 
  * `B` \- Borys's desk (guaranteed to appear exactly once, as the rightmost desk in the front row) 
  * `*` \- A cooperative finalist's desk 
  * `#` \- An uncooperative finalist's desk 
  * `.` \- An unoccupied desk 

At any point, a single finalist may move from their current desk to an
adjacent, currently-unoccupied desk. Two desks are considered adjacent if
either they're in the same column, or they're directly side-by-side in the
same row. However, the finalists won't be foolish enough to move sideways
between two desks in the front row, as that would surely attract the contest
organizers' attention.

Alex, Borys, and any cooperative finalists may all move between desks in this
fashion. On the other hand, uncooperative finalists are too busy actually
competing, and will never move from their original desks.

Assuming that Alex, Borys, and the cooperative finalists all work together, is
it possible for Alex and Borys to switch seats (in other words, for Alex to
occupy the front row's rightmost desk while Borys simultaneously occupies its
leftmost desk) without the contest organizers noticing?

### Input

Input begins with an integer **T**, the number of parallel universes in which
the 2018 Hacker Cup is occurring. For each universe, there are two lines of
**N** characters each, as described above. The first line is the front row of
desks, and the second line is the back row of desks.

### Output

For the _i_th universe, output a line containing "Case #_i_: " followed by the
string "Possible" if Alex and Borys can successfully switch seats, or
"Impossible" otherwise.

### Constraints

1 ≤ **T** ≤ 200  
2 ≤ **N** ≤ 2,000  

### Explanation of Sample

In the first case, the contest room looks as follows (with grey lines
indicating adjacent desks which finalists may potentially move between). The
blue circle denotes a cooperative finalist, and the gray square denotes an
uncooperative finalist. A and B denote Alex and Borys respectively.

One possible sequence of moves resulting in Alex and Borys switching places is
as follows (with some moves omitted):

In the second case, Alex and Borys are unable to get past one another and
switch seats.



Sample input:
10
A#..B
..*..
AB
..
A.B
...
A.B
***
A.#.B
.*.*.
A########B
..........
A#*#.*##*B
**.**..*.*
A*.*#*#*.B
**#..**.*.
A*#*###**B
...****...
A##*.#*##.##**B
****.****.*****


Sample output:
Case #1: Possible
Case #2: Impossible
Case #3: Possible
Case #4: Impossible
Case #5: Possible
Case #6: Impossible
Case #7: Possible
Case #8: Impossible
Case #9: Possible
Case #10: Impossible



Code: // Contest Environment
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 2002

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N;
	int i,b,c;
	bool ans;
	char A[LIM],B[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			printf("Case #%d: ",t);
			// input
			scanf("%s%s",&A,&B);
			N=strlen(A);
			// bottom blocked?
				Fox(i,N)
					if (B[i]=='#')
						goto Imp;
			// count blanks
			b=0;
				Fox(i,N)
					b+=(A[i]=='.')+(B[i]=='.');
			// find sequences of blocked top-row cells
			c=0;
				Fox(i,N)
					if (A[i]=='#')
						c++;
					else
					{
							if (b<c+3)
								goto Imp;
						c=0;
					}
			// output
			printf("Possible\n");
			continue;
Imp:;
			printf("Impossible\n");
		}
	return(0);
}