XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: passatempo.x, onde x deve ser c, cpp, java, js ou py

Passatempo

Desafios de lógica e matemática são um ótimo passatempo, atraindo um grande número de praticantes, e um mercado que envolve aplicativos para celular, atividades on-line, revistas especializadas e até mesmo cursos na internet para melhorar o desempenho!

Neste problema sua tarefa é escrever um programa que resolva um novo passatempo, mostrado na figura abaixo. O passatempo é composto por um quadriculado com letras dentro de cada célula e números ao lado de cada linha ou coluna do quadriculado. As letras dentro de cada célula representam variáveis, e os números representam as somas dos valores das variáveis em cada linha ou coluna.

O objetivo desse passatempo é determinar o valor de cada variável de modo a satisfazer as somas das linhas e colunas mostradas. Para permitir que um número maior de pessoas consiga resolver o passatempo, ele tem uma propriedade que facilita a sua solução: sempre é possível encontrar uma linha ou coluna em que há apenas uma variável cujo valor ainda é desconhecido. Assim, uma possível maneira de resolver o problema é, a cada passo da solução, encontrar o valor de uma variável.

Sua tarefa é, dado um passatempo, determinar os valores das variáveis que o solucionam.

Entrada

A primeira linha contém dois inteiros L e C indicando o número de linhas e o número de colunas do passatempo. Cada uma das L linhas seguintes contém C nomes de variáveis, seguidos de um inteiro S, a soma resultante das variáveis dessa linha. A última linha contém C inteiros Xi, indicando respectivamente a soma das variáveis na coluna i. Nomes de variáveis são formados por precisamente duas letras minúsculas, de 'a' a 'z'. Todos os passatempos têm solução única, em que todas as variáveis são números inteiros.

Saída

Seu programa deve produzir uma linha para cada variável do passatempo, contendo o nome da variável e o seu valor inteiro. As variáveis devem ser escritas em ordem alfabética crescente, ou seja, respeitando a ordem aa, ab, …, az, ba, bb, …, za, zb, …, zz.

Restrições

  • 1 ≤ L ≤ 100
  • 2 ≤ C ≤ 100
  • -108 ≤ S ≤ 108
  • -108 ≤ Xi ≤ 108

Exemplos

Entrada
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
Saída
az 1
bb 3
cg 2
df 2
ee 1
	

 

Entrada
3 4
aa bb cc dd 10
aa bb cc dd 10
aa bb cc dd 10
3 6 9 12
Saída
aa 1
bb 2
cc 3
dd 4
	

 

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

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação