题目描述
给定两个 N 维整数数组 S,T,其各维长度分别为 (a1,…,aN) 和 (b1,…,bN)。每一维的下标从 1 开始。
设 p=(p1,…,pN),且每维满足 1≤pd≤ad−bd+1。若对于所有满足 1≤id≤bd 的下标 (i1,…,iN) 都有
T[i1,…,iN]=S[p1+i1−1,…,pN+iN−1],
则称 p 为一个匹配位置。求字典序最小的匹配位置。
输入格式
第一行一个整数 N。第二、三行分别是 N 个整数 a1,…,aN、b1,…,bN。
第四行给出 S 的 ∏dad 个元素,第五行给出 T 的 ∏dbd 个元素。两个数组的元素都按下标元组的字典序列出,第一维变化最慢,最后一维变化最快。
输出格式
输出 N 个整数 p1,…,pN,表示字典序最小的匹配位置。
数据范围
1≤N≤10,1≤bd≤ad,两个数组各自的元素总数不超过 500000。本站评测保证至少有一个匹配位置,且元素均为 1 或 2。
样例
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
2 2
题目来源