This page is still under construction.

Parts of this page are still being built. What you see may change.

Oar Tester

Time limit1sMemory limit512 MB

Summary
Assign each of n oar types a positive integer strength so every pair sums to at most x_ij and at least one of the two reaches y_ij.
Level

Medium7 of 10

Topics
Graph, Shortest path, Greedy
Solved
No attempts yet

Problem

There are n oar types. For every pair (i,j), the sum of their strengths is at most x_ij, and at least one of them is at least y_ij. Output any array of positive strengths that satisfies all constraints.

Input

The first line contains n. The next n lines hold matrix x, then a blank line, then n lines for matrix y.

Output

Print n positive integers separated by spaces.

Constraints

  • 1≤n≤3001 \leq n \leq 300

Examples1

  1. Example 1

    Input
    3
6 8 5
7 6 6
5 7 7

2 3 1
3 1 1
2 1 3
    Expected output
    3 2 3