| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 31 | 10 | 9 | 32.143% |
Longlandia is a very long country. All of its $n$ cities are located along a line segment. If we enumerate them from the beginning to the end of the segment, the $i$-th city has $a_i$ inhabitants.
You need to get from city $s$ to city $f$. For this purpose, an infinite number of taxis called Kaban-2, Kaban-3, Kaban-4, Kaban-5, ... operate in Longlandia. A taxi named Kaban-$m$ can take you from city $i$ to city $j$ if the numbers of inhabitants in all cities from $i$ to $j$ inclusive are congruent modulo $m$. Formally, for any integer $k$ such that $\min\{i, j\} \le k \le \max\{i, j\},ドル the relation $a_k \equiv a_i \pmod m$ must hold.
Find the smallest number $Q$ of taxi calls required to get from city $s$ to city $f,ドル and output $Q$ lines describing the route. If it is impossible to reach the destination by taxi, output "Impossible".
The first line contains an integer $n$: the number of cities in Longlandia (2ドル \le n \le 2 \cdot 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$: the population of each city (1ドル \le a_i \le 10^9$).
The third line contains two integers $s$ and $f$: the starting and finishing city numbers (1ドル \le s, f \le n$; $s \ne f$).
Let $Q$ be the smallest number of taxi calls required to get from city $s$ to city $f$. Output $Q$ lines of the form "Kaban-$m_i$ $s_i$ $f_i$", indicating that the $i$-th trip will be made by taxi Kaban-$m_i$ and will take you from city $s_i$ to city $f_i$ (1ドル \le s_i, f_i \le n$; 2ドル \le m_i \le 10^9$). The following equalities must hold: $s_1 = s$; $f_Q = f$; $s_{i + 1} = f_i$. And, of course, taxi Kaban-$m_i$ must be able to take you from city $s_i$ to city $f_i$.
If it is impossible to reach from $s$ to $f$ with any number of taxi calls, output the word "Impossible".
Letter case does not matter, so you can output, for example, "kaBAN" and "IMPossiBle".
6 1 2 3 4 5 6 5 3
Impossible
8 1 16 20 20 20 23 7 8 1 7
Kaban-5 1 2 Kaban-4 2 5 Kaban-3 5 6 Kaban-8 6 7
11 55 55 55 55 55 55 55 55 55 55 55 7 2
kaBAn-239239239 7 2