E - Coprime Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

N 個の整数があります。i 番目の数は A_i です。

「全ての 1\leq i < j \leq N について、GCD(A_i,A_j)=1」が成り立つとき、\{A_i\} は pairwise coprime であるといいます。

\{A_i\} が pairwise coprime ではなく、かつ、GCD(A_1,\ldots,A_N)=1 であるとき、\{A_i\} は setwise coprime であるといいます。

\{A_i\} が pairwise coprime、setwise coprime、そのどちらでもない、のいずれであるか判定してください。

ただし GCD(\ldots) は最大公約数を表します。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq A_i\leq 10^6

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 \ldots A_N

出力

\{A_i\} が pairwise coprime ならば pairwise coprime、setwise coprime ならば setwise coprime、そのどちらでもなければ not coprime と出力せよ。


入力例 1

3
3 4 5

出力例 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1 なので pairwise coprime です。


入力例 2

3
6 10 15

出力例 2

setwise coprime

GCD(6,10)=2 なので pairwise coprime ではありませんが、GCD(6,10,15)=1 なので setwise coprime です。


入力例 3

3
6 10 16

出力例 3

not coprime

GCD(6,10,16)=2 なので、pairwise coprime でも setwise coprime でもありません。

Score : 500 points

Problem Statement

We have N integers. The i-th number is A_i.

\{A_i\} is said to be pairwise coprime when GCD(A_i,A_j)=1 holds for every pair (i, j) such that 1\leq i < j \leq N.

\{A_i\} is said to be setwise coprime when \{A_i\} is not pairwise coprime but GCD(A_1,\ldots,A_N)=1.

Determine if \{A_i\} is pairwise coprime, setwise coprime, or neither.

Here, GCD(\ldots) denotes greatest common divisor.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq A_i\leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

If \{A_i\} is pairwise coprime, print pairwise coprime; if \{A_i\} is setwise coprime, print setwise coprime; if neither, print not coprime.


Sample Input 1

3
3 4 5

Sample Output 1

pairwise coprime

GCD(3,4)=GCD(3,5)=GCD(4,5)=1, so they are pairwise coprime.


Sample Input 2

3
6 10 15

Sample Output 2

setwise coprime

Since GCD(6,10)=2, they are not pairwise coprime. However, since GCD(6,10,15)=1, they are setwise coprime.


Sample Input 3

3
6 10 16

Sample Output 3

not coprime

GCD(6,10,16)=2, so they are neither pairwise coprime nor setwise coprime.