Max is the sole serious monarch of Lovingland, a nation made of ~N+1~ cities arranged in a road. However, as a youthful country, none of these cities are connected! Hence, Max wants to build ~N~ roads between each consecutive city.

To do so, he has access to ~M~ types of road blocks with a length of ~L_i~ and a cost of ~C_i~ each. To form an entire road, he can combine some number of blocks together. The length of this road is equal to the sum of the lengths of the road blocks that form it, and its cost is defined similarly.

Each city has a radius ~r_i~, and the distance between city ~i~ and ~i+1~ is ~R_i~. The road that connects these two cities must be within ~r_i + r_{i+1}~ of ~R_i~ inclusive. Additionally, its total cost cannot exceed ~M_i~ and it cannot use more than ~A_{i,j}~ of the ~j~-th road block. Finally Max can cut off a chunk of road of length ~L_j~ and sell it to gain ~C_j~, and he can do this at most ~S_{i,j}~ for the ~i~-th road and ~j~-th road block. Max cannot spend a negative amount of money. Can you find a configuration of roads that satisfies these constraints?

Note: for this problem, your team may use any publicly available internet resource, as long as you do not communicate with any other person.

Constraints

~1\le M\le7~ Except subtask 3.

~1\le N\le10~

~1\le C_i\le10^{16}~

~1\le L_i\le10^{16}~

~1\le R_i+r_i+r_{i_1}\le10^{16}~

~0\le r_i+r_{i_1}\le10^{3}~ Except subtask 3.

~1\le M_i\le10^{16}~

~1\le A_{i,j}<=100~

~1\le S_{i,j}<=100~

Subtask 1 [10%]

~M\le2~

Subtask 2 [30%]

~M_i\le10^3~

Subtask 3 [60%]

~0\le r_i+r_{i_1}\le10^{11}~

~M\le 6~

Input Specification

The first two lines contain the two integers ~M~ and ~N~. The next line contains ~M~ space separated integers, denoting the length ~L_i~ of each block. The next line contains ~M~ space separated integers, denoting the cost ~C_i~ of each block. The next line contains ~N~ space separated integers, denoting the distance ~R_i~ between each pair of cities. The next line contains ~N~ space separated integers, denoting the maximum budget ~M_i~ allowed for each road. The next line contains ~N+1~ space separated integers, denoting the radius ~r_i~ of each city. The next ~N~ lines contain ~M~ space separated integers. The ~j~-th integer on the ~i~-th line denotes the maximum block count ~A_{i,j}~. The next ~N~ lines contain ~M~ space separated integers. The ~j~-th integer on the ~i~-th line denotes the maximum times Max can sell ~S_{i,j}~.

Output Specification

Output ~N~ lines, each containing ~M~ integers, denoting how the net amount of each block Max should use to build the road between cities ~i~ and ~i+1~. The net amount is denoted as the amount of times Max purchased a block ~j~ minus the amount of times Max sold a block ~j~. If it is not possible to build the given road, output impossible for the given road.

Sample Input

2 3
5 2
8 4
10 15 18
17 25 30
1 2 0 1
2 3
1 8
2 2
0 0
0 0
0 0

Sample Output

1 1
1 4
impossible