Shootout in London

3.3

8 votes
Approved, Easy, Hiring, Math, Primality test, Sieve
Problem

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 ith street is denoted by the number A[i]. Gunmen do not enter streets that are denoted by a prime number i.e. ith 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 ith integer is the index (1-based) of the nearest safe street. The distance between cities i and j is given by |ij|. 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 ith integer denotes A[i] .

Output:
Print the answer on a single line.

Constraints:

1N5×105

1A[i]106

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

.

Editor Image

?