bee 1934 - Puzzle

Recent discussions in the Internet caused a renewed interest in logical puzzles. In this problem your task is to write a program that solves puzzles as the one shown in the figure below. In this kind of puzzle, the letters inside the grid represent variables, and the numbers represent the sum of the values of the variables in each line or column.

Puzzle

The objective of this type of puzzle is to determine the value of each variable so that the sum of the lines and columns shown is satisfied. But as this type of puzzle is intended for kids, it has a property that makes it easier to solve: it is always possible to find a line or column which contains only one variable whose value is not yet known. So, one way to solve the problem is to proceed step by step, finding the value of one variable at each step.

Given a puzzle, you need to determine the values of the variables that will solve it.

Input

The input consists of several test cases. The first line of each test case contains two integers L (1 ≤ L ≤ 100) and C (1 ≤ C ≤ 100) indicating the number of lines and the number of columns in the puzzle. Each of the next L lines contains C names of variables, followed by an integer S, the sum of the variables in that line (−10⁸ ≤ S ≤ 10⁸). The last line contains C integers X_i (−10⁸ ≤ X_i ≤ 10⁸), indicating respectively the sum of the variables in column i. The names of the variables are formed by exaclty two lower case letters, from ‘a’ to ‘z’. All puzzles have a unique solution, in which all variables are integer numbers between −10⁶ and 10⁶.

Output

For each test case, your program must produce one line for each variable of the puzzle, containing the name of the variable and its integer value. The variables should be produced in ascending alphabetical order; in other words, respecting order

aa, ab, . . . , az, ba, bb, . . . , za, zb, . . . , zz.

Input Example	Output Example
4 5 df bb cg df df 11 ee az cg az ee 6 df cg cg df df 10 az az cg az az 6 6 7 8 6 6	az 1 bb 3 cg 2 df 2 ee 1

Input Example

Output Example

4 5

df bb cg df df 11

ee az cg az ee 6

df cg cg df df 10

az az cg az az 6

6 7 8 6 6

az 1

bb 3

cg 2

df 2

ee 1


3 4 aa bb cc dd 10 aa bb cc dd 10 aa bb cc dd 10 3 6 9 12	aa 1 bb 2 cc 3 dd 4

3 4

aa bb cc dd 10

3 6 9 12

aa 1

bb 2

cc 3

dd 4


3 3 aa zz aa 27 vv zz aa -5 kk kk aa 40 15 -7 54	aa 18 kk 11 vv -14 zz -9

3 3

aa zz aa 27

vv zz aa -5

kk kk aa 40

15 -7 54

aa 18

kk 11

vv -14

zz -9