Mastermind II

Time limit1sMemory limit128 MB

Summary

Given c codes and their A/B compatibility scores with a hidden code of length c, find the lexicographically smallest code consistent with all scores.

Level: Medium7 of 10
Topics: Brute force, Backtracking, Implementation, Combinatorics
Solved: No attempts yet

Problem

Consider sequences that satisfy all of the following conditions:

the length of the sequence is $c$ ;
every element is a digit from $1$ to $9$ ;
no digit is repeated within the sequence.

Such a sequence is called a code.

Given two codes, we measure their compatibility with two numbers:

$A$ is the sum of the digits that appear in both codes at the same position.
$B$ is the sum of the digits that appear in both codes but at different positions.

There is one fixed but unknown code. You are given $c$ codes together with the compatibility $(A, B)$ that each of them has with this unknown code. Find a code that is consistent with all of these compatibility values.

Input

The first line contains one integer $c$ ( $1 \le c \le 9$ ).

Each of the next $c$ lines describes one given code together with its compatibility with the unknown code. A line contains $c + 2$ non-negative integers separated by single spaces: the first two are the compatibility values $A$ and $B$ of this code, and the remaining $c$ integers are the distinct digits (each from $1$ to $9$ ) that form the code.

Output

Print $c$ digits separated by single spaces: a code (distinct digits from $1$ to $9$ ) whose compatibility with every given code matches the input.

It is guaranteed that at least one such code exists. If several codes satisfy all the constraints, print the lexicographically smallest one (compare the two codes digit by digit from left to right).

Examples1

Example 1
Input
```
3
4 0 4 9 7
0 10 6 7 4
0 5 9 4 1
```
Expected output
```
4 1 6
```