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%0RR91fDixx00000KmY&$00000$SnW>0000000000Kma%Z2>?I<9snHx1^@s61ONa4KmY&$00000KmY&$00000KmY&$00000_yGU_00000_yGU_000002mk;8000000{{R31ONa4I066w00000I066w00000I066w000008~^|S000008~^|S000000RR91000000RR911poj5000000000000000000000000000000^ArF800000^ArF800000001BW000000RR911^@s6FdYB@00000FdZNO00000FdZNO00000=mG!$00000Pz3-000000001BW000000ssI21^@s6NF4wG00000NF5*m00000NF5*m000005CQ-I000005CQ-I000002mk;8000001ONa41ONa4R004100000R004100000R004100000L;wH)00000L;wH)000001ONa400000P~~)F1ONa4)Di#y00000)Di#y00000)Di#y00000Q~&?~00000Q~&?~000001ONa400000QRQ@G1^@s6000000000000000000000000000000000000000000000000005C8xG00000Qss1H1ONa4FdYB@00000FdZNO00000FdZNO00000&;kGe00000&;kGe000000RR9100000FKlUIHZ(76WG!rIZgqGqcsMpKHZ(4CZ!R(b1ONa45C8xG0RR91M^04$000000{{R30ssI2000001ONa46aWAK0{{R3M^04$ug{QZtu-*<=d^eLg9?uCsh2UD0ssI26aWAK0RR911^@s6000mI0RRL56aWAK000006qpP{bCw4J000000000000000000000000000000yZ`_I5&!@I00000000000000000000+yDRo5&!@I00000000000000000000)d2tiA^-pY00000000000000000000!2tjO5&!@I00000000000000000000U;qFB5&!@I00000000000000000000RR9105&!@I00000000000000000000$N>NV5&!@I00000000000000000000)c^nh5&!@I00000000000000000000VF3UD5&!@I00000000000000000000umJ!75&!@I0000000000000000000069E7K5&!@I00000000000000000000X8`~J5&!@I00000000000000000000{r~^~5&!@I000000000000000000009{>OVAOHXW00000000000000000000mjM6(5&!@I00000000000000000000<N*Kx5&!@I000000000000000000005C8xGAOHXW00000000000000000000I{*LxAOHXW00000000000000000000qyPW_5&!@I00000000000000000000e*pjh5dawgKp-Fh000005CH%H00000n*aa+5dawgU?Cs?000007y$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-?UKRc?1_Ze(9lWpj0HWdLkxVq-3IZ!R_fUte={VPk7wV`yt%W?^Y;0CRM5Y-Mf$UteQ*VP9c%Wq4_H0AF8Ycwt{=X>MU`X?kS<Uter#Vq;%(bYXIIUu|J&ZU9F^Ltis4FaSqPNkT(kGA=X#M@&gVLtip3GA=a$Ls(crLP=jSE;9f}Oi4mRSXf^(E;KGV07pzoLPJ<sUo$Q=000000ssO40{{a60ssO40{{X50ssU61pop71^@s62LJ;A000000ssO40ssI20RRC2i2(or5C8xGAOHXWP$qc`000L7_5lC@000000RRF3rU3u|5C8xGFaQ7m6lrM<000C4{s9005C8xGbsA|2000932m$~A000000RRI40RR915C8xG00000)30j<000I66aoMM5C8xGiGL{q000F59|8aX5C8xGbSaVu00062Edl@l00000FdZNO000002mk;800000fDr%y00000I2|AW000002mk;800000P!IqB00000Kph|e000002mk;800000KoI}{000002p}K;000002mk;8000002p}K;00000&>tWG000001^@s60{{R30000000000*dHJO000001^@s64gdfE0000000000;2$6W000001^@s65C8xG0000000000=pP^e000001^@s65dZ)H0000000000@E;%m000001^@s65&!@I0000000000_#Yqu000001^@s66951J00000000005Fj7`000000RR914FCWD0000000000Kp-Fh000001poj56aWAK0000000000U?Cs?000001poj56#xJL0000000000a33H5000002LJ#70RR910000000000cpo4D000002LJ#70ssI20000000000fFB?L000002LJ#71ONa40000000000h#w#T000002LJ#71poj50000000000kRKob000002LJ#71^@s60000000000m>(bj000002LJ#72LJ#70000000000pdTOr000002LJ#72mk;80000000000s2?Bz000002LJ#72><{90000000000upb}*000002LJ#73IG5A0000000000xE~+@000002LJ#73jhEB0000000000z#kw0000002LJ#73;+NC0000000000$R8j8000002LJ#74*&oF0000000000NQ3MMNQ(u%6(9geg}`(I|IkQ-#0bLx0000000000|1}yFAOQa*92Fn{4<A4P|0Nm~AOL6p0002#;Q#;s|0NO?AOL6q0002#(EtDc|0N0)AOL6r0002#!2kdM|0MzyAOL6s0002#u>b%6|0VhqAOL6t0002#p#T5>|0VJiAOL6u0002#kpKVx|0U`aAOL6v0002#fdBvh|0UuSAOL6w0002#aR2}R|0UWKAOL6x0002#VE_OB|0U8CAOL6y0002#Q2+n`|0T*4AOL6z0002#K>z>$|0Ti{AOL6!0002#F#rGm|0TK<AOL2N0000000000L03UmG5<kTK~z;!NP+CgOH2S{NQ(p|C;$KeNQs0bxJyg`F~H~*|Ns9;jdUbTNR2%S79apf#|7pVAOHXW008JI|Ns9;V_YOmNQK)EgmDA_07$t1|NsC0|NlQoIl~W!bp!waNR2F=00000NQv+0DF6TeNQuHoi9{qQF~DXIA4C8E#{_}^0000;gTMhuIm31ENQ-<VC`bYQNICsTiEJbgbR<ZPEsqr-07!}Z4<A4PNQvG^iSOvG{{R0-gTn+!Ib0+Vb?QisOe9c9jgdt{4**Ds$PXU?#sC3GgTMhuInZ_VNR5F=LJt5)jgeeSOaNvNA4C8E#{mET|NlsXzywG+&~@=hxBvhE009610LDZlQ2@q7Bv1fIiG(DWLJt7C0ssI2>l0=VA4C8ENQ1%wNP+rALJt6RPk=lT0EyOg>x~2wiIkB@LJt5vL_!Y$ciKpe1QKQsA4C8EgS>%ALJt7{#smQXbq9&Gfk;9R07wDQJw!qe0Dj>}gTetwf%-*44*+$sztpBZ0O$h#|NlshkkqC<07!{MBp_xFA4C8E#{d8T002mXzywG+!gcXTi+m&yNI85YC=Z0t0ssI=i$o+S#zZ7H0Z55NBsfTk1SDn;A4C8ENQ(p{ix`9Z0S|<w0000n$we{tMKS-7NMplAG31M^gqT7P01qDkiP%Ad!~vQ2{YYcbJFJwLLJt5)iPLoGOgZsEiNz0uGywnrL5VI!iDm>zgT@F!gZ%+@yG=R%bVW&H2S|%_Bp^tQ42FvVg}@Jw&;bAdNsU(s>mOz=4<Cd800000NMiy>gTe?%jSPm10foR1kE;Oy0E55*OgZw20d?U`h5vL2Oo{*K^!)$-NP`3<1W1bnBuF_#BoGgUIRF3ufP5r301t)a0RR9@i$o+4Op8n;I5EIx4<Cd800000Nn<fcWBBNm0{{R?gTVw%Il*=8gXjSdgo^<H07#8Ju>=4B==TEv07#8Br33%~NR2%i5+DFbiNffy{Qv(*jXeqyAOPq^{Qv(*i+m&?=xhA{|44&;Bq#uM3P_85Bq-=v{Qv(kz(|X{B)CgV0AxrrJS8Xq000k#%K-oYNP)!2OH2S;T|rzyT|r(!U&Ce(A4C8EOo{MJDfmc<!bpikBp67+`U6OX(hr240000;jRX=%Il@SZL?j3ghNS=i07%C~BnbHb|Nlsfd?X0y`1}9=NQ+b?7)SxaO*!|8DnyB51P_F<0000<jaLXsDb_L4Nx|*|PK`A62mk;84<A4PNs9~@NQn#(NQ1%%NjcVa?@0m1NrT1+O@;q-5=@EzNQp!w80e1s|NlsfL?jqUi%cX4Nr}fu0m11g{{R1G4<Cd800000NXJAZ2nYZG0O@f5|Nmx?#zZ7H0O?i!|Nlt8|NsC0|Ns9VNICcqhe-eb|1rQwgM1_i01t#s|Ns9;!Quo+iBu#A={5iV{|_I400000Nr}ekbpQYVNR2%f0{{T%YytoPNR2fL0{{R>jXjPKAOJ{-!ssUZ|NrT5{{R0-jXmB1008Jk0ssI=jWyB&002mhJ!cRg07!|#=>Piv|LIBo|NltGL?kEx0000;$3!F$00000>GAvj|L9Ko|Nlsd!$^aCBq#uM3P_85Bq->a`v3n(iQnkq`v3n;h5ty2!*mEtiT~(<`v3n(i+m&?=y&@6|Le-=koy1sNQuMi$ViF9>*Zz-A4C8ENR2%r5+DFbgX{?Ckoy1sNQ*s@4<G<YjTM>?AOJ{>H3SkM07!$x2<amF|Nmx?G3`l-(OyW2;z)z!@K97tjRpDv002mh4TAvy07#8JeER?Y{}nb5AOQ3aA4C8ENR2&V4<G<lNR0(q4<G<YIrvD4<#ZWHiv<b~AOJ{(z;q2=|KMgW4<Cd800000UBeF_KmcYg4<Cd800000NR2%q4<G<YjWrq%AOKZJDgH=_<w(K)14xPRNWthoNCC!3(f)K8NQ(v04j=$Xg}`(SUH{-_4<Cd800000UBeF_KmcYg4<Cd800000fITr0AOHY$FGzzue-0o3098nd<#Y^4i#@6iAOPsC`TzguNdN!;#svuxAOHbf!w(;T00000^TTEjA4C8ERY-~DUFl~3|NmwWA4C8ENQwGL!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>09{!|7I=^AA|q^0001xL03UmNr~4%RY6otjV1mHAOKZJjV%TXAOKTAiTz25_Dm_|NQ3MMNWuLB=+F26|44=HbRaR?4<Cd800000Oo{qTiS|T^??L|*+(?7N0Z2LBb?Qii#0XnmL0myyL0&;$!;oe!4<Cd800000^TPlDNQ3MMNQ1-(!vFvP0RRF3aA9e3cWHBFAY*TEa%pX40CQz@cWHBFAY*TEa%pX40B&z|AY*TEa%pX4000000UHB5Pyhe`2><{9Z1?~FoB#j-Jox|r!~g&QO!)u*Bmn>beEt9bcmV(ato{H0YybcNy#D|H@Bjb+Jpcdy+yDRoO#lD?lmP$$y#N3I+yMXp6aWAK000000eVsZ0eBDr8w>{skO2n}6aWAK8~^|SIQ{?sD*ylh00000000006aWAK000000eVsZ0eBDr8w>{skO2SyBme*a8~^|S$oBvL&;S4c01gmF4j4)g3wH>B06!W#Dl;S^000006aWAKL;wH)aQFZJ2mk;800000000005C8xGTmS$7SpNV21poj5000005C8xGZ~y=R#Qp#Oa{vGU000008~^|S000000eVnOQUC#X5C@wj3?Kj-8w>{skO2SyPyhe`Bme*aAou_ODg^)l1it_P074EBj{-st7>)x(4j_#LLJla51wjrlh6X_nID-dA4uF`k0s}+?3Jy3y4lqFuC_)Y(LJk;04iG{P2uBM57ytkO_y7O^{QLj^E&u=k080)KUJeKV00000L;wH)6afGLu>Jr4WdHyG074EBj{-st7>)x)4j_#LLJla51xOAsh6YFuID-dG4nT4aI6)3DK@KQF4j@7f7(xyZLJkN35C8xGTmb+8*!}<i0ssI20000000000|Nj9eCQ<+Zz5xZG3ILe{1>y++iUtv-3IL-A1^)>El?g1R3IN>+A^-pY0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000fDr%y00000P!IqB00000KoI}{000000RR91000000RR91000000RR9100000i2(or000000RR9100000rU3u|000003;+NC00000APN8g000004FCWD00000lo9{{0000082|tP00000FdZNO000008vp<R000005C8xG000008UO$Q00000Kph|e000008~^|S000002mk;800000_5S~F00000m;wL*000001poj500000&;$Sg000001^@s600000zybgO000003IG5A00000IRXFx000003jhEB000007ytkO000006#xJL0000000000000000{{R300000SRWt&000000ssI200000AOQdX000006aWAK000002LJ#7000007XSbN0000000{s9000002LJ#700000$Oixb000002mk;800000H~|0v000002><{9000007ytkO000009smFU000002mk;800000`~UxM000000RR9900000{{R1P00000I0pa#00000|NsAQ000000{{R300000@c;jB000003I_lH00000`TzfK000001ONa4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000NF5*m0000000000000000000000000Rtf+B00000W(oiR00000b_xIh00000h6(@x00000mI?p>00000rV0Q600000wh90M00000#tHxc00000)(QXs00000<_Z7+00000_6h(1000001`7ZH0000000000000000000000000000000000000000000000000000000000000000000000000002p}K;000000000000000M?*t8AShL0b#8QZAU7^GE-)=Kbz*gHbagR)F*q(TG$|lAE;TMN0000000000000000000000000000000000000000000000{{U4I066w000000000000000000000{{X5R0041000000000000000000000{{a6bOHbX000000000000000000000{{d7m;wL*000000000000000000000{{g8zybgO000000000000000000000{{j9&;$Sg000000000000000000000{{mA3I_lH000000000000000000000{{pBI0pa#000000000000000000000{{sC$Oixb000000000000000000000{{vD00{s9000000000000000000000{{yEAPN8g000000000000000000000{{#FKnef=000000000000000000000{{&G5DNeR000000000000000000000{{*HAPWEh000000000000000000000{{;Ilo9{{000000000000000000000{{>Jpb`K8000000000000000000000{{^K)Di#y000000000000000000000{{{LC=&nx000000000000000000000{{~M$P@qo000000000000000000000{|2NFdZNO000000000000000000000{|5OKph|e000000000000000000000{|8PNF5*m000000000000000000000{|BQSRWt&000000000000000000000{|ER03aX$000000000000000000000{|HSKp-Fh000000000000000000000{|KT000000000000000000000RR911OV~>000000000000000000002><{90ssyGP!IqB00000E&u=k00000DF6Tf0RR~Qc_JVH000000RR9100000H~;_u1OV~>00000000000000000000LjV8(0ssyGun+(M000000000000000MF0Q*0ssyG@DKn1000000000000000SO5S30ssyGKoI}{000000000000000ZU6uP0RR~Qcp@MG000000RR9100000eE<Le0RR;MKph|e000000000000000qyPW_0ssyGfDr%y000000000000000umAu60RR*LFdZNO000000000000000H~;_u1OV~>00000000000000000000&j0`b0RR#J#1sGk000000000000000000001OV~>00000000000000000000-2eap000pH)Di#y000000000000000@Bjb+0RR>NNF5*m000000000000000`2YX_000yKKph|e0000000000000003IPBB000yKFdZNO0000000000000009RUCU0RR^OSRWt&000000000000000GXVeq5C9ke7$6`3000000000000000I|Bd!AOIKu03aX$000000000000000IspIx5daVXpb`K8000001ONa400000NdW)=5&!@I00000000000000000000Zvg-R5&!@I00000000000000000000o&f*=A^-pY00000000000000000000x&Z(H5&!@I00000000000000000000&H(@b5&#YWAPWEh00000Dg^)l00000(*Xbg5&!@I000000000000000000008v+0T5ds(h2p}K;000000000000000C;|Wg5&!@I00000000000000000000Kmq^&Ap#fx5Fj7`000002mk;800000<^uo#5&#bXlo9{{000000000000000Tmk?95&!@I00000000000000000000b^-tZ5&!@I00000000000000000000KLY>&5&#YWfDixx00000D*ylh00000iUI%t5&!@I00000000000000000000odN&=5&!@I00000000000000000000fdc>l5&#PTAPN8g000000000000000xdH$H5ds(h7$6`3000000000000000#R32T5&!@I00000000000000000000A_D*b5dawgKp-Fh000005CH%H00000IRgLy5C9ke03aX$0000000000000001pxp65C9nffFd9O000000000000000Mgsr<5C9nf7$6`3000000000000000QUd@05&!@I00000000000000000000cLM+b5&#YWAQAuo00000WdHyG000007ytkO5&#YWkP!d?00000a{vGU00000hXVir5&!@I00000000000000000000r~?21AOHXW00000000000000000000!~*~T5&!@I00000000000000000000+yejr5&#YWkP-j@000000ssI200000>;nJ*5dawgU?Cs?000007y$qP000000t5g65&!@I00000000000000000000Ap`&bA^;8m5E1|Y000001poj500000LIeN+AOHXW00000000000000000000Q3L=0AOHXW00000000000000000000YXkrQ5&!@I000000000000000000000BvDuZZ2bE0AEK;PeMUVUte=|VqZyLUs^FRVrgz+a(Q28V`O-E0AE^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|uAPhWF%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@A6UteQ*VP9c%Wq4_HKtM-KNkT(kGA=SMH2_~)WNc7&KtM-KNkT(dSYI<PGyq>(Zg*`!Ku1hTLPJ<sUo$Q=0AF8obYWv_Ut?%%UuI!xY(PLqOi4mRUotK<0AF8JO+#NrPDEc{0AE^DbTKwxUvG1Ca%Ev{UukZ0WpZ>$V^ef7F=J?9a$j_EVQF-8Nn=GtQd4v>Gh$(LX=7h+b98cLVQooNUsNz(MN>9kP)k!YUu-}?M@&gVLs(c}GcGhPIRIZ;Q*<<AZ*_D)Ku1hTLPJ<sUo$Q=0AF8ZVRT_%b97;HbO2vpVsmp}b97;HbO2vkPE&L^X>W61VqtS-G)Zo0bVD&kc0fQ!Oi4mRSXf^(E;ImNUu<b&V_#!)bzf<2X><TzUuSrDUvOn|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-IpnT251RIB9QlUt(c%Wi&}{X>>#}MRq_yM@&gVLs(c}GcGg$04{TRZFFH`04{TMa&%#004{TAb98caVPXI-X>N37a&Q1HZf|sDE<r*`Ep%aL04{ECbY(7QZgnnVb!lv5Eoo!`E@y6aE@)wMXaFu`d2VxgZ2&H0d2VxbasV!8ZgnnpWpZ<AZ*BlCXKr;ac4cyNX>V>{asV!JWo%(CWO;4?E^=jTVJ>iNbO0`CZfSG?E^usgE@y9a04{W8cys_RW@&C|04{QGWMOn+04`-{UuJS)ZDn6*WO4v5WoTb!a$#*{04`@^V_#)>V`Xr3Uvyz&Y-Ip0X>MtBUtw}`VR-;9W@&C|Utw}`VR-;9WO;63ZE0fwE@WYJVE`^-b8`SLV{dJ3Wo~o;000000000000000000000000000000000000000000000000000000000000000000000000000000008vp<R0RR910ssI200000I066w00000I066w000008~^|S0000000000000000RR91000000000000000BLDyZ2LJ#70ssI200000R004100000R004100000AOHXW0000000000000001ONa4000000000000000F#rGn2LJ#70ssI200000bOHbX00000bOHbX00000Bme*a0000000000000001ONa4000000000000000L;wH)_W%EH0ssI200000m;wL*00000m;wL*00000C;$Ke000001poj5000002mk;8000000000000000P5=M^3jhEB0ssI200000zybgO00000zybgO000005CQ-I000001^@s60RR912mk;8000007ytkO00000RsaA10{{R30ssI200000&;$Sg00000&;$Sg00000IRXFx0000000000000000RR91000000000000000UH||9|NsAQ0ssI2000003I_lH000003I_lH00000EC2ui000001poj5000000ssI2000000ssI200000YXATM{{R1P0ssI200000I0pa#00000I0pa#00000kN^Mx000001^@s60{{R32mk;8000000000000000dH?_b1ONa40ssI200000$Oixb00000$Oixb00000H~|0v000001poj5000002mk;8000007ytkO00000ga7~l1ONa4LI3~&0000000{s90000000{s900000AOQdX000001poj57XSbN2mk;8000007ytkO00000jsO4v0RR911^@s600000APN8g00000APN8g000007XSbN0000000000000001ONa4000000000000000i2wiq0RR911^@s600000Knef=00000Knef=00000&;S4c0000000000000005C8xG000005C8xG00000lmGw#0RR911^@s6000005DNeR000005DNeR000002mk;80000000000000002mk;8000002mk;800000od5s;0RR911^@s600000APWEh00000APWEh00000at8na0000000000000005C8xG000000000000000qW}N^0RR911^@s600000lo9{{00000lo9{{000002><{90000000000000001ONa4000000000000000sQ>@~0RR910ssI200000pb`K800000pb`K800000F#rGn0000000000000001ONa4000000000000000u>b%70RR910ssI200000)Di#y00000)Di#y00000Q~&?~0000000000000001ONa4000000000000000zW@LL0RR910ssI200000C=&nx00000C=&nx00000paB2?0000000000000002mk;8000000000000000$p8QV0RR910ssI200000$P@qo00000$P@qo00000D*ylh0000000000000000RR91000000000000000+W-In4gdfE0{{R300000FdZNO00000FdYB@000005C8xG0000000000000002mk;8000002mk;800000=Kufz4*&oF0{{R300000Kph|e00000Kpg-8000002mk;80000000000000002mk;8000002mk;800000^8f$<1^@s60{{R300000NF5*m00000NF4wG000005CQ-I000001^@s6000002mk;8000005C8xG00000m;e9(0RR910{{R300000SRWt&00000SRViY00000r~m)}0000000000000002mk;8000002mk;800000`~Uy|0RR910{{R30000003aX$0000003ZMW000007ytkO0000000000000002mk;80000000000000000s#O32mk;80{{R300000Kp-Fh000007$5)u00000Kmq^&000000000000000KmY&$0000000000000002LS*80RR91FaQ7m0000000000000007$5)u00000DF6Tf0000000000000000RR91000000RR91000000RR910ssI200000000000000000000NFV?J00000;0FKz000008~^|SE&u=k2mk;8000007ytkO000002><{90{{R300000000000000000000C@25`00000kOTk#0000000000000000RR910000000000000005dZ)H0{{R300000000000000000000xGVqw000005CH%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:
import math
N = int(input())
A = list(map(int, input().split()))

maxA = max(A) + 1

C = [0] * maxA

g = 0

for a in A:
    C[a] += 1
    g = math.gcd(g, a)

pairwise = True

is_prime = [True] * maxA

for i in range(2, maxA):
    if is_prime[i]:
        cnt = 0
        for j in range(i, maxA, i):
            cnt += C[j]
            is_prime[j] = False

        if cnt > 1:
            pairwise = False

if pairwise:
    print("pairwise coprime")
    exit()

if g == 1:
    print("setwise coprime")

else:
    print("not coprime")

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
m = max(A)
C = [0 for a in range(m + 1)]
for a in A:
    C[a] += 1
s = 0
for a in range(2, m + 1):
    s = max(s, sum(C[a::a]))
if s < 2:
    print('pairwise coprime')
elif s < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
m = max(2, max(A))
P = {p: True for p in range(2, m + 1)}
for i in range(2, m + 1):
    for j in range(2 * i, m + 1, i):
        P[j] = False
Pmap = {p: 0 for p in P if P[p]}
Amap = {a: 0 for a in range(1, m + 1)}
for a in A:
    Amap[a] += 1
for p in Pmap:
    for a in range(p, m + 1, p):
        Pmap[p] += Amap[a]
s = max(Pmap.values())
if s < 2:
    print('pairwise coprime')
elif s < n:
    print('setwise coprime')
else:
    print('not coprime')

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]


class Prime:
    @staticmethod
    def trial_division(x):
        if x % 2 == 0:
            return True
        for p in range(3, int(x**0.5 + 1), 2):
            if x % p == 0:
                return False
        return True

    @staticmethod
    def factorization(n):
        a = set()
        while n % 2 == 0:
            a.add(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.add(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.add(n)
        return a

    @staticmethod
    def miller_rabin(n):
        def suspect(a, t, n):
            x = pow(a, t, n)
            n1 = n - 1
            while t != n1 and x != 1 and x != n1:
                x = pow(x, 2, n)
                t <<= 1
            return t & 1 or x == n1

        if n == 2:
            return True
        if n < 2 or n % 2 == 0:
            return False
        d = (n - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        if n < 2**32:
            check_list = (2, 7, 61)
        elif n < 2**48:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23)
        else:
            check_list = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

        for i in check_list:
            if i >= n:
                break
            if not suspect(i, d, n):
                return False
        return True


c = collections.defaultdict(int)
for a in A:
    for p in Prime.factorization(a):
        c[p] += 1
ans = 'pairwise coprime'
if c:
    x = max(c.values())
    if x == 1:
        ans = 'pairwise coprime'
    elif x == N:
        ans = 'not coprime'
    else:
        ans = 'setwise coprime'
print(ans)

Submission status: Accepted

Solution code:
import math

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

a_max = (10**6)+1
hist = [0] * a_max
for a in a_list:
    hist[a] += 1

pairwise = True
for i in range(2, a_max, 1):
    count = 0
    for j in range(i, a_max, i):
        count += hist[j]

    if count > 1:
        pairwise = False

if pairwise:
    print('pairwise coprime')
else:
    setwise = True
    g = a_list[0]
    for a in a_list:
        g = math.gcd(g, a)
    if g > 1:
        setwise = False

    if setwise:
        print('setwise coprime')
    else:
        print('not coprime')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from math import gcd
from functools import reduce
from collections import defaultdict


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def is_pairwise_coprime(A):
    n = max(A)
    base = [False for i in range(n+1)]
    for a in A:
        if a > 1 and base[a]:
            return False
        base[a] = True
    
    is_prime = [True for i in range(n+1)]
    for i in range(2, n+1):
        if is_prime[i]:
            include_number = set()
            if base[i]:
                include_number.add(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
                if base[j]:
                    include_number.add(j)
            if len(include_number) >= 2:
                return False
    return True


def solve(N, A):
    if is_pairwise_coprime(A):
        return "pairwise coprime"
    if reduce(gcd, A) == 1:
        return "setwise coprime"
    return "not coprime"


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
maxa = max(A)
cnt = [0] * (maxa + 1)
for a in A:
    cnt[a] += 1

from math import gcd
from functools import reduce
if reduce(gcd, A) != 1:
    print('not coprime')
else:
    for i in range(2, maxa+1):
        if sum(cnt[i::i]) > 1:
            print('setwise coprime')
            break
    else:
        print('pairwise coprime')

Submission status: Accepted

Solution code:
def main():
    import math
    n = int(input())
    a = sorted(list(map(int,input().split())))
    g=a[0]
    for i in range(1,n):
        g = math.gcd(g,a[i])
    if g > 1:
        print('not coprime')
        return
    d = [1 for i in range(a[-1])]
    for i in range(2,a[-1]+1):
        if d[i-1] == 1:
            for j in range(1,a[-1]//i+1):
                if d[i*j-1] == 1:
                    d[i*j-1] = i
    prm = {}
    for i in range(n):
        p = []
        while a[i] != 1:
            p.append(d[a[i]-1])
            a[i] = a[i] // d[a[i]-1]
        p = set(p)
        for p_ in p:
            if prm.get(p_)==None:
                prm[p_] = 1
            else:
                print('setwise coprime')
                return
    print('pairwise coprime')

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
M=10**6+1
f=lambda p: exit(print(['pairwise','setwise','not'][p]+' coprime'))
n=int(input())
l=[*map(int,input().split())]
g=0
from math import *
for x in l:
  g=gcd(g,x)
if g>1: f(2)
def sieve(x):
  p=[]
  s=[0]*x
  for i in range(2,x):
    if s[i]<1:
      p+=[i]
      for j in range(i,x,i): s[j]=i
  return s
s=sieve(M)
C=[0]*M
for x in l:
  t=set()
  while x>1:
    t.add(s[x])
    x//=s[x]
  for y in t:
    if C[y]: f(1)
    C[y]=1
f(0)

Submission status: Accepted

Solution code:
import math
 
N = 1000001
 
spf = [*range(N)]
i = 2
while i * i < N:
  if spf[i] == i:
    for j in range(i * i, N, i):
      if spf[j] == j:
        spf[j] = i
  i += 1
  
r = 'pairwise'
 
input()
d = 0
u = set()
for x in map(int, input().split()):
  d = math.gcd(d, x)
  s = set()
  while x > 1:
    p = spf[x]
    if p in u:
      r = 'setwise'
    s.add(p)
    x //= p
  u |= s
print((r, 'not')[d > 1], 'coprime')

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
def p(n):
    """ """
    min_facts = [0] * (n+1)
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if not is_prime[i]:
            continue
        min_facts[i] = i
        
        for j in range(i*2, n+1, i):
            is_prime[j] = False
            if min_facts[j] == 0:
                min_facts[j] = i
    return min_facts

min_facts = p(max(A))
fact_counts = dict()
for a in A:
    appeared = set()
    while min_facts[a] > 0:
        f = min_facts[a]
        if not f in appeared:
            fact_counts.setdefault(f, 0)
            fact_counts[f] += 1
            appeared.add(f)
        a //= f

pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == N:
        print('not coprime')
    else:
        print('setwise coprime')

Submission status: Accepted

Solution code:
from math import gcd
max_a = int(2e6)
factor = [0]*max_a
for p in range(2,max_a):
  if factor[p]:
    continue
  factor[p] = p
  for x in range(p+p,max_a,p):
    if factor[x]:
      continue
    factor[x] = p

def prime_fac(ai):
  while factor[ai]:
    yield factor[ai]
    x = factor[ai]
    while x == factor[ai]:
      ai = int(ai/factor[ai])

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

cnt = [0]*max_a
loop_end = False
g = 0
pairwise_coprime = True
setwise_coprime = True

for ai in a:
  for p in prime_fac(ai):
    if cnt[p]:
      pairwise_coprime = False
      loop_end = True
    cnt[p] = 1
    if loop_end:
      break
  if loop_end:
    break

for ai in a:
  g = gcd(g,ai)
setwise_coprime = g==1

if pairwise_coprime:
  print('pairwise coprime')
elif setwise_coprime:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

def trial_division(n):  # n > 1
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def eratosthenes(n):
    a = [1]*(n+1)
    for i in range(2,int(n**0.5)+1):
        if a[i]:
            for j in range(i*i,n+1,i):
                a[j]=0
    return [i for i in range(2,n+1) if a[i]]

flag = 0
ans = ['pairwise coprime', 'setwise coprime', 'not coprime']

n = readint()
a = readints()

prime = eratosthenes(10**6)

check = {x:0 for x in prime}

for x in a:
    for y in set(trial_division(x)):
        check[y] += 1

m = max(check.values())
if m==n:
    flag = 2
elif m>1:
    flag = 1
print(ans[flag])

Submission status: Accepted

Solution code:
N = int(input())
li = list(map(int,input().split()))

S = max(li)
L = [0] * (S+1)

import math
from functools import reduce

if reduce(math.gcd,li) != 1:
    print('not coprime')
    exit()

for i in li:
    L[i] = 1

for k in range(2,S+1):
    t = 0
    for j in range(0,S+1,k):
        t += L[j]
    if t > 1:
        print('setwise coprime')
        exit()
print('pairwise coprime')

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
maxa = max(A)
min_facts = [0] * (maxa+1)
def p(n):
    """ """
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if not is_prime[i]:
            continue
        min_facts[i] = i
        
        for j in range(i*2, n+1, i):
            is_prime[j] = False
            if min_facts[j] == 0:
                min_facts[j] = i
p(maxa)
fact_counts = dict()
for a in A:
    while min_facts[a] > 0:
        f = min_facts[a]
        fact_counts.setdefault(f, 0)
        fact_counts[f] += 1
        while a%f == 0:
            a //= f

pairwise = True
for c in fact_counts.values():
    if c > 1:
        pairwise = False
        break

if pairwise:
    print('pairwise coprime')
else:
    if max(fact_counts.values()) == N:
        print('not coprime')
    else:
        print('setwise coprime')