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:
import base64
import subprocess


exe_bin = "e??420s#R400000000000{}h%0RR91pb!8600000KmY&$000007%u<-0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000)ffN(00000)ffN(00000001BW000000RR911^@s6ARPbz00000ARQn800000ARQn800000_yPa`00000cm@Cf00000001BW000000ssI21^@s6I2`~000000I2|AW00000I2|AW000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4^c4UA00000^c4UA00000^c4UA00000YybcN00000YybcN000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4ARPbz00000ARQn800000ARQn800000-~s>u00000-~s>u000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$vf@fT5NQ(ARnr7ALYvfZ_eG2U0{{R3761SM0RR911^@s6000mIApjHr761SM000007ytkOa+U`IC2b5t6_^Y|000000000000000000000000000000yZ`_I5&!@I00000000000000000000<^TWy5&!@I00000000000000000000<^cczA^-pY00000000000000000000%K-oY5&!@I00000000000000000000U;qFB5&!@I00000000000000000000RR9105&!@I00000000000000000000-vIys5&!@I00000000000000000000(g6Sf5&!@I00000000000000000000-v9sr5&!@I00000000000000000000YXJZN5&!@I00000000000000000000x&Z(H5&!@I000000000000000000009RUCU5&!@I00000000000000000000aRC4T5&!@I00000000000000000000^#K3?5&!@I000000000000000000002mt^95&!@I000000000000000000009{>OVAOHXW00000000000000000000p#cB@5&!@I00000000000000000000{Q&>~5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000qyPW_5&!@I00000000000000000000n*aa+5dawgU?Cs?000007y$qP00000)c^nh5dawgfFd9O000005CH%H00000i2(or5dawgKp-Fh000005CH%H000000BmVub97{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^DbTngSa&iD)T4Zccb^u>mPE&L^X>W61VqtS-F*S2}Zew3}X>@2`b97{BZ$)ANUtec<cwca3a&vEPVQgu1d0%!g0AE^DbTKwxUvG1Ca%Ev{UukZ0WpZ>$V^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kP)k!YUu*zhT5fl30AE^8Q*=0KZ*yN_VRL0PNp5L$Lor2m0AE^DbTngcb#wr1X<}z%V_$PFb8jv&0AE#ZcWG{9Us7drb!}w;Y-wU+E^}`#HUM8=b97;2YhPn%YhPwzX>0&<baHHEZUA3jV|Za-VRU79X><T>Wo=_{c>rHuV|Za-W@&C=Y-xIB0BvP$ZEtpE0AF8hX<}nvb97;HbYE>@X>I^VLqlIPE-(N`Oi4mRUotK<07pzoLPK9NE-^F!M@&gVLtip3GA=a$Ls(crLP=jSE;9f}Oi4mRSXf^(E;KGV07pzoLPJ<sUo$Q=000000ssO40{{a60ssO41ONj70ssO41po#B0ssR52LJ#72mk{B000000ssO40ssO40RRC2lK}t#5C8xGAOHXWP$qc`000O84*~!H000000RRI4umJ!75C8xGKmY&$6lrM<000F57XknP5C8xGl#!MO000C4Ap!sZ5C8xGbsA|200093ECK)k000000RRI40RR915C8xG00000)30j<000L7I066w5C8xGiGL{q000I6LjnK*5C8xGbSaVu00062Q33z}00000ARQn8000002mk;800000pb-E700000C><aG000002mk;800000a1a0h00000FdZNO000002mk;800000U=aWS000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60{{R30000000000*dHJO000001^@s65C8xG0000000000;2$6W000001^@s65&!@I0000000000=pP^e000001^@s66951J0000000000@E;%m000001^@s66aWAK0000000000_#Yqu000001^@s66#xJL00000000005Fj7`000000RR914*&oF0000000000Kp-Fh000001poj57ytkO0000000000U?Cs?000001poj5761SM0000000000fFd9O000001poj57XSbN0000000000U>_g=000002LJ#70RR910000000000XdfT|000002LJ#70ssI20000000000a33H5000002LJ#71ONa40000000000cpo4D000002LJ#71poj50000000000fFB?L000002LJ#71^@s60000000000h#w#T000002LJ#72LJ#70000000000kRKob000002LJ#72mk;80000000000m>(bj000002LJ#72><{90000000000pdTOr000002LJ#73IG5A0000000000s2?Bz000002LJ#73jhEB0000000000upb}*000002LJ#73;+NC0000000000xE~+@000002LJ#74FCWD0000000000z#kw0000002LJ#74gdfE0000000000$R8j8000002LJ#75dZ)H0000000000NQ3MMNQ(vS6d(Xdg}`(I|IkQ-#0bLx0000000000|1~-kAOQa*JQN@R4<A4P|0OyUAOL6p0002#;Q#;s|0OaMAOL6q0002#(EtDc|0OCEAOL6r0002#!2kdM|0N<6AOL6s0002#u>b%6|0Nm}AOL6t0002#p#T5>|0NO>AOL6u0002#kpKVx|0N0(AOL6v0002#fdBvh|0MzxAOL6w0002#aR2}R|0VhpAOL6x0002#VE_OB|0VJhAOL6y0002#Q2+n`|0U`ZAOL6z0002#K>z>$|0UuRAOL6!0002#F#rGm|0UWJAOL6#0002#ApigW|0U8BAOL6$0002#5dZ)G|0T*3AOL2N0000000000L03UmG5<kTK~z;!NP+BV5_$k+NQ(p|C;$KeNQs0bSQ2^wF~I2c{{R0-jdUbTNR2%i6(9ge#|8EkAOHXW008I-|Ns9;V_YOmNQK)EgpvaQ07$t1|NsC0|NlQoIl~W!=mP)%NR2F=00000NQv+082|tONQuHoi9{qYF~DXIA4C8E#{_}^0000;gTMhuIm31ENQ-<VFh~LYNICsTiEJbobR<ZPEuR!107!}Z4<A4PNQvG^iSOu*{{R0-gTn+!Ib0+db?U#=rab`Yxc>kDNQp!wC`gM$Bq&IYkkqC<01qF400000#{d8T002mXzywG+&~@=hjeI0f=%)q%07#2OBrr&ed?Xl1IrtBR-T(jqNQp!wI7o>^BoJmU4<Cd800000NQ*=y5Q`Xt`vDJxqyPW_G08<S_C+!O4<Cd800000NMplAG31MEgivM=A4C8EiP%Ad!~vQ2{YYcbJ8YCtNQu*Q>r6TEL5al=gzo?V06~c^MTuqvNrT1+L4*APb-qnG{&YY|V+Tl!bR;N9jSPm10foR1kAndK07;Ek2<sXTA4C8ENMiy>gTe?%jSPm10foR1k7EG<0E55*NjcVu0d?U`h5vL2Oo{*Koc;g*NP|Qq5ClkzL?jSMIYcBF4}~`W|NlshJ+lV@0O)E2002mhHKzvv07#8J91<V^NQuJel>PtzNR2%W5+DHR82$hMNQ-<VDCkc8|NlsXd?YXcbP7m|d?YaFJpKRwF~CTRyd+o>dH`fdGdv|I0000Fh2#MM07!wvXcBq=TU|k1L0v&!L0`j=Oo{MJDfmc<!bpikBp^t^`U6OX(hr1{0000;jRX=%Il@SZL?j3ghUWkP07%C~BnbHb|Nlsfd?X0y;QaspNQ+b?AV>kiO*#IFDnyB51P_Gq0000<jaLXsDb_L4Nx|*|PK`A62mk;84<A4PNs9~@NQn#(NQ1%%NjcVa?@0m1NrT1+O@;q-5=@EzNQp!wAn11d|NlsfL?j?ci%cX4Nr}fu0m12Q{{R1wNXJAZ2nYZG0O@%D|Nmx?Oo{*KNc{i*Op8P$7)*;yBsej^Nn<fcWBBNy0ssI>gTVw%Il*=8gXjTtV@QoXaRvYY=m!G;07#8BWd;BMNR2(Y5Fh|ZiNfeH{Qv*ynEwC&NWcI8|NsC0{~t&>_z#B$|Ns9nz(|99BnSWxgbV-w|46~&1W1WgBnavA{{R0EA4C8ENr}ekH2?qqNR2)I1pol(qyhi{NR2h}1poj@jXhQnAOJ{-!syQX|NrSV{{R2K)TTWE=%4%l|47F~BrpH~002mdL?kFk$3!F;00000>CpWD|4oJeNQuLA2uz9p=wti;|455`Bq-=v`~Uw)gM1_~0CWmSi+m(7=tuki|4517=%4%l|L9u#|Nlsd!|T#WiNovP=)3y=|Bz-b4<Cd800000NR2%j6CeOcgX{?CQ2YP?NQ*sj4<G<YjTL$iAOJ{>HT)7F07!$x2<hVb|Nmx?G3`l-(OyW2;z)z!@K97tjRpDy002mh4TA&#07#8JO#A=;{}mPwAOQ3aA4C8ENR2%~4<G<lNR0(K4<G<YIrvD4<#ZWHiv{WqAOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2%K4<G<YjWzlXAOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(ur4j=$Xg}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fITS^AOHY$FGzzuUk)Gu098nd<#Y^4i#>`CAOPrn`v3pvNdN!;#svWqAOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8ENQ3McNR2(k5Fh}$0RR91NR4zP2gXDs2MT0Jiv%So0000;i9{p_F~I2I`Tze&i$o*{WJogvB`5#@0CfdOgTxra=(qX*{|_I400000NQwGL!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>AU#<|7I=^AA|q^0001xL03UmNs0DBRY6oqiS$)dNQwPOgX|bci%$qhiyugd$Vn;QNGaGz!T175g}@Jlv;Y7ANR2cANyo?h|Ns9;Iq(mLxBvhEOo{(Ui4-L0y!ikBNQ+$nNQ+GfO^M)0ixebDiN#3)$4M#JivmnJ<3ou=H2`!VOo_rsiQY_!??{PEBnV821SIIe`2YV%i%cX4Op630Nr}!+jYI_mO)2I~IpK5>Oo_)#iSkT|=IAQ;|Nlvez)b<hNQK*U2uO+F=r{QP|4fN(08EK>2uz865J-c>7+YOITtQtyUO`{O4<A4Pz5xIL08EWMwEzGB0O?Nu|NmwWA4C8ENVxz1|NsC0|364M#t(-z|Ns9;h4yvTO^NVDG5<v|?deAU|Nmw#4<Cd800000K~z;pjh6%xdH_>MiTg-{>@Z|Viv%So0000;i9{qQF~CTP_zxcd#{d8T002mXzywG+!gcXXjbtPYNR4bH5J<;FBoF`q002nGL?jph0000;$3!F`00000G4{tqBn$!o002R_0ssI24<A4PNn^lBjRb>>5QWkYgr@)i07#2`BoIl7@<fY7Bn(L@`bok10!4+=eo#qcz>615jSPc9I}v|EiO@k0ufRQkgdPBYHAsz51VMx90Zxq+k?S1~A4C8EixELP5q}$r&`5*91VIn4z&(J39sqv|NSH}E%83+%b>2aPzyU#l_<)2S07QvIBn%IZaR2}RNQM7&1?a~1|NlsfL?kF=NHYW_C;$KebzMk<#4uZ3L0rQRA4C8ENIP^SAVi4(bQVO321tX(1W1W=BpB&F|Ns9FA4C8EOo`%1iSOur{r~?+i*zIy=_LRE|455`BoIi6!$^hybOq>P_W%D#iQnkC_W%FrboT%M4<A4PL03UmNr~4%RY6otjU~<pAOKZJjV;y(AOKTAiTz25_Dm_|NQ3MMNWuLB=zsP9|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3aA9e3cWHBFAY*TEa%pX40CQz@cWHBFAY*TEa%pX40B&z|AY*TEa%pX4000000UHB5XaE2J3;+NC9QFVIv;Y7A4EF#3+yDRo9QObJ+yMXpeER?YFaiJotor}|ga7~ly!-$E2mt^94E+E9Bmn>bjQs!q^Z)<=oc#a)H~|0v%>DoWqyYc`O#lD?OacG^y#N3IlmY+%6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|SAo~CRD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|SVD$h0@Bjb+01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)DE0sU2mk;800000000005C8xGTmS$7ko*7t1poj5000007ytkOZ~y=Rtor}|NdN!<07MQTe+mu=K??u?5C8xGi~s-t;QIgna{vGU00000NB{r;pa1{>T>Jn3CIJ8d074EBj{-st7>)x)4j_#LLJla51w;-oh6X_nID-dA4p0KZ3Jy3y4lqFuC_)Y(LJk;04iG{P2t^A38~^|S000000eVnOQUC#X5C@xu2p|9(8w>{skO2SyGynhqBme*aApHOTd;tIe1or>{074EBi~>Op7={B#4j_XBM-ET}3;_xbAVCfoK@Jc?4hTjIPyhe`TmS$7IQ0MjRRjP41kL~e074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-dA4xpvz0|QY43Jy3y4lqFuC_)Y(LJk;04iG{P2to@07ytkOm;nF)MEL*zE&u=k080)KUJeKV00000L;wH)v;hDB`27F>WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xG`~d&}ApQUU0ssI20000000000|Nj9C&H@G90s!&?1pom5{{bQ<QUCzH0UFB)0E7ah0>%gcs|5v(2mty9XvPQt><4K80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000pb-E700000a1a0h00000U=aWS000000RR91000000RR91000000RR9100000lK}t#000000RR9100000umJ!7000003;+NC00000@CpC`000004FCWD00000v=smV0000082|tP00000ARQn8000008vp<R000005C8xG000008UO$Q00000FdZNO000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000AO!#b000001^@s600000$N~TW000003IG5A00000T>=0A000003jhEB000007ytkO000006#xJL0000000000000000{{R300000NFN{o000000ssI200000Pyqk{000006aWAK000002LJ#7000007XSbN00000pa}o~000002LJ#700000PzV43000002mk;800000Pyqk{000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000um=DD00000|NsAQ000000{{R300000@c;jB00000eg^;m00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I2|AW0000000000000000000000000CJO)n00000HVXg%00000MhgG{00000Rto?C00000W(xoS00000b_)Oi00000h6?}y00000mJ0v?00000rV9W700000whI6N00000#tQ%d00000)(Zdt00000<_iD-00000_6q<20000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8$N~TW000000000000000000000{{j9AO!#b000000000000000000000{{mAeg^;m000000000000000000000{{pBum=DD000000000000000000000{{sCPzV43000000000000000000000{{vDpa}o~000000000000000000000{{yE@CpC`000000000000000000000{{#F5DNeR000000000000000000000{{&G01N;C000000000000000000000{{*H5DWkS000000000000000000000{{;Iv=smV000000000000000000000{{>Jz!d-h000000000000000000000{{^K^c4UA000000000000000000000{{{LU={!X000000000000000000000{{~MpcnuE000000000000000000000{|2NARQn8000000000000000000000{|5OFdZNO000000000000000000000{|8PI2|AW000000000000000000000{|BQNFN{o000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000002><{90ssyGa1a0h00000E&u=k00000CIA2c0RR~Qks}}g000000RR9100000H2?qr1OV~>00000000000000000000KmY&$0ssyG&=3Fs000000000000000LI3~&0ssyG5D@?X000000000000000RR9100ssyGU=aWS000000000000000YXATM0RR~QkRu=f000000RR9100000dH?_b0RR;MFdZNO000000000000000p#T5?0ssyGpb-E7000000000000000tpET30RR*LARQn8000000000000000H2?qr1OV~>00000000000000000000%m4rY0RR#JoEQKA000000000000000000001OV~>00000000000000000000+5i9m000pH^c4UA000000000000000?EnA(0RR>NI2|AW000000000000000_5c6?000yKFdZNO0000000000000002LS*8000yKARQn80000000000000008UX+R0RR^ONFN{o000000000000000FaZDn5C9ke7$6`3000000000000000xdQ+IAOIKu03aX$000000000000000Hvs?u5daVXz!d-h000001ONa400000Mgaf-5&!@I00000000000000000000YykiO5&!@I00000000000000000000n*jg-A^-pY00000000000000000000w*deE5&!@I00000000000000000000%K-oY5&#YW5DWkS00000RRjP400000&;bAd5&!@I000000000000000000007y<wQ5ds(h2p}K;000000000000000B?15d5&!@I000000000000000000007ytkO5&#YWun_<N00000NdN!<00000Jpup#Ap#fx5Fj7`000002mk;800000iUa@v5&#bXv=smV000000000000000Spon65&!@I00000000000000000000YytoP5&!@I00000000000000000000h5`TpA^;8mz!Lxf00000d;tIe00000nF0U+A^;8mkP-j@00000CIJ8d00000^a20?5&!@I00000000000000000000y#oLM5&#YWpb!8600000D*ylh000002m=5B5&!@I000000000000000000008v_6U5&!@I00000000000000000000{{sL35&#PT@CpC`000000000000000Hv<3w5ds(h7$6`3000000000000000LjwQ+5&!@I00000000000000000000paTE^5dawgKp-Fh000005CH%H00000w*vqG5C9ke03aX$0000000000000000s#O35C9nfm?Izn000000000000000!~*~T5C9nf7$6`3000000000000000&;tMf5&!@I00000000000000000000^#cF^5&#YWKotN000000WdHyG000001q1*95&#YW01^NI00000a{vGU0000076bqQ5&!@I00000000000000000000D+B-l5&!@I00000000000000000000OauS`AOHXW00000000000000000000XaoQN5&!@I00000000000000000000fCK;l5&#YWuoVCR000000ssI200000kOTk#5dawgU?Cs?000007y$qP00000rUU>05&!@I00000000000000000000#RLEVA^;8mfD!-z000001poj500000<^%u$AOHXW00000000000000000000^#lL_AOHXW000000000000000000004+Q`K5dawgfFd9O000005CH%H00000CItWh5&!@I000000000000000000000BvDuZZ2bE0AEK;PeMUVUte=|VqZyLUs^e2Wny(_UvG7Eb^u>mQ*=x?Utei&X>MtB0Aq4=b98lPW-em@WMy(?XK8bEWpZD1ZC_(-Z*FCC0AF8ZZ(nC@Z(?C=Uu1M|a&uo{b$9?{Z*6dFWprg^E;lwgH~?Q?WN%+*Y;R&=Y+qz_Z*p^AVRd+4W@&C|Utw}`VR>I=Zgg^a0A_MwZDn6%b!}~V0AF8ba$#*{Uu1P{ZFyg5ZfSI1VRCX|d0%C2baHtBUtdO2K}|(pMNULtUjScUM^05=MMz&pQbA2cUr0n!0AEB|PC-pcLjYf2X>MtBUtw}`VR>I=Ze##oUukY>bYEd|a$$L2b97;HbO2vROiw~VOkYn%MpH#pUsORtOhsP+Uu9%rbYTErNl#yMbYy96Uv+b3WB^}UQ*<#mUte@+a&LEEVqs)oVQg$~V|GA5M@&gVLs(c}GcGg$Us_I6bU0~mb6;X%b7e6#b9ruKUw3JAXkT-5WNB|jVn9GgOi4mRSXf^(E;ImNUt@S-UuJ1;VQgu7Wk5hjOi4mRUotK-E;RsibaHHEZa_dsOi4mRUotK-E;RscVQFpvUs_XiG-YmNY)NBNbTKhwXkl_+baG*7baP2#MMY9mbTKnxVRLC?UvG1Ca%Ev{NmO4{FkeMeHeWzMM@&gVLs(c}GcGg$UteT%Z(nF(Ze(m_0AE^8Q)zN@MN(-%Ku1hTLPJ<sUo$Q=07O?Va%E;NUtec<cwca3a&vEPVQgu1d0%!g0BvP$V{myuKu1hTLPK9NE-^F!UteQ*VP9c%Wq4_HKtM-KNkT(kGA=SMH2_~)PBw3IVP9)9HDYyXY-B}t0AE^8Q*<_VWn*-2a!F}ZVM%F4MKL#DO<!_lVQg$~V_#`*b7gXLNlH>_MMXt+PB~v+XKr<0V|aKmH(y_FZ*py6Y+q?~WpZJ3Z*oacX;U#@MMXq#PgGw3Us_~rP<B8-M@&gVLs(c}GcGg$Us`T=Z9qUrOi4mRSXf^(E;ImNUvqR}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>MtB0AE@$Fk)$LVRCt2XJce|cmQo>ZEbIMWk5hjOi4mRUotK-E;RsOUuSrDUvOn|b8l{8Y-x0PUv@A+KtotqK|)DiF)lLzUrAI=Uu0!+WoKz~bY*f>O+##NZe>(qVr*pqUsY~*X>Md+Qe|^>ZDl|}M?*tjGcGUyUter#Vq;%pb9G;4X>Mr%Us_XiGh=CPKtM-KNkT(dSYI<PGyq>;Y-wU+UvqR}a&%v9VQFqaKu1hTLPK9NE;24P0AE^8Q*<#gV`yP=UvzR|X>@Z*V?{P>Wo~D5Xhl#<V*p=YXKin8UvqR}a&%u`0AEQ|O<!_lXK8bEWpY$aLu_wuWmI8eY-IpnT2pj1V`Xx3KtM-KNkT(dSYI<PGyq>(PE&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*00000FaQ7m000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000$N~TW00000$N~TW00000SONe5000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000AO!#b00000AO!#b00000T>=0A0000000000000000RR91000000000000000UH||9|NsAQ0ssI200000eg^;m00000eg^;m00000G5`Po000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000um=DD00000um=DD00000pa1{>000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000PzV4300000PzV4300000Pyqk{000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&00000pa}o~00000pa}o~00000Pyqk{000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000@CpC`00000@CpC`000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s6000005DNeR000005DNeR00000@Bjb+0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s60000001N;C0000001N;C000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s6000005DWkS000005DWkS00000q6q*10000000000000005C8xG000000000000000qW}N^0RR911^@s600000v=smV00000v=smV000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000z!d-h00000z!d-h00000F#rGn0000000000000001ONa4000000000000000u>b%70RR910ssI200000^c4UA00000^c4UA00000YybcN0000000000000001ONa4000000000000000zW@LL0RR910ssI200000U={!X00000U={!X00000Kmq^&0000000000000002mk;8000000000000000$p8QV0RR910ssI200000pcnuE00000pcnuE00000H2?qr0000000000000000RR91000000000000000+W-In4gdfE0{{R300000ARQn800000ARPbz000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000FdZNO00000FdYB@000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000I2|AW00000I2`~0000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000NFN{o00000NFM+I00000xBvhE0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000SOWk6000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000a0mbZ000008~^|SE&u=k2mk;8000007ytkO000002><{90{{R300000000000000000000xF`Ss00000O9cP`0000000000000000RR910000000000000005dZ)H0{{R30000000000000000000011<mn000005CH%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
from functools import reduce
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))


def sieve(n):
    n += 1
    res = [i for i in range(n)]
    for p in range(2, int(n**.5)+1):
        if res[p] < p:
            continue
        for q in range(p**2, n, p):
            if res[q] == q:
                res[q] = p
    return res


U = 10**6
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(int)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


# 10**6以下の素数しかでてこないから、鳩の巣原理的に考えて間に合う
facts = set()
for a in A:
    for k, v in prime_factor(a).items():
        if k in facts:
            if reduce(gcd, A) == 1:
                print('setwise coprime')
            else:
                print('not coprime')
            break
        facts.add(k)
    else:
        continue
    break
else:
    print('pairwise coprime')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy
import math
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]

# a,bの最大公約数


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# a,bの最小公倍数


def lcm(a, b):
    return a * b // gcd(a, b)


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


max_a = pow(10, 6)+5
N = z()
A = zz()
pari_flg = True

set_flg = True
count = [0]*max_a
for i in range(N):
    count[A[i]] += 1
for i in range(2, max_a):
    c = 0
    for j in range(i, max_a, i):
        c += count[j]
        if (c > 1):
            pari_flg = False
res = A[0]
for a in A:
    res = math.gcd(res, a)
if (res != 1):
    set_flg = False

if (pari_flg):
    print('pairwise coprime')
elif (set_flg):
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
ans = 0


def sieve(n):
    n += 1
    res = [i for i in range(n)]
    for p in range(2, int(n**.5)+1):
        if res[p] < p:
            continue
        for q in range(p**2, n, p):
            if res[q] == q:
                res[q] = p
    return res


U = 10**6
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(int)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


facts = set()
for a in A:
    for k, v in prime_factor(a).items():
        if k in facts:
            ans = 1
            break
        facts.add(k)
    else:
        continue
    break

if ans == 0:
    print('pairwise coprime')
else:
    if reduce(gcd, A) == 1:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
pc="pairwise coprime"
sc="setwise coprime"
nc="not coprime"

tmp=a[0]
for i in range(n):
    tmp=math.gcd(tmp,a[i])
if tmp!=1:
    print(nc)
    exit()

a.sort()

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def factorize(N,prime_list):  # prime_listに素数のリストをぶち込め！
    lst = []
    for p in prime_list:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            lst.append(p)
    if N > 1:
        lst.append(N)
    return lst

plst=primes(1000000)
dic={}
for i in range(n):
    fac=factorize(a[i],plst)
    for j in fac:
        if j in dic:
            print(sc)
            exit()
    for j in fac:
        dic[j]=1
print(pc)