SOLVE

LATER

Shootout in London

Problem

Editorial

Analytics

There is a major shootout going on in London. Gunmen can be encountered in most of the streets and only a few of them are safe. Sherlock is given the responsibility to ensure the safety of the people by asking them to shift to the nearest safe street.

There are *N* streets on the road. The \(i^{th}\) street is denoted by the number \(A[i]\). Gunmen do not enter streets that are denoted by a prime number i.e. \(i^{th}\) street is safe, if \(A[i]\) is a prime.

Help Sherlock find the nearest safe street for people trapped in all the *N* streets i.e. print *N* integers, where the \(i^{th}\) integer is the index (1-based) of the nearest safe street. The distance between cities *i* and *j* is given by \(|i-j|\). For any city *j*, if there exists no safe city *i*, such that people of city *j* can move to city *i*, print *1* for it.

**Note** :

-If there are multiple nearest safe streets, print the one with the lower index.

**Input**:

The first line contains a single integer *N* denoting the number of cities. The next line contains *N* integers, where the \(i^{th}\) integer denotes \(A[i]\) .

**Output**:

Print the answer on a single line.

**Constraints**:

\( 1 \le N \le 5 \times 10^5 \)

\( 1 \le A[i] \le 10^6 \)

Explanation

.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Swift-4.1,
Visual Basic

Initializing Code Editor...

{"6767003": "/pagelets/show-submission/algorithm/shootout-in-london-1/", "c03d9ca": "/pagelets/recommended-problems/algorithm/shootout-in-london-1/", "922e693": "/pagelets/suggested-problems/algorithm/shootout-in-london-1/", "d03d76e": "/pagelets/problem-author-tester/algorithm/shootout-in-london-1/", "4613069": "/pagelets/problems-hint/algorithm/shootout-in-london-1/"}

realtime.hackerearth.com

80

9154231d0ac01c4433d78d89a1cad80ab123dc61

58a29e5cae2309f04b28

/realtime/pusher/auth/