#P3857. Multiplication table

    ID: 3060 传统题 1000ms 64MiB 尝试: 45 已通过: 19 难度: 5 上传者: 标签>CF1700普及+/提高-不变量分析向下取整与向上取整时间戳避免清空数组By镇海中学

Multiplication table

Multiplication table

Problem Description

Teacher Mai has a multiplication table in base p. For example, the following is a multiplication table in base 4:

  • 0 1 2 3 0 00 00 00 00 1 00 01 02 03 2 00 02 10 12 3 00 03 12 21 But a naughty kid maps numbers 0..p-1 into another permutation and shuffle the multiplication table. For example Teacher Mai only can see: 11=11 13=11 12=11 10=11 31=11 33=13 32=12 30=10 21=11 23=12 22=31 20=32 01=11 03=10 02=32 00=23 Teacher Mai wants you to recover the multiplication table. Output the permutation number 0..p-1 mapped into. It's guaranteed the solution is unique.

Input

There are multiple test cases, terminated by a line "0". For each test case, the first line contains one integer p(2<=p<=500). In following p lines, each line contains 2p integers. The (2j+1)-th number x and (2j+2)-th number y in the i-th line indicates equation ij=xy in the shuffled multiplication table. Warning: Large IO!

Output

For each case, output one line. First output "Case #k:", where k is the case number counting from 1. The following are p integers, indicating the permutation number 0..p-1 mapped into.

Sample Input

4
2 3 1 1 3 2 1 0
1 1 1 1 1 1 1 1
3 2 1 1 3 1 1 2
[b]1 0 1 1 1 2 1 3[/b]
0

Sample Output

Case #1: 1 3 2 0

Author

xudyh

Source

2014 Multi-University Training Contest 8