Problem:


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.



Sample input:
3
3 4 5


Sample output:
pairwise coprime

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
# Original source code : 

"""
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all($) begin($), end($)
#define rall($) rbegin($), rend($)

using int128 = __int128_t;

int128 power(int128 base, int128 e, int128 mod) {
  int128 res = 1;
  base %= mod;
  while (e) {
    if (e & 1) (res *= base) %= mod;
    (base *= base) %= mod;
    e >>= 1;
  }
  return res;
}

bool is_prime(int64 n) {
  if (n < 2 || ~n & 1) return n == 2;
  int s = __builtin_ctzll(n - 1);
  int64 d = (n - 1) >> s;
  for (int64 base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
    int128 x = base % n;
    if (!x) continue;
    x = power(x, d, n);
    if (x == 1 || x == n - 1) continue;
    bool ok = false;
    for (int i = 0; i < s - 1; ++i) {
      (x *= x) %= n;
      if (x == n - 1) {
        ok = true; break;
      }
    }
    if (!ok) return false;
  }
  return true;
}

int64 binary_gcd(int64 x, int64 y) {
  if (x < 0) x = -x;
  if (y < 0) y = -y;
  if (!x) return y;
  if (!y) return x;
  int s = __builtin_ctzll(x | y);
  x >>= __builtin_ctzll(x);
  do {
    y >>= __builtin_ctzll(y);
    if (x > y) std::swap(x, y);
    y -= x;
  } while (y);
  return x << s;
}

template <class T>
inline std::vector<T> connect(const std::vector<T> &a,
                              const std::vector<T> &b) {
  std::vector<T> c(a.size() + b.size());
  std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
  return c;
}

template <class T>
std::vector<T> factor(T n) {
  if (n <= 1) return {};
  if (is_prime(n)) return {n};
  if (~n & 1) return connect({2}, factor(n >> 1));
  for (T c = 1;; ++c) {
    T x = 2, y = 2, d;
    do {
      x = ((int128)x * x + c) % n;
      y = ((int128)y * y + c) % n;
      y = ((int128)y * y + c) % n;
      d = binary_gcd(x - y, n);
    } while (d == 1);
    if (d < n) return connect(factor(d), factor(n / d));
  }
}

template <class T>
std::vector<std::pair<T, int>> RunLengthEncoding(const std::vector<T>& vec) {
  std::vector<std::pair<T, int>> ret;
  int sz = vec.size();
  int beg = 0;
  while (beg < sz) {
    int ed = beg;
    while (ed + 1 < sz && vec[beg] == vec[ed + 1]) ++ed;
    int len = ed - beg + 1;
    ret.emplace_back(vec[beg], len);
    beg = ed + 1;
  }
  return ret;
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vector<int> a(n); for (int& e : a) cin >> e;
  vector<int> cnt(1010101, 0);
  bool p_coprime = true;
  for (int e : a) {
    auto v = RunLengthEncoding(factor(e));
    for (auto p : v) {
      if (cnt[p.first] > 0) {
        p_coprime = false; break;
      }
      ++cnt[p.first];
    }
    if (!p_coprime) break;
  }

  if (p_coprime) {
    cout << "pairwise coprime" << endl;
  } else {
    int g = 0;
    for (int e : a) g = binary_gcd(g, e);
    if (g == 1) {
      cout << "setwise coprime" << endl;
    } else {
      cout << "not coprime" << endl;
    }
  }

  return 0;
}
"""

import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91AQ1on00000KmY&$00000NIw7o0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000f*$|?00000f*$|?00000001BW000000RR911^@s67%cz*000007%d<G000007%d<G0000000RI300000XaxWO00000001BW000000ssI21^@s6Ff9N800000FfAYe00000FfAYe000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4{2KrO00000{2KrO00000{2KrO00000bN~PV00000bN~PV000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa47%cz*000007%d<G000007%d<G00000=mG!$00000=mG!$000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04${Z5rdDwGLJa3b4<LWD-#V+!1N0ssI27ytkO0RR911^@s6000mI0RRL57ytkO000006qpP{bCw4J000000000000000000000000000000yZ`_I5&!@I00000000000000000000+yDRo5&!@I00000000000000000000?*RY+A^-pY00000000000000000000)Bykh5&!@I00000000000000000000U;qFB5&!@I00000000000000000000RR9105&!@I00000000000000000000=m7u#5&!@I00000000000000000000mjM6(5&!@I00000000000000000000+W`Oo5&!@I00000000000000000000)c^nh5&!@I00000000000000000000VF3UD5&!@I00000000000000000000!vO#Q5&!@I0000000000000000000069E7K5&!@I00000000000000000000X8`~J5&!@I00000000000000000000uK@r65&!@I00000000000000000000{s9005&!@I00000000000000000000{r~^~5&!@I000000000000000000009{>OVAOHXW00000000000000000000paB2?5&!@I000000000000000000001_A&85&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000qyPW_5&!@I00000000000000000000e*pjh5dawgKrkQx000005CH%H00000n*aa+5dawgU@;&7000007y$qP000000BmVub97{5D=RK@Z!R_fUtec!Z*E_6bYXIIUta)UNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnNmNZ=a%E>}b97~LR82!{Z*FB&VPb4$0AE^8Q)zN@MN(-1Us_XiG-YmNY)NBNbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeUc=T2pj0V`**xUs_I6bU0~mb6;X%b7eG1ZfSHxF-3L&Us_XiF*jddbZByKcVA**WM5%yY;R+B0AE^UY*2OpUs_I6bU0~mb6;X%b7e6#b9ruKUw3JAXkT-5WNB|jVgO%XXLxvDaAk6HZ*F01X>@sCb}#^6T2pi}HeX+Fb98cLVQpV&ZgXXFbV*}VbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeXOnQ!`&|0AE^ecWnS)T251RIB9QlUt(c%Wi&}{X>>y|MRovRT2pj1V{dhI0BmVuXJcbub1rjlE-?UKUu|z>bZIjHUsY~*X>Md+Qe|^>ZDjyoUv+J7WOQjW0BmVuV=i-VE;ayPUvqR}V{2byXlq|)VQFjtb98cSWo`gpUt@S-Utx4*cxiM1ZDnm^aCrb<Ut@S-UuJ1;VQgu7WdLnuZEbIMWdL7aY-wU+UvqR}a&%v9VQFpvM?*tjGcGUyM@&gVLtip3Gyq3TNkT(kGA=PR07pzoLPK9NE;24P07F<<K|)DiF)lLzM@&gVLs(c}GcGhPIRHmYNkT(dSYI<PGynhq0ssO40{{a60ssO41ONp90{{X50ssa82LJ*91pos82mk;81pos8000000ssO40ssI2000000RRC2i2(or5C8xGAOHXWP$qc`000F57y<wQ000000RRI4xd8wG5C8xGKmY&$6lrM<000I6AOZjY5C8xGl#!MO000C4Dgpoi5C8xGbsA|200093H39$t000000RRI40RR915C8xG00000)30j<000O8K>`2(5C8xGiGL{q000L7OacG^5C8xGbSaVu00062S^@w7000007%d<G000002mk;800000AQAuo00000AT1yO000002mk;800000@DKn100000C@mlW000002mk;800000;1K`-000002rwW3000002mk;8000002rwW300000&@UhW000001^@s60{{R30000000000*e@Ue000001^@s65&!@I0000000000;4dHm000001^@s66aWAK0000000000=r14u000001^@s66#xJL0000000000@Gl?$000001^@s6761SM0000000000_%9#;000001^@s67XSbN00000000005HKJB000000RR915dZ)H0000000000KrkQx000001poj57ytkO0000000000U@;&7000001poj582|tP0000000000ST7&|000002LJ#70RR910000000000U@ss5000002LJ#70ssI20000000000XfGfD000002LJ#71ONa40000000000a4#SL000002LJ#71poj50000000000crPFT000002LJ#71^@s60000000000fG;2b000002LJ#72LJ#70000000000h%X=j000002LJ#72mk;80000000000kS`zr000002LJ#72><{90000000000m@gmz000002LJ#73IG5A0000000000pf4Z*000002LJ#73jhEB0000000000s4pM@000002LJ#73;+NC0000000000urDA0000002LJ#74FCWD0000000000xGx|8000002LJ#74gdfE0000000000z%L*G000002LJ#75C8xG0000000000$S)uO000002LJ#76951J0000000000NQ3MMNQ(u{Bp?7tg}`(I|IkQ-#0bLx0000000000|1}aMAOQa*6eJ)34<A4P|0NP6AOL6p0002#;Q#;s|0N0}AOL6q0002#(EtDc|0Mz>AOL6r0002#!2kdM|0Vh(AOL6s0002#u>b%6|0VJxAOL6t0002#p#T5>|0U`pAOL6u0002#kpKVx|0UuhAOL6v0002#fdBvh|0UWZAOL6w0002#aR2}R|0U8RAOL6x0002#VE_OB|0T*JAOL6y0002#Q2+n`|0TjBAOL6z0002#K>z>$|0TL3AOL6!0002#F#rGm|0S{`AOL6#0002#ApigW|0Sv;AOL6$0002#5dZ)G|0SX$AOL6%0002#0RR90|0S9uAOL2N0000000000L03UmG5<kTK~z;!NQ3NnWJrqyB`5#@07!{MBxo_f=<ELf|45B=Buq$+J?|tS07%CL%q1WI00000=>Puz|43t8Buq$!+Yf}+0{{R>xc~qE|NsC0KS(*l4~PB(002mhES&%V002md@8}-?|Nlsd!bpikBrq|+4<A4P#{_}^0000;gTMhuIm31ENQ-<VFh~LYNICsTiEJbgbR<ZPEq5d!07!}Z4<A4PNQvG^iSOuz{{R0-gTn+!Ib0+Vb?U#=rab`Y!2bXLNQp!wAV`ZuBp^tQkkqC<01qF400000#{d8T002mXzywG+!gcXTi$o+aNQ-<V5J)-r4}=&2002mdL?k#!i9{p_NR31!P)LbHBq(N(NQ*=y2uO>3Bq)n8=)VX607#2`Bv43;L?l>9Dfmdi_yUE%L5ao>j-vtq05Qo$G2}%t|1r{L4<Cd800000NMpi@)l7{nhfIm+>kwv;NQ1xxi!ebsbpUk=iQSD|0YN$5f9fgKgT(<%IpGh41OWg5L5oEINrS`)L5XZ6{6UFCB=|u&-ig|Ovq**ibOq?i{r~?>Is9}(Nn-~{i*zI)NR14Jivfke508!k002piR|xAJ4<Cd800000NMiy>gTe?%jSPm10foR1k81${0E55*OgZ9-0d?U`h5t;6|8xcDbp8MTNP|Qq2n0xrL?j4EIYcB74~72z|NlshJv$8m0O+y@002mhH7^YS07#8J#33L6NQuJeZ2kZLNR2(UAs_(g;QaspNQ-<VAm}Fj|NlsXd?YXcbP7m|d?YaF6#f7IF~CTRd?aXONHaVoC;$Ke4~63a002mX#CTg>L0myyL0&;$!w(;T00000Oo`x3Dfmc<!bpikBp67+`U6OX(hr240000;jRX=%Il@SZ1SAiJ@Bjb+NXG;u`2YX^NQ*oq=)3&?|455eBp5-9O#ny%!c95+i3*8o1P_Gy0000<jaLXsDbz{9>;p=T4CM#_002cX<PRSJON$gIN{JL8NrS`)Njc1Q?@0l~NrS`)O@;q-5=@EzNQp!w80b#?|NlsfL?jqUiwq=4i+m(dNr}fu0m128{{R0EA4C8ENXG;u2mk;8>2Lr4{|_GkOo{*K82tbLOp8P$5KN0qBsej^Nn<fcWBBOd1poj^gTVw%Il*=8gXjTtaY&6l@e2R|=tl+s07#8B<qH4+NR2&NARqupiNfds{Qv*ykpBPwNWcI8|NsC0{~t&>_z#Eu{{R0mz(|8UBmfVD0ssI1NWtO+NQo3A>FfUg{|_I400000Nr}YiEdT%iNQM6og%1Az|LG3?|NlshJ#Y&E0O-~Q002mhHDn6_07#8J=pP^eNQuJeko*7t=^y_8|G(6xJpkxo`~Uw)$3!GB00000NQp!wAV|kVBoF`q008NV{Qv(*iNi>Xd?YaFDEt5aNQvL*fcyXd=$rcg|L8XR|Nlsd!$^yKBp~Ps`~Uw)gM1_~0Cmsn*G+~0NQuLA2uz9p=<oXf|455`Bv43&|8&ym;QIgn>&p)xKmcYg4<Cd800000NR2&$As_%qgX{?C0Q>*{NQ*u39v}cnjTQPHAOJ{>HDn<m07!$x2<ejg|Nmx?G3`l-(OyW2;z)z!@K97tjRjf?002mh4dV#_07#8J{QCd@{}q-VAOQ3aA4C8ENR2(g9v}c!NR0)#9v}cnIrvD4<#ZWHiv?;PAOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2&#9v}cnjWv26AOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(tA9v}cng}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fIX2QAOHY$FGzzu-yI+T098nd<#Y^4i#-Y+AOPqs`v3pvNdN!;#sz60AOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8EL03qPNB==qK~+IiG09a^^GFZ8$cfHKiNi^W{78fBSV+_RO^N47i9{qYNWu6&iA*F+NQp!wC`gSBa0vhajYj`SiCiQ&NWuF*zXAXN07!{UBp6A-|365HTqHn=L?lQLA4C8ENMpxHnMwEjNQKf!iPsN=qyYc`OpA0RKuC$!Op9zJI7q?%KTL_@Oo{pE*!chdNr}NsiSS8@&`b&F4}^9B002yhJS0fRL?jRa0000@iRUrfO^M8qLH5M~bUjFmOe7FYi9{qINe{2wNQur!iO5Kc3?xYpukcCt<VXSDNCDPJiN{Qd`sjN2|Nl&jL?j?ci9{q2NQu);53j^biQq_!3?xbS<V_E(^#MuI{!5KC07!|)NCDPNiTdb8`2YV&iNs8a@JWf#ObO_9he(S|BoIxB{7j2HBuI(KNQ3YJND0^vgv$T`07#2eBq&IWL?kdsG1^Em$ViFTND0Regs%Vq0E2uaOaTv$k^lezNDr^sNQuZu_u)*5`ACg48%T-ANCDPNiQ?$h_y7M$i%cXiNQu@+i&P{iNQuWtiO5JX@<=iGND0DpXH1E7BnUCvOo=QcNr}!#iSp|?4<A4PNDr^qNQwANiTOy4G!jVn=STt8NQuWxiQ?#i_y7M$i*zI?Oo{PGiN{DW!ALRIND0n#8-v3EIb0-2b;3x4#8@%FTU|k1L0v&!L0`j=NP|Qq7z9X-9iImP07#2OBp66J!*mIYIO!_>|Nmx?NQ1;!xB&nF09#!_TtQtyUO`{OW{_qs4<Cd800000L03UmNr}!uRY6oqiPcq8Oo_rwiOEQV>?ll$1SCv}Oe6^C==T5rNr}fyiSSGb=nsUc0000<iPXCR0000;$3!F;000004<Cd800000LH5M~bTvqeY$O;=iRMU&*hmkr^GJ(KBnV0O=SdH*??{QqNCECh0oF*16eQ@4_W%D#iNi>VR3sQp53lD;iTFs1Oe6?N_vcLytn~p&(f&(~G$crg$4CLzNQ)FC=v(&x|4E6*Oo{MGiPTI9=yi=qi&P{SNQ1;ENQu~6T|rzyT|r(!U&Ce(A4C8Ey8!?I07%C~Bp3hy008ULNQ3_YeiA_T#{qN<>7V@n{|_I400000NQ3_Z50t>eNQwGL!TLW)iO@(f_(&<xNQL%z6G(;sbQVa3_H`Na!w(;T00000NcY}Ih5vO3NQv;n4<A4PNQuWW$w&$J^GFZ8$n!`Ky#Gkk_zxcdG0F2t54_Gu)BZ>~#(fD$iNZ*U@JNZ)NGZm3<B9o5)8NBqE)O4s0000001qDk={xoR|7I=^AA|q^0001xL03UmK~+IiRZ~cV>}X_2iyS2=0000;iCiRDG24Uw0Z55_Bp8WwBoq&h$N~TWOk-pu6ikWWr~!3!L4*7P4~6Oi002mfTqGF31ONa4NXG*J0000;$3qAJ0000;$3qYR0002!H1+@gi*zIuNR3bgNQnbTiBk|riBkxPFi4ABBv@ofGaMx-0000;i$o+C4}}*5002mX#AsVxL0myyL0&;$!w(;T00000Oo`{{Nc;c)gur!*O^N40y#W9K07WtONx}a=4<A4P#{?t-0002H0ssI24<A4PNMplHiTOzP=u83VOcC-(iN{EZ)=Y`w=yUY{|43szBuI%wBnXMaOo{nOiTFtO??{QqNQu=<iQ-HF?@ST(NQv&~Nc8{zNQu!%53k5b_uxnY$w-OENQu=<iQ-5B%}fFBOo{nS5%oxk?&u!$|Nl&jL?j4IiROs}Bta>_Nn`lv2>$>7gZKeRiNOzqZ2$lNNrS}!NrTn^IYcBB4~|Oz|Nlsd1SE?@Bos)Ed?Y}b_xXv&=wtr>|454rBuI^XBp`{-=u`gx|455`Bq&IWY$Qlbi)<tyOp9bBKuC*RBp67E_(+NFOeyG0DdtGQ_yS15{sKtH0{{R307wDwNXJ7600000NXJ7E000004}^IF002n3|NsC0|Ns9#NIB3ChtUE607#7-g#Z8m07!}7=!5hB|450!NQ*=y7)*<7Bp^tQG#N;XY$Qlbi)17~NQ-<VC`gG2NQrO|NQua14<Cd800000#{d8T002mXzywG+#&z*Xi$o+CNjdCHiQ`C#a0pC^?sPazIq!8G>oH~zA4C8ENQ1)!i4jPH!30P--E<sCIrnrIixZ0mIl_G8i2+E1#so-%!30P--F4(iiT+6`_DDJRbz(?4-E<O2iRwy?JTXX#-bg9h=o9n*|4oJMbPY_2@94Jj|Nl&jWF$aMh2#%}nf?F&Oo`{{pz{C!>5TpV{|_GkNXG{N0000;$43YN0000;$43wV0002#ZT<iM4<A4PNQuu(iSp>Z^8f!xIo(K!!F7=9pbsAai*zIuNR50XK+*o_!2JLJzXSjP0O(fo|Nl&jbR<Yfi(Di?Nr}bB00IC208EWw1W1cSBp6JI^++k*NXGyG0000;$3O@G0000;!TkbA$3PGO0000;gT(<4gzEqR07$t1|NsC0|NlQoImHi$0|5X4NR1q=00000NQvL*?D7BqNQuEni$o+COpA0RNJxzo8Ayv<BtS@s2uO)g5HY|HA4C8E#{_`@0000;gTMhuImLDGNQ*=y7)d$aOo{GDiBJf28|y6(A4C8Ei8)Av!vsi!!30b>^K=<WIrMZCi#v-3ImdkDi2+E1#sur)4<A4POo`=4DfLM?^mGnLiO)!h>gXcz|Nlsd!Av>xbP`O7@<@$5DM*RlNGaOri1GjbOo{L4F!BHYNQ-<VKuCrE4~2dH|NrR@{Qv(k$uain<Ng2tG08E~>0|%@|4fPRNQuMf0P+9-NQ-<VKuCrEbOq?~@c;iviQni+@&EtmWbpt0NQuMi-{|`A|NrasNQuKpi$o+CNQ*c~h5vQZ>(xk$d?X-9iNi>R|8%+NwDAA`>$2!A@c;j2E)O4s0000001qDkL03UmNr~4%RY6otjV0z0AOKZJjV<mGAOKTAiTz25_Dm_|NQ3MMNWuLB=)dp(|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3aA9e3cWHBFAY*TEa%pX40CQz@cWHBFAY*TEa%pX40B&z|AY*TEa%pX4000000000000000000000ssI2MF9W+pCkYP5^ewh*Wd;K7(JB${*eJ|0UHB5Z~y=R4FCWDH1GfayZ`_IH1Plb<NyEwMDYLrSONe5^z{G#tO5W4B=!IQi~s-tH1_}h`~Uy|l=%PubO8VWg!%vfzySaNr1}5<)BykhB>MmVU;zLCH2VMl2m$~AB>(^a!~y^Sl>h(#3<CfF6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|Sko5omD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|SaPI&A0096101gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)Nbmpu2mk;80000000000U;qFBTmS$7F!lfcR0041074EBj{-&x7>)x%4j_#LLJla51w#%nh6X_nID-dK4v+x@@c{}BI71FFK@KQF4j@7f7(xyZLJkN*3uF#BMh-AR4k$tnAVLlpLJkl@4hR4M5C8xGzyJUMy!ikB1poj500000NB{r;)Bpeg82A7G@Bjb+074EBj{-st7>)x)4j_#LLJla51w;-oh6X_nID-dD4qyVZ3Jy3#4lqFuC_)Y(LJk;04iG{P2uBM55C8xGAOQdXy!ZeAAOHXW000005C8xGGywnr$oK#Ma{vGU000008~^|S000000eVnOQUC#X5C@wX5+DE@8w>{skO2SyOaK4?Bme*aB>4aT;{*Tz1PcKG074EBj{-st7>)x%4j_#LLJla51wjrlh6X_nID-d74xj-7kO~esK@KoM4k$tnAVLlpLJkl@4hTpKPyhe`bN~PV<n90eq67c{1or>{074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-d74zK|Ob^;0xI6)3DK@KQF4j@7f7(xyZLJkN>3jhEB6aWAK3<3ZEK=S|pE&u=k080)KUJeKVL;wH)Bmw{cSp5J0WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGYytoPfc*de0ssI20000000000|Nj9vX9c(k0GI;>005{11-1zQm;?pN2>`nW1polW1_i7M0IvrHg$V$n2?YQErwIjx2>{*+1<DBk|Nj9ZAW{GTwgDQ;2mq`Cqyp*)0MG>mfe8Sr2X^WR0ICQ(000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000AQAuo00000@DKn100000;1K`-000000RR91000000RR91000000RR9100000i2(or000000RR9100000xd8wG000003;+NC000005DNeR000004FCWD00000lp6p50000082|tP000007%d<G000008vp<R000005C8xG000008UO$Q00000C@mlW000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000Fa-br000001^@s600000zybgO000003IG5A00000W&!{J000003jhEB000007ytkO000006#xJL0000000000000000{{R300000KrbKw000000ssI200000XaN8K000006aWAK000002LJ#7000007XSbN00000s0jc7000002LJ#700000a0mbZ000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000&<6kj00000|NsAQ000000{{R300000@c;jB00000mInX;00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000FfAYe0000000000000000000000000MhgG{00000Rto?C00000W(xoS00000b_)Oi00000h6?}y00000mJ0v?00000rV9W700000whI6N00000#tQ%d00000)(Zdt00000<_iD-00000_6q<2000001`GfI0000077PFY00000CJX=o0000000000000000000000000000000000000000000000000000000000000000000000000002rwW3000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9Fa-br000000000000000000000{{mAmInX;000000000000000000000{{pB&<6kj000000000000000000000{{sCa0mbZ000000000000000000000{{vDs0jc7000000000000000000000{{yE5DNeR000000000000000000000{{#FFbe<x000000000000000000000{{&GFbn_y000000000000000000000{{*HKnwr?000000000000000000000{{;Ilp6p5000000000000000000000{{>Jpc?=H000000000000000000000{{^K{2KrO000000000000000000000{{{La2x;t000000000000000000000{{~MARhn#000000000000000000000{|2N7%d<G000000000000000000000{|5OC@mlW000000000000000000000{|8PFfAYe000000000000000000000{|BQKrbKw000000000000000000000{|ER05Bi`000000000000000000000{|HSKrkQx000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000002><{90ssyGFcJU&00000R0041000009RL6T0RRvH;2Qt{000008~^|S00000A^-pY0ssyG@DKn100000E&u=k00000Jpcdz0RR~Qc`_gX000000RR9100000OaK4?1OV~>00000000000000000000R{#J20ssyGP!RwC000000000000000SpWb40ssyGkP!d?000000000000000YybcN0ssyG;1K`-000000000000000f&c&j0RR~QcrqXW000000RR9100000kpKVy0RR;MC@mlW000000000000000xBvhE0ssyGAQAuo000000000000000!~g&Q0RR*L7%d<G000000000000000OaK4?1OV~>00000000000000000000;{X5v0RR#J93KDx000000000000000000001OV~>00000000000000000000@c;k-000pH{2KrO0000000000000001OWg50RR>NFfAYe0000000000000004FLcE000yKC@mlW0000000000000009svLV000yK7%d<G000000000000000F#!Mo0RR^OKrbKw000000000000000M*#o;5C9ke7%(6J000000000000000P5}S_A^;8mFcts+00000;{*Tz00000r2_x}AOIKu05Bi`000000000000000asdDU5daVXpc?=H000001ONa400000fdK#j5&!@I00000000000000000000rvU%}5&!@I00000000000000000000)&T$jA^-pY00000000000000000000@&Nz<5&!@I000000000000000000001_A&85&#YWKnwr?00000q67c{000003jzQD5&!@I00000000000000000000Qvv`05ds(h2rwW3000000000000000U;+RD5&!@I00000000000000000000cme<bAp#fx5HKJB000002mk;800000i39)u5&#bXlp6p5000000000000000lmY+%5&!@I00000000000000000000rvd-~5&!@I00000000000000000000xdH$H5&!@I00000000000000000000(*ghh5&!@I00000000000000000000sRIB25&#YWAQ1on00000D*ylh00000=K=r#5&!@I00000000000000000000`T_s|5&#YWfE54$00000AOHXW000002Lk{A5&!@I00000000000000000000>jMA)5&#PT5DNeR000000000000000BLe^c5ds(h7%(6J000000000000000F9QGo5&!@I00000000000000000000i~|4w5dawgKrkQx000005CH%H00000qXPf{5C9ke05Bi`000000000000000836zQ5C9nffHEKe000000000000000umb=95C9nf7%(6J000000000000000yaNCL5&!@I00000000000000000000;R65w5&#YWAR7Px00000WdHyG00000@dE$=5&!@I000000000000000000001Oxy85&#YWpcMcB00000a{vGU000006$AhP5&!@I00000000000000000000Dg*!k5&!@I00000000000000000000F#rGn5&#YWkQ4v_00000@Bjb+00000O9TJ_AOHXW00000000000000000000X9NHM5&!@I00000000000000000000e*^#k5&#YWkQ)F1000000ssI200000j|2b!5dawgU@;&7000007y$qP00000r33%~5&!@I00000000000000000000!~_5UA^;8mAQk`s000001poj500000<pcl#AOHXW00000000000000000000^aKC^AOHXW000000000000000000004g~-J5&!@I000000000000000000000BvDuZZ2bE0AE@-X>(t2a%pX4crI{Za&#^@04`rSHUM8oOiw~VOkZDfbz)yhUtd}^aBp{Ia&B&J0AE^DbWAv3Uukb?ZfSG?V{&wJbaiHCE@J>>WpZU_X>)XCa$j_9Ut?@<Ze?=-UteTzUuSG@Vqt7wWOQ$Gb6;U~cmQK>ZE$R5bY)~NH#Rvq0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$DN9X>Ms>VRCX|d0%C2baHtBW^!R|WnW}<ZEbk~UteZ&VQpn!WOZ$Ad0%O6X>?y<a&lpLUuAA|a(Mt>Uq(_vO+{ZtPDEc{0AF86PE}t;NMA-$K}|(pNJLTqUqo3>K}|_R0AF8eZfSI1VRCX|d0%C2WB^}ZX>MtBUtw}`VR>J3bYXII0AEK;PeMUVUr$CxQ$<u?R6#;aMPC44Wn^J=VE|uRHfCXCbZ>G=X+=|XHg;uWbZ>G=R9{nJNmDUjMMYCFUjSc8PhWF%WNB_+b#rB80AE^DbTKzyUvy}4Z+Bl}VPs!nY;131c0fQ!Oi4mRSXf^(E;ImNT251RIB9QlUt(c%Wid5#d2VB0cWHEJUvqS1X>UbhKtM-KNkT(dSYI<PGyq>;V|Za-W@&C=Y-xIBKtM-KNkT(kGA=SMH2`yTa%^R8KtM-KNkT(kGA=SMH2`g4X>I^tT2pj1Wo~3_Nn=xVF)?FkVRBz|a$#w7b4g=GMN(6AF*9Oeb7^B=Z*z2VWnpbeR9{puUqw?kUqC=dOi4mRSXf^(E;ImNUu1J{Uua=&WNc*sUs_I6X>xN#QfWXyM@&gVLs(c}GcGg$L{~0yWo9m4UuSrDUvOn|b8l{8Y-x0PUv@A6ZDnm^aCtyLM@&gVLtip3F*E>QUu|z>bZIj{Ku1GEUo$Q+0AF8Ycwt{*bY*yHbU;8yOi4mRUotK-E;RsOT4Zccc0fQ!Oi4mRSXf^(E;ImNT5fl3KtM-KNkT(dSYI<PGyq>(IB9cVaB^vFWq1HzUvqR}V{2byXlq|)VQFkYKu1hTLPK9NE;ImNUsO#)UqwztUta)UT2pi}HeX+Fb98cLVQpV&ZgXXFbV*}VbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeXOnQ!`&|KtM-KNkT(dSYI<PG%h&+Us_XiG-GddbU;8yOi4mRSXf^(E;ImNUu0o)VPA7}VRCc;UteN#b6<0GVRCc;Us_I6bU0~mb6;X%b7eG1ZfSHwF-3MjKu1hTLPJ<sUo$Q=0AF8hX<}nvV{>(1X>MtB0AF8qZEs|BX){1TM?*tjGcGUyUs^FRVrgz+a(Q28V`O-E0BvP$ZEtpEKtM-KNkT(kGA=SMH2_~<XLxvDaAk6HZ*F01X>@sCb}&FdLs(crLP=jSE;9gMNmNZ=WMy(?XK8bEWpY$aLu_wuWmI8eY-IpnRc?1_Ze(9lWpj0HWk5hjLqlIPE-(OJUu<b&V_#!)bzf#_ZfO8tT2pj0V`*+cKu1hTLPJ<sUo$Q=0AF8hX<}nvb97;HbYE>@X>LG3M@&gVLtip3GA=a$Us_I6bTKhwXkl_+baG*7baP2#MK)|@ZfA68MNms)0AF8cZEtR0b97;HbYEWpUrAI=Uvgz<X>)XCa#T%2Y;SI5RAFLlWdL7VPE&L^X>W61VqtS-G)Zo0bVM;lc0fQ!Oi4mRSXf^(E;IlDE^~QpbYWruE^~BpbYWruE^}yebaHfIVgN2_ZggdGZ~!iDZ**lYK|)C_bYW)zE^cphWiDrKbuMCcX>4RIX=DH{XKr;aXkl|`04`*CZgY8U04`*CZgX^U04`^4buM;ga&u{KZU8Q4ZgnnpWpZ<AZ*E_504{Q6Y+){Bd2RqMa%F5`E^usg04`~6X><TCaBOrgXK!=>E_7vhbO0`9X>Mr%E^=>VVRT^tE@fz6W^!R|WnXAyasV!6XkTV>VQpmqE@xw7UuAe>WpH#~bYWs_WdJT|ZfSI1VRCX|c>peEX>Ms>VRCX|c>peCd2V5CX=4B`WMOn+04`#4a{w-5Z*6U5Zgc<u00000000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO00000Z~_1T000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000Fa-br00000Fa-br00000W&!{J0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000mInX;00000mInX;00000Gynhq000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000&<6kj00000&<6kj00000pa1{>000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000a0mbZ00000a0mbZ00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000s0jc700000s0jc700000XaN8K000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s6000005DNeR000005DNeR000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000Fbe<x00000Fbe<x00000009610000000000000005C8xG000005C8xG00000lmGw#0RR911^@s600000Fbn_y00000Fbn_y000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000Knwr?00000Knwr?00000QV#$C0000000000000005C8xG000000000000000qW}N^0RR911^@s600000lp6p500000lp6p5000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000pc?=H00000pc?=H00000TmS$70000000000000005C8xG000000000000000u>b%70RR910ssI200000{2KrO00000{2KrO00000bN~PV0000000000000001ONa4000000000000000zW@LL0RR910ssI200000a2x;t00000a2x;t00000umS)80000000000000002mk;8000000000000000$p8QV0RR910ssI200000ARhn#00000ARhn#00000VgLXD0000000000000000RR91000000000000000+W-In4gdfE0{{R3000007%d<G000007%cz*000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000C@mlW00000C@la0000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000FfAYe00000Ff9N8000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000KrbKw00000Kra9Q00000zyJUM0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000005Bi`0000005AXm000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000KrkQx000007%%_;00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007%%_;00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NH72Z00000xCj6M000008~^|SFaQ7m2mk;8000007ytkO000002><{90{{R3000000000000000000000672v00000GX($u0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000Gd=(S000005CH%H0000000000000000RR91000000000000000"

exe_bin = base64.b85decode(exe_bin)

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
from math import gcd


class Eratosthenes(): # エラトステネスの篩
    def __init__(self, N): # 素数リスト生成 O(n*log(log n))
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N**0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i * 2, N + 1, i):
                self.fact[j] = i
        self.prime_list = [i for i, pi in enumerate(self.fact[2:], 2) if pi == i]


    def factor(self, NUM):  # 高速素因数分解 O(log num)
        PRIME = set()
        while NUM > 1:
            PRIME.add(self.fact[NUM])
            NUM //= self.fact[NUM]
        return PRIME


n = int(input())
a = list(map(int, input().split()))

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 # 0をpairwise coprime

for a in A:
    memo[a] += 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        flag = 1
        break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

Submission status: Accepted

Solution code:
from math import gcd


class Eratosthenes(): # エラトステネスの篩
    def __init__(self, N): # 素数リスト生成 O(n*log(log n))
        self.fact = [i for i in range(N + 1)]
        for i in range(2, int(N**0.5) + 1):
            if self.fact[i] < i:
                continue
            for j in range(i * 2, N + 1, i):
                self.fact[j] = i
        self.prime_list = [i for i, pi in enumerate(self.fact[2:], 2) if pi == i]


    def factor(self, NUM):  # 高速素因数分解 O(log num)
        PRIME = set()
        for p in self.prime_list:
            if p * p > NUM:
                break
            while NUM % p == 0:
                NUM //= p
                PRIME.add(p)
        if NUM > 1:
            PRIME.add(NUM)
        return PRIME


n = int(input())
a = list(map(int, input().split()))

ans = 0
for ai in a:
    ans = gcd(ans, ai)
if ans != 1:
    print('not coprime')
    exit()

era = Eratosthenes(max(a))
num = set()
for ai in a:
    prime = era.factor(ai)
    if len(prime & num) > 0:
        print('setwise coprime')
        break
    num |= prime
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

upper = 10**6
N = int(input())
A = list(map(int, input().split()))
num = defaultdict(int)

g = 0
for a in A:
    g = gcd(g, a)
    num[a] += 1

isStopped = False
for i in range(2, upper+1):
    x = 0
    for j in range(i, upper+1, i):
        x += num[j]
    if x >= 2:
        isStopped = True
        break

if not isStopped:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")

Submission status: Accepted

Solution code:
# E - Coprime

import math
from functools import reduce

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    sqrtn = math.sqrt(n)
    d = 2
    while d <= sqrtn:
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

count = [0] * (10 ** 6 + 1)
for x in a:
    for f in factors(x):
        count[f] += 1
        if count[f] > 1:
            print("setwise coprime")
            exit()
print("pairwise coprime")