Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学ACM/ICPC竞赛训练暑期课面向全球招生!
欢迎参加hihoCoder挑战赛21,赢取亚马逊礼品卡!
Language:
Recurrent Function
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1119Accepted: 301

Description

Dr. Yao is involved in a secret research on the topic of the properties of recurrent function. Some of the functions in this research are in the following pattern:

\begin{tabular} {ll} \textit{f}(\textit{j}) = \textit{a}$_j$ & for 1$\le$\textit{j}$<$\textit{d}, \\ \emph{f}(\emph{d}$\times$\emph{n}+\emph{j}) = d$\times$f(\textit{n})+\textit{b}$_j$ & for 0$\le$\textit{j}$<$\textit{d} and \textit{n}$\ge$1, \\ \end{tabular}

in which set {ai} = {1, 2, …, d-1} and {bi} = {0, 1, …, d-1}.
We denote:

\begin{tabular}{l}\emph{f}$_x$(\emph{m}) = \emph{f}(\emph{f}(\emph{f}($\cdots$\emph{f}(\emph{m})))) \quad\emph{x} times \\ \end{tabular}

Yao's question is that, given two positive integer m and k, could you find a minimal non-negative integer x that

\begin{tabular}{l}\emph{f}$_x$(\emph{m}) = \emph{k}\\ \end{tabular}

Input

There are several test cases. The first line of each test case contains an integer d (2≤d≤100). The second line contains 2d-1 integers: a1, …, ad-1, followed by b0, ..., bd-1. The third line contains integer m (0<m≤10100), and the forth line contains integer k (0<k≤10100). The input file ends with integer -1.

Output

For each test case if it exists such an integer x, output the minimal one. We guarantee the answer is less than 263. Otherwise output a word "NO".

Sample Input

2
1
1 0
4
7
2
1
0 1
100
200
-1

Sample Output

1
NO

Hint

For the first sample case, we can see that f(4)=7. And for the second one, the function is f(i)=i.

Source

[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