Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
N-dimension Matching
Time Limit: 10000MSMemory Limit: 131072K
Total Submissions: 227Accepted: 101
Case Time Limit: 5000MS


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.


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.


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

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


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator