Description

Dr. Hanks is a renowned expert in BT (Bio-Tech, 生物技术). He is preparing for a cell experiment: culturing cell samples.

Dr. Hanks currently has $N$ types of cells, numbered from $1 \sim N$. A type $i$ cell can split into $S_i$ cells of the same type after $1$ second ($S_i$ is a positive integer). He needs to select one cell of some type, put it into a Petri dish, and let it divide freely for culturing. After some time, he will evenly distribute all cells in the dish into $M$ test tubes to form $M$ samples for the experiment. The number of test tubes $M$ is very large, so ordinary computer primitive data types cannot store it. Fortunately, $M$ can always be expressed as the $m_2$-th power of $m_1$, i.e., $M = m_1^{m_2}$, where $m_1, m_2$ are both positive integers storable in primitive data types.

Note that splitting a single cell is not allowed during the entire experiment. For example, if at some moment there are $4$ cells in the dish, Dr. Hanks can distribute them into $2$ test tubes with $2$ cells per tube, and then start the experiment. But if there are $5$ cells, he cannot evenly divide them into $2$ test tubes. In that case, he must either wait for a while for further division so that the count becomes divisible, or switch to culturing another cell type.

To start the experiment as early as possible, once he has fixed a cell type to culture, he always stops culturing and starts the experiment at the first moment when the number of cells can be evenly divided into $M$ test tubes. Now he wants to know which cell type to culture so that the experiment can start at the earliest time.

Input Format

• The first line contains a positive integer $N$, the number of cell types.
• The second line contains two positive integers $m_1, m_2$ separated by a space, representing the total number of test tubes $M = m_1^{m_2}$.
• The third line contains $N$ positive integers. The $i$-th number $S_i$ indicates that a type $i$ cell becomes $S_i$ cells of the same type after $1$ second.

Output Format

Output a single integer: the minimum time in seconds from the start of culturing to the moment the experiment can begin.

If no choice of cell type can satisfy the requirement, output $-1$.

1 
2 1 
3

-1

2
24 1
30 12

2

Hint

Explanation for Sample Input/Output #1:

After $1$ second, the cells split into $3$; after $2$ seconds, they split into $9$; … It can be seen that the number of cells is always odd, so they can never be evenly divided into $2$ test tubes.

Explanation for Sample Input/Output #2:

For the first type of cell, the earliest time to be evenly divided into $24$ test tubes is after $3$ seconds, while for the second type it is already possible after $2$ seconds (each test tube gets $144 / {24}^1 = 6$ cells). Therefore, the earliest time to start the experiment is after $2$ seconds.

Constraints:

• For $50\%$ of the testdata, $m_1^{m_2} \le 30000$.
• For all the testdata, $1 \le N \le 10000$, $1 \le m_1 \le 30000$, $1 \le m_2 \le 10000$, $1 \le S_i \le 2 \times 10^9$.

NOIP 2009 Junior, Problem 3.

Translated by ChatGPT 5