   Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
N-dimension Matching
 Time Limit: 10000MS Memory Limit: 131072K Total Submissions: 222 Accepted: 99 Case Time Limit: 5000MS

Description

Let us consider an n-dimension matching problem of two matrices. Here the index number of each dimension of a matrix starts at 1. For two n-dimension matrixes S and T, if there is a position (p1, p2, p3, p4, …,pn) which satisfies that each element at the position (t1, t2, t3, t4, …,tn) in T is the same as the element at the position (p1 + t1 - 1, p2 + t2 - 1, p3 + t3 - 1, p4 + t4 - 1, …,pn + tn - 1) in S, we call it’s a matching position. So the n-dimension problem is to compute the matching position for given S and T. You can assume that the traditional string matching problem is the 1-dimension version of this problem, and the normal matrix matching problem is the 2-dimension version.

Input

The first line contains the positive number n, which is not larger than 10.
The second line contains n positive numbers a1, a2, a3, ...,an, representing the range of each dimension of matrix S.
The third line contains n positive numbers b1, b2, b3, ...,bn, representing the range of dimensions of matrix T.
The fourth line gives the elements in S.
The fifth line gives the elements in T.

To give out an n-dimension matrix with size c1 * c2 * c3 * ... * cn in a line, we will give the element at the position (d1, d2, d3, …,dn) in the matrix as the (c2 * c3 * ... * cn * (d1 – 1) + c3 * c4 * ... * cn * (d2 – 1) + ... + cn * (dn - 1 – 1) + dn)–th element in the line.

We guarantee that bi <= ai, elements in S and T are all positive integers that are not larger 100, and the number of the elements in S and T are both not larger than 500000.

Output

You should output n numbers in a line, p1, p2, p3, …,pn, representing the matching position. Please print the lexically smallest one if there are many. We guarantee that there is at least one matching position.

Sample Input

```2
4 4
2 2
3 2 1 1 2 2 2 1 1 2 2 2 1 1 2 2
2 2 2 2
```

Sample Output

`2 2`

Source

[Submit]   [Go Back]   [Status]   [Discuss] Home Page Go Back To top