Back

Fireflies

Worth 10 point(s) - Runtime Limit: 2 seconds

Introduction

You have a set of N (80 ≤ N ≤ 100) jars with a firefly inside of each, numbered from 1 to N. The jars are connected to four magic lighters. Information about each lighter is shown below.

There is a counter C which records the total number of times the lighters were used. At the beginning, all the jars are LIT and the counter C is set to zero.

Given the number of jars, N, the number of times the lighters were used (up to 10,000), and the state of some of the jars (e.g., jar 7 is lit), output all the possible states the jars could be in.

Input:
The first line contains the integer D indicating the number of datasets that follow. The first line of a dataset contains the number N and the second line the final value of counter C. The third line lists the jar numbers you are informed to be LIT in the final configuration, separated by one space and terminated by the integer -1. The fourth line lists the jar numbers you are informed to be NOT LIT in the final configuration, separated by one space and terminated by the integer -1.

Output:
Each line has N characters, where the first character represents the state of jar 1 and the last character represents the state of jar N. A 0 (zero) stands for a jar that is NOT LIT, and a 1 (one) stands for a lamp that is LIT. Order the number in numerical order (by binary value of the item with the leftmost bit being the least significant digit).
If there are no possible configurations, put IMPOSSIBLE.

Sample Input

1
10
1
-1
7 -1

Sample Output

0000000000
0110110110
0101010101