"ab us ke shahar main Thaharein ki kuuch kar jaayein.
'Faraz' aao sitaare safar ke dekhate hain"


Faraz is playing a computer game. The game consists of several levels. You can advance from one level to another. The levels are designed i such a way that it is not possible to come back to a level that you have already visited once. There are multiple starting levels. He can start at any level which has no preceding level and has atleast one other level which he can reach from it.He can end at any level that has no level after it, which means there are multiple end levels. It takes certain amount of time to reach level j from i. However he can explore the level ‘i’ for how much ever time he wants to(explore time should be an integer), but any transition of level (i->j) should take no more than time X.

Simply put, if he reaches level i at time Ti, he has to reach level j (for a (i->j)transition) within time Ti + X. He won’t spend any time exploring the last level.
He has to go to Himalayas for meditation in time T, but at the the same time he wants to explore each level he goes to, as much as possible. He also wants to spend equal amount of time exploring each level. Find the maximum amount of time he can spend exploring in each level.


Input format:

n - number of nodes
a b c - parameters for generating the graph.
n lines will follow denoting the elements of m.
ith integer denotes the number of levels you can reach from the level i-1 ( 0 based ie. the levels are numbered from 0 to n-1).
(the number of levels that can be reached from the (n-1)th level will be zero).
ith level goes to
j=(a * i * i + b * i + c + k * k)%(n-i-1)+i+1 and
weight=(a * (i+1) * (j+1)+b * (i+1) * (j+1)+c)%1000000 for k=0 to mi-1
X T - maximum time you can spend in a level and maximum time he can play the game

Output format:

Maximum amount of time he can spend in exploring each level or "It cannot be done" if not possible.


Constraints:

n,a,b,c <= 10 ^ 6
summation of the number of levels that can be reached from each level<= 10 ^ 6
1 <= time for any move <= 10 ^ 6
1 <= T <= 10 ^ 6
1 <= X <= 10 ^ 6

EXAMPLE:

Input:

1
8 5 10
0
39 11

Output:

It cannot be done

Input:

4
10 9 10
5 0 5 0
15048 8996

Output:

8948