Electrification

Interview

Time limit2sMemory limit256 MB

Summary

Given switch-to-lamp toggle mappings and a sequence of switch flips, compute and print the final on/off state of each lamp using parity counting.

Level: Easy2 of 10
Topics: Simulation, Bit manipulation
Solved: No attempts yet

Problem

Ellen is designing the light-management system for a luxury hotel room. The room has n switches and m lamps.

The room designers assigned each lamp a set of switches. A lamp changes its state (it turns on if it was off, and turns off if it was on) every time one of the switches assigned to it is flipped. A lamp never reacts to a switch that is not assigned to it.

Initially every switch is off and every lamp is off. Ellen then flips a sequence of switches, one at a time. After all of the flips have been performed, report the final state of every lamp.

Input

The first line contains two integers n and m — the number of switches and the number of lamps (1 ≤ n, m ≤ 10).

Each of the next n lines contains m characters. The j-th character of the i-th line is 1 if switch i is assigned to lamp j, and 0 otherwise. Every lamp is assigned at least one switch, and every switch is assigned to at least one lamp.

The next line contains an integer q — the number of switch flips (0 ≤ q ≤ 1000).

The following line lists q integers s_1, s_2, …, s_q (1 ≤ s_k ≤ n): the switches that are flipped, in the given order. When q = 0 this line is empty or omitted.

Output

Print a single line of m characters. The j-th character must be 1 if lamp j is on after all the flips have been performed, and 0 otherwise.

Examples5

Example 1
Input
```
5 3
101
001
010
001
001
4
1 3 3 5
```
Expected output
```
100
```
Example 2
Input
```
2 2
01
10
1
1
```
Expected output
```
01
```
Example 3
Input
```
2 2
01
10
0
```
Expected output
```
00
```
Example 4
Input
```
1 1
1
3
1 1 1
```
Expected output
```
1
```
Example 5
Input
```
3 4
1010
0110
1001
4
1 2 3 2
```
Expected output
```
0011
```