fork download
  1. from typing import Iterable, Dict
  2. import re
  3. from abc import ABC
  4.  
  5. class Advent_19:
  6.  
  7. class WorkflowRule(ABC):
  8. """An abstract base class for a workflow rule."""
  9.  
  10. def test(self, part: Dict[str, int]) -> str:
  11. """Test a rule against a part and return either:
  12. '' (Rule did not fire) - or -
  13. 'R' (Rejected) - or -
  14. 'A' (Accepted) - or -
  15. A new workflow name"""
  16.  
  17. class DefaultWorkflowRule(WorkflowRule):
  18. """This rule always fires."""
  19.  
  20. def __init__(self, action: str):
  21. self._action = action
  22.  
  23. def test(self, part: Dict[str, int]) -> str:
  24. return self._action
  25.  
  26. class ConditionalWorkflowRule(WorkflowRule):
  27. """This rule fires only if a condition exists as defined by
  28. this rule."""
  29.  
  30. def __init__(
  31. self,
  32. part_category: str,
  33. comparison_operator: str,
  34. comparison_value: int,
  35. action: str,
  36. *_
  37. ):
  38. self._part_category = part_category
  39. self._comparison_operator = comparison_operator
  40. self._comparison_value = comparison_value
  41. self._action = action
  42.  
  43. def test(self, part: Dict[str, int]) -> str:
  44. value1 = part[self._part_category]
  45. value2 = self._comparison_value
  46. result = value1 > value2 if self._comparison_operator == '>' else value1 < value2
  47. return '' if not result else self._action
  48.  
  49.  
  50. def __init__(self, lines: Iterable[str]):
  51. self.read_workflows(lines)
  52. self.read_ratings(lines)
  53.  
  54. def read_workflows(self, lines: Iterable[str]) -> None:
  55. workflows = {}
  56. workflow_rex1 = re.compile(r'([a-z]+){([^}]+)}')
  57. workflow_rex2 = re.compile(r'([xmas])([<>])([0-9]+):([a-z]+|R|A)|([a-z]+|R|A)')
  58.  
  59. while (line := next(lines)) != '':
  60. m = workflow_rex1.search(line)
  61. workflow_name = m[1]
  62. workflow_rules = []
  63. for m in workflow_rex2.finditer(m[2]):
  64. groups = list(m.groups())
  65. if groups[2] is not None:
  66. groups[2] = int(groups[2])
  67.  
  68. if groups[4]:
  69. # Default rule:
  70. workflow_rules.append(Advent_19.DefaultWorkflowRule(groups[4]))
  71. else:
  72. # Condiitonal rule:
  73. workflow_rules.append(Advent_19.ConditionalWorkflowRule(*groups))
  74.  
  75. workflows[workflow_name] = workflow_rules
  76.  
  77. self.workflows = workflows
  78.  
  79.  
  80. def read_ratings(self, lines: Iterable[str]) -> None:
  81. ratings = []
  82. ratings_rex = re.compile(r'([xmas])=([0-9]+)')
  83.  
  84. try:
  85. while (line := next(lines)) != '':
  86. d = {}
  87. for m in ratings_rex.finditer(line):
  88. d[m[1]] = int(m[2])
  89. ratings.append(d)
  90. except StopIteration:
  91. pass
  92.  
  93. self.ratings = ratings
  94.  
  95.  
  96. def is_accepted(self, rating: Dict[str, int]):
  97. workflows = self.workflows
  98. workflow_name = 'in'
  99. while True:
  100. workflow_rules = workflows[workflow_name]
  101. for workflow_rule in workflow_rules:
  102. workflow_name = workflow_rule.test(rating)
  103. if workflow_name: # Rule fired
  104. if workflow_name == 'R':
  105. return False
  106. if workflow_name == 'A':
  107. return True
  108. break # Else process workflow name
  109. # Else process next rule
  110.  
  111. def part1(self) -> int:
  112. """Solves Part 2 of Day 19 Advent of Code.
  113. See: https://a...content-available-to-author-only...e.com/2023/day/19"""
  114.  
  115. return sum(
  116. sum(rating.values())
  117. for rating in self.ratings
  118. if self.is_accepted(rating)
  119. )
  120.  
  121. if __name__ == "__main__":
  122. import sys
  123. program_input = sys.stdin.read().split('\n')
  124.  
  125. puzzle = Advent_19(iter(program_input))
  126. print(puzzle.part1())
  127.  
Success #stdin #stdout 0.04s 10384KB
stdin
qdg{a>3896:kg,s>540:tjk,s>478:A,A}
gzl{m<1268:A,s>979:vc,zqk}
mvd{s>1872:A,x>3724:A,vp}
fcg{a>1544:R,s<557:A,s>957:A,A}
gmb{x<809:A,x>1490:A,a>109:A,A}
hdh{x<839:R,a>1530:mg,mkb}
sm{a<59:R,m>1921:R,s>578:A,A}
lz{m<530:R,R}
vkm{x>541:sn,a<3531:R,x>322:tl,R}
srr{x>2868:R,A}
fh{m>3795:A,m>3694:A,s<1294:R,R}
ztk{s>1791:A,m<1364:R,a>3383:fx,A}
vcp{a<3090:thl,a>3580:czh,mhk}
czh{s<1457:gc,x<1505:gl,x>2388:sg,gp}
kp{s>2499:btp,zqd}
hh{x>2791:A,x>2466:A,A}
pr{x<1973:dnz,a<3949:nn,pfl}
qkr{x<1069:qb,qsd}
xt{a<2960:R,s<1141:A,x>914:R,A}
hp{s<3544:A,R}
snn{s<2457:zxm,R}
qb{x<627:A,a<1470:A,x>831:hr,hpn}
zhv{x<1751:R,s<1348:A,s>1361:A,A}
qcr{s>2370:A,R}
pkq{m>3170:R,R}
jk{s<705:A,a>2489:A,R}
gb{m<2661:R,A}
pdd{x<658:R,R}
nfr{a>1692:kpf,x>722:nsm,tpx}
lll{s<560:vqp,ssp}
hr{m<1766:R,A}
rl{x<1745:trn,s<2332:A,jgh}
ztc{x<2474:fj,s<1068:R,A}
fnt{m>2570:A,a>1708:cm,a<1661:A,A}
lh{a<3688:rvd,x>1270:jcx,x>1144:qcr,psr}
lqq{m<1390:vl,A}
mkb{s>3551:A,R}
zk{s>614:A,x>3124:A,a>3003:A,R}
ffh{m>3626:A,x<1925:R,R}
xrq{x>1344:A,a<280:R,m<360:R,R}
zcx{x<2337:nhn,a>384:dx,s<628:dq,td}
gmd{x>3241:hpq,a<3743:nfs,a<3800:nv,cq}
zvb{a>617:R,a>572:chk,ph}
dfh{s<3154:A,x<3731:R,a>1581:ttv,jmt}
gh{x>1901:A,R}
mvh{x>3546:A,s<685:A,R}
kg{a<3951:R,A}
nqm{x<960:tdl,a>3785:mhl,m>2700:kph,lh}
gf{m>1794:fn,x<2038:rl,x<2196:vhc,ktb}
btp{s<3352:ssg,x>1553:mm,m<1975:pf,msd}
czz{x>1788:R,A}
hpq{a>3672:A,A}
fsz{a<307:shz,a>588:nxd,st}
tf{a<1501:nbj,m<1908:jfr,x<3238:rxs,kj}
kfz{s>1112:A,lvp}
zt{s>1451:R,s>1379:xht,a>462:zhv,R}
mmb{x<662:lfz,cxb}
ldh{x<3242:R,R}
grt{a>560:R,s>305:A,a>365:R,R}
gjs{x<1556:A,x>2869:R,R}
kz{m>773:R,m<694:R,R}
mmv{a>2908:R,a<2890:R,a<2900:R,A}
cl{s>2605:A,s<2166:R,R}
vxt{m<3583:R,m<3756:R,A}
lq{m<705:gjs,s<983:cp,s<1374:ksz,vfm}
zht{m<3617:R,A}
gfn{x>850:A,a>1487:zns,a<1404:R,A}
cj{x>1979:R,m<995:A,nqt}
jt{a<2336:A,a<2552:R,R}
psr{m<2138:A,a<3746:A,R}
flb{m<1118:R,s<2797:szr,x<584:R,vxl}
jbb{m>2557:A,s<2147:R,m<1296:A,R}
mmz{a<166:A,m<3330:A,A}
td{m>528:zph,mhr}
lmt{x>1383:A,a>3769:A,A}
st{m>2913:A,R}
fxs{m>1823:km,m>623:krv,pgn}
kpf{a>1709:A,a<1701:A,R}
pkx{s<3455:nl,a<894:A,R}
lr{m>3552:qc,m<3355:cc,pj}
zfx{s<2696:R,A}
skk{s>1154:R,R}
km{a<1830:lmz,a<1964:ch,R}
mhl{s>2540:A,a<3884:srq,s>1934:A,rds}
hq{s<1312:gfn,hg}
mhr{x<3405:A,m<254:pdn,R}
npj{x>3322:R,R}
sg{a<3842:nzh,sd}
dqx{m<239:R,A}
zr{a>851:cgs,A}
tlm{s>3676:R,x<878:brg,vsm}
hst{x<2559:A,s>363:R,A}
lc{s>1852:A,R}
bqq{x>1066:fsf,x>610:nnz,hdv}
kph{x>1169:A,s>2487:nnv,m<3448:A,R}
zgc{a>1558:A,x>3608:sfv,R}
sj{s<2157:hq,s>3139:xm,qkr}
dq{x>3258:ltx,kpp}
dpc{m<3225:R,m<3722:R,x<1715:A,A}
qxp{s>1092:R,R}
kdl{a>1965:xj,xk}
ch{x<2766:A,x<3456:R,x>3672:A,R}
nzh{m>2465:gmd,x>3169:srv,zs}
xd{x<1228:lpx,x<1429:R,A}
gl{m<1794:bdn,nqm}
csn{m>1773:R,a<1142:A,R}
kbj{s<2930:A,R}
xmt{a>266:hcb,x<2147:R,nc}
pvt{a>1613:A,m>359:A,a>1598:R,R}
ljd{m<470:A,A}
tg{x>298:R,s>927:R,x<140:R,A}
cfp{m>1471:R,s>3153:A,m<516:A,A}
bfg{a<3975:R,m<3044:R,A}
xhs{a>1107:qn,m>426:A,m>157:A,stb}
ssp{s<803:vkt,m<3159:pxp,x>2245:tj,fz}
spj{s<2285:A,R}
sgm{m<2781:A,x<1052:dm,R}
gjk{s<646:vkf,m<2932:szp,m>3057:xnl,hkh}
hzc{m>930:R,R}
pfl{x>2116:A,A}
xnk{x<421:A,x<696:R,A}
dl{m>1471:gqn,xjh}
tl{s>1656:R,a>3559:A,R}
vvb{s>2261:R,R}
ttv{a<1613:A,a<1623:R,A}
ddt{x>3345:A,R}
brg{a<1456:A,x>525:A,R}
ssg{s<2935:cs,xb}
px{s>2926:R,R}
bjj{m>875:A,x<2388:A,a>1560:R,A}
jvc{x<2165:R,x>2274:R,x>2211:R,A}
khz{x<254:R,A}
qd{m>2081:R,m<1273:A,A}
srv{a<3694:R,nx}
hcn{x>1979:R,a>3055:A,a<3032:R,A}
mlq{m>2945:A,R}
gqn{a<3177:R,kd}
mb{x>2340:khn,s<632:pcn,a<531:pqm,R}
vz{a<3254:A,m>2111:R,m<1228:tg,gmr}
qsh{a>3516:sjt,s<1806:A,m>2549:fml,gqv}
mh{x<520:A,R}
cg{s>903:A,R}
cls{x<572:A,a>874:fhn,A}
vkt{x<1526:R,x<3037:A,s>698:rhv,A}
qh{x<1112:pdd,a>1056:A,mx}
khn{m>1683:R,R}
jtg{a<362:A,a>413:A,A}
tpx{x<455:R,m>2065:A,A}
zqd{s<2044:tfn,s<2247:hdf,flm}
kvm{m>3480:A,s<3620:A,R}
vsm{s<3325:R,a>1444:A,x<1338:R,A}
hl{m<3229:A,A}
cb{s>1825:A,x>2840:R,s>1640:R,R}
cd{s>889:rf,ghm}
nbs{m>1525:R,x>2977:A,R}
jv{x>666:rnm,a<3434:htp,s<2082:bh,R}
vkf{s>336:R,x<1336:R,A}
vxl{m<1386:R,R}
llk{a>1544:A,A}
vj{s>1374:A,a>3033:vdc,m>2684:zk,R}
vlv{s<287:lzx,x>1685:zht,xn}
ph{a>545:A,a<516:R,m>262:A,R}
sd{m<2201:cv,lmh}
sc{m<833:R,R}
vl{s<2172:A,x<3066:A,x<3530:A,A}
xnh{m<671:R,a>266:R,A}
vr{s>1110:ckb,s>806:A,A}
bgl{a>2783:A,a<2771:R,R}
csq{a<3716:A,A}
nf{a>3884:R,R}
dzv{x<1216:R,s>435:R,sq}
nk{m>3277:pzz,x>3415:mvd,x>3039:qt,srr}
qm{a<2532:R,A}
qk{m>1458:R,m>762:A,A}
jvz{a<2864:dv,a<2925:qjg,ddt}
bkz{a>3856:R,m<2902:A,a<3715:A,R}
hj{a<228:czq,m>1831:R,lb}
hbl{m>3744:R,A}
shz{s>1282:R,m>2858:xtg,s<1132:hcq,R}
jfr{s<2642:vdx,a<1581:gxb,tlz}
vnb{a>3295:nh,m>970:R,R}
mfg{m<3239:gjk,s>686:vxf,vlv}
lzx{m>3552:R,m>3392:gcq,A}
crf{s<1148:R,bz}
pks{x>1580:A,a>493:R,a>230:A,R}
lm{m<888:A,m>1424:pv,jvc}
ltx{x>3725:nj,m>388:tc,rcp}
gmz{s>526:jhb,x<1479:thn,bhb}
bdn{a>3810:flb,a>3680:mlp,jf}
msv{x>1658:A,m<3399:R,a<592:R,R}
srq{a>3822:R,x<1250:A,m<3223:R,R}
cf{a>3181:R,R}
lmh{x<2951:R,s>2719:R,vvb}
pgn{a<1879:rhr,x>2964:dxr,m<344:jkz,ljd}
fmm{x<1264:R,a>3156:R,R}
rf{a>523:A,s<1242:R,R}
kq{x>1882:R,R}
pm{a<465:R,m<3694:hnc,m>3816:R,R}
nv{x>2750:R,s>2595:A,s>2037:R,R}
bmb{x<1389:A,m<1638:R,R}
stb{a<1009:A,x<854:R,R}
zj{s<1284:A,A}
gcs{m<3562:mmz,kkn}
sxg{m>1526:R,A}
sn{x>889:A,x>769:R,m>2027:R,A}
qvm{s<1337:rr,s>2931:fc,x>1754:jt,zh}
hpn{s<2511:R,R}
hkn{a>2967:vj,s>1378:nkl,s>603:jvz,lvd}
ll{a<2547:jk,a>2624:ttl,A}
qfd{m>3298:R,x>2017:R,a<3828:R,R}
jfp{m>2899:A,s<2166:A,a>2436:A,R}
xj{s>2120:cfp,A}
gd{a>632:ldl,tdg}
pcn{m<1546:A,x>1253:R,A}
dx{s>656:fq,s>331:gd,x>3172:sf,hv}
xgf{s>890:A,s<559:bhd,a<1416:jc,A}
dm{a>2923:A,s>1340:R,R}
xhv{a>2829:A,x>2770:A,A}
nhn{m>404:cd,a>498:zvb,x<905:rk,zkf}
qc{x>1532:fh,x<640:R,vvj}
chk{s<556:A,a<589:A,A}
qn{m<580:A,s>182:A,R}
zxm{m<2637:R,A}
hdv{a<1798:R,R}
xtt{a>3840:R,m>3305:R,x<570:R,A}
zc{m<2975:R,s>1315:A,s>1205:R,R}
rnm{m>1407:R,m>749:A,R}
pmr{a<2467:R,R}
vqp{m>3399:pm,m<3046:qzt,cfb}
dg{x<1128:vkm,x>1519:sjn,x<1381:ccb,qsh}
rr{a<2507:R,R}
nnv{m<3547:R,A}
xnl{x>2643:R,s>1132:mhf,pkq}
nl{s<3397:A,a>827:A,A}
nn{a<3936:A,R}
qsd{a>1448:A,a>1405:qd,a<1376:bn,mv}
cfb{a>260:grt,rrr}
nbj{s>1938:js,x<3227:lkh,xgf}
ctf{a>2868:R,x<2217:lz,A}
gp{a<3836:gf,a>3927:kxf,x<1861:jl,gsv}
pxp{s<860:pks,a>389:R,gk}
vt{x>3144:kmx,m>1087:xhv,A}
mr{m>1876:zlg,s<1909:kfz,lpb}
cdr{s<3245:A,s>3283:A,A}
qjg{s<904:R,A}
rk{a>261:kjg,dqx}
fvt{a<565:R,R}
zn{x<3601:A,x>3785:A,R}
sjn{x<1774:R,mzh}
lpx{s>3591:A,A}
kl{a>744:mfg,s>938:rd,lll}
in{a>2109:vcp,nlb}
jqk{m<1618:rp,a>3744:R,a>3652:A,R}
dn{x>3357:A,m>1085:bgl,m<428:R,vx}
gk{a>143:A,A}
qdt{s>2577:R,R}
mx{s<1030:R,s>1210:R,x<1498:R,A}
fbc{m<1459:R,A}
nq{s<3163:R,R}
sfv{a>1532:R,s<1392:A,R}
vp{a>2517:R,x<3595:A,R}
dr{s<2481:R,R}
trn{x<1663:A,x>1701:R,a>3705:R,A}
hz{a<193:A,a>357:R,x>419:A,A}
tfn{x>1470:tdz,s>1837:dc,cls}
rp{s<1247:A,A}
cq{a<3822:A,m>3331:A,x<2698:R,A}
kmx{a<2840:A,s<871:R,A}
lvh{s>3146:fl,s>2549:gb,m<2163:kq,jzz}
tjf{s>3580:R,m<969:bd,a<378:gvd,qmp}
smq{a>2937:A,x<557:A,sbr}
fn{s<3006:R,a>3696:R,hp}
jm{x>2403:xcb,R}
tdl{m>3102:hfl,a>3838:R,m<2320:A,csq}
kf{a>3253:mr,dl}
rhv{x>3458:R,a>489:R,m<3072:R,R}
vsr{x<2152:gmb,a<109:sm,s>714:R,rtm}
rq{x>771:jbb,m>1626:R,a<3250:rxm,R}
nkl{a<2833:bbm,s<2359:bt,x<3256:A,A}
bbm{a<2779:R,A}
jgh{a>3666:A,R}
rmr{s>1583:zcr,a<2701:fp,a>2855:lq,cn}
gvb{s<3036:A,s>3512:A,a>1761:knl,A}
jc{s>731:A,a>1389:R,R}
ktb{a>3701:sc,A}
bs{x<1296:A,x>1870:R,s>1252:R,R}
tjg{s<152:R,R}
xcb{x<2488:R,s>1614:R,R}
gmr{s<837:A,A}
tdg{x<3221:R,A}
nrk{m<1592:A,a<876:R,R}
hfl{x>472:A,m<3449:A,s>2782:A,A}
fz{m<3538:A,R}
cjp{s<1572:A,s>1577:A,A}
cp{a>2941:R,x>1350:nbs,m>1179:A,R}
hcq{x<2133:A,R}
bc{s<2648:R,a>3738:A,m<651:A,R}
thl{m<1971:rmr,rfm}
pv{a<3874:R,a<3897:R,a<3916:R,R}
gsv{s>2955:nf,m>2104:mc,lm}
cjj{x<2974:A,R}
zh{a>2411:R,s>2017:R,x>1603:A,R}
cxb{x<980:rq,m>2634:jq,a<3209:tp,vnb}
tn{a>3678:A,x>3579:A,s<363:A,R}
np{x>2364:R,mjk}
bhd{x<3712:A,x>3816:A,R}
sx{x>3007:tn,x>2586:A,a>3697:ppb,A}
mld{a<1908:A,x>1026:A,A}
dvh{s<1790:A,m>2391:R,R}
vxf{x>1980:qrs,qh}
tp{s>2484:rdn,s<1600:xv,a<3130:A,fmm}
blt{s>581:hh,x>2883:zn,a<2727:R,hst}
sq{a>3747:A,s>160:A,A}
mc{m<3220:qq,A}
dc{a>506:R,s>1935:R,a>282:jtg,A}
mqn{s<982:mb,a<543:lln,x<1784:zj,zvs}
nx{m<1350:A,s<2994:R,s>3466:A,R}
rxm{x>702:R,A}
dnz{s<2734:A,m>1724:A,x<1743:A,R}
lln{x<2592:bs,s>1222:A,x>3139:R,A}
htp{s<2223:A,A}
qnv{x>1110:R,A}
nts{a<1737:nfr,a>1781:bqq,gvb}
kjg{s>727:A,A}
qhn{a<2683:gs,x>857:sgm,s<2204:smq,hvk}
kkn{x>2484:A,x>1526:R,s<1203:R,A}
mv{a<1387:A,a>1396:R,R}
dxr{s<2547:A,m<239:R,A}
bz{m<1172:R,x<1295:A,A}
pz{a>1750:qfh,s<1134:mtc,fnt}
pgd{s<2978:R,m<761:A,a<3791:A,A}
zph{a>143:dt,A}
kjd{x<2552:A,m>975:pmr,m>591:kz,nq}
zkf{x>1684:vv,m<148:R,m>283:xrq,A}
fhn{a<1083:A,a>1174:A,A}
zs{m<1284:bc,a<3720:xvr,A}
rcp{a<215:A,s<295:R,x<3424:A,A}
xmp{s>298:A,R}
gcq{s<184:R,m<3474:A,R}
thn{m<974:xhs,xzz}
zvs{s>1186:A,x<2678:R,A}
zb{x<587:A,a>1113:R,A}
lf{x>2395:R,s<3117:R,a>2855:mmv,A}
pcb{m<1631:cj,s>373:qdg,np}
nsm{a<1665:R,a>1683:R,m<2415:R,R}
msd{x<766:zd,a<857:xd,x>1084:bgg,mlq}
gc{m>2602:prd,s>712:nt,a>3842:pcb,qz}
pb{m<3227:A,A}
qrs{x>2813:R,R}
vdc{a>3064:R,a<3052:R,A}
zd{a<459:hz,m<2919:R,x<396:kvm,R}
rrr{m>3225:A,x>1941:R,R}
cpg{s>2251:mn,a>3868:R,x>1654:sct,R}
qq{s<2087:A,x<2128:R,R}
nqt{m>1360:A,s<259:R,A}
lff{x>3051:A,R}
hvk{a<2893:kbj,a<2975:R,R}
cn{x<2156:dp,a<2756:blt,a<2815:dn,vt}
jcx{m<2249:R,R}
qz{x>2042:sx,dzv}
dv{m>2906:R,A}
xvr{m<1712:R,m<2199:R,a>3630:A,R}
vvj{a>626:A,m>3772:R,R}
slm{m>2544:A,a<561:lhg,x>2768:R,R}
fnh{x>282:R,s>2545:R,R}
vdx{x>2982:llk,s>1644:bjj,m>760:tjr,fcg}
dvr{x>983:A,R}
vc{x<1716:A,x>2600:R,R}
rfm{x<1338:qhn,x<2547:bp,a>2742:hkn,nk}
qdp{a<1172:A,x>625:R,A}
kxf{a<3962:pr,a>3985:lvh,tq}
mn{a<3892:R,s>2616:A,R}
stn{m<380:R,R}
xk{s<1573:A,mld}
szp{s<1089:A,A}
rxs{x>2590:cjj,jm}
fsf{s>3134:R,m<1763:R,x>1531:A,R}
qt{x<3213:R,m>2684:zgb,dr}
jqh{m<1985:csn,x>2319:lff,a<1137:mhd,A}
mjk{a<3930:A,R}
mts{x<2623:A,m<2901:R,A}
ccb{s<1850:A,a>3517:R,a>3494:A,R}
gxb{s<3410:R,R}
kx{s>2771:R,A}
rd{m<3188:fsz,a<390:gcs,a<508:vf,lr}
bt{x>3490:R,A}
ldp{x>1916:fxs,a>1827:kdl,s<2119:pz,nts}
vtg{a>584:A,A}
ppb{x>2299:R,a<3758:R,x>2175:A,A}
xb{s<3080:R,cdr}
fq{m>586:vtg,x<2915:vpt,x>3365:R,R}
nh{m<1043:R,m>1679:A,A}
fml{x<1449:A,a<3496:R,R}
zns{m>1400:R,x>490:A,s<772:A,R}
gqr{a<3481:R,x>2644:xf,R}
sbr{x>681:R,a>2850:R,A}
tj{m<3462:A,s<854:ht,a<439:cg,hbl}
vhc{a>3741:pgd,x<2121:kbd,R}
rvd{m>2131:R,A}
mhf{a<1023:R,A}
ghm{s<547:A,x<1433:A,R}
gpk{x>736:A,m>1085:A,s>2929:R,A}
hcb{x>1982:R,A}
qfh{m>2590:pb,R}
jf{a<3619:R,gpk}
prd{s>884:txm,x<1386:xtt,s>320:bf,qjq}
gvd{a>189:R,s<3441:A,x>689:R,R}
ckb{a<1150:A,x<2820:A,a>1220:A,A}
jl{s<3142:cpg,fk}
vpt{a>647:A,s<967:A,m<233:R,R}
xjh{s>1442:cf,R}
pzz{a<2323:R,s<1766:R,zfx}
jmt{a>1538:R,a>1520:A,R}
zqk{a>2305:R,x<1647:A,R}
jhb{x<1923:dvr,vr}
hkz{x>1692:R,m>2936:R,R}
qjq{m<3081:mts,x<2588:A,vxt}
tc{s>363:R,x>3451:R,A}
txm{m<3425:lmt,a>3859:qzk,s>1229:ffh,xlt}
vf{s>1325:zt,a<459:qxp,ztc}
cjc{a<3486:R,R}
xzz{m<1968:R,zb}
fk{s<3595:R,a>3880:R,m>2234:dpc,qk}
vv{m>259:A,A}
dt{x>2999:R,R}
qx{x<1251:R,x<1426:A,A}
mg{a<1580:R,m<3092:R,R}
pqm{m>1841:R,x>1285:R,R}
mjc{s>2706:R,a>1090:A,m<3463:R,R}
pc{x>3414:A,R}
pj{m<3474:msv,R}
bp{a<2758:qvm,ls}
mzh{s>2401:R,A}
lvd{x<3054:R,pc}
nlb{a>1341:hds,s>1531:kp,m<2594:sbd,kl}
fp{a<2421:gzl,m>1241:xs,ll}
xht{x<2044:R,a<457:R,s>1422:R,R}
bn{x<1502:A,m>1464:A,s<2516:R,A}
czq{m>1778:A,m<852:R,a>108:R,R}
kgf{x>2766:A,s<3039:A,x<2332:R,R}
rtp{m<1323:A,A}
fl{m>1551:A,m>603:A,R}
zbz{m>743:qdt,kx}
hx{x<2647:R,A}
kj{s>2373:dfh,zgc}
lpb{a<3291:A,ktl}
vx{x>2870:R,A}
kd{x>2985:R,A}
hdf{x>1397:lqq,x>838:nrk,m>1599:pvl,xnk}
mm{m<1647:hzc,s>3570:slm,pkx}
nc{m<1563:A,A}
ztp{s>561:A,A}
fc{m<2662:A,s<3421:A,x<1851:R,A}
xlt{x>2359:A,s<1077:R,R}
bh{m<2423:A,m<3235:R,s<1041:A,R}
phm{a<332:R,s<2714:A,x<1986:R,A}
hnc{m>3552:A,s<291:R,R}
ck{s<1817:gqr,cjc}
qzt{s<351:A,x>1743:R,R}
mhk{a>3356:sgc,x<1442:mmb,kf}
qxd{a<319:kjt,mqn}
rdn{s<3250:R,s>3686:R,a<3137:R,A}
ldl{x<3386:R,s<503:R,s<559:R,R}
nxd{a>642:A,x>2020:R,m<2832:kjk,R}
xs{m>1501:ztp,x<2285:qnv,m<1392:rtp,qm}
lfh{a<3181:R,x<317:qfn,mh}
nfs{m>3081:R,s>3075:R,R}
qzk{s>1170:R,a>3922:R,s<1013:R,A}
kjk{a>615:A,A}
zgb{s>2356:R,A}
xtg{m<3019:A,x<2070:R,A}
gs{x>465:jfp,m<2818:khz,x>159:fnh,A}
xv{m<1340:A,R}
hg{x>1111:dvh,A}
tlz{m<678:pvt,R}
pf{a<616:tjf,bvk}
rds{a<3934:R,s>1706:R,A}
zlg{a<3293:A,spj}
fj{m<3682:A,R}
kb{m>837:R,s<3541:A,a>3755:R,R}
gx{m<3654:R,A}
xx{m<2874:R,s<3493:R,A}
nt{x<2262:crf,s<1134:jr,jqk}
rtm{x>3117:R,a<145:A,R}
hv{m<375:R,A}
gqv{a>3495:R,a<3483:A,R}
tjk{m<2047:A,a<3868:R,R}
qmp{m<1491:A,A}
lvp{s<583:R,A}
xm{m>1862:hdh,tlm}
lb{s<2443:A,s>2475:R,R}
cs{a<875:phm,m<2630:R,x<1434:mjc,R}
ttl{a<2664:A,R}
mhd{s<335:R,m>2228:R,R}
jr{s<887:npj,a<3860:A,A}
jkz{s<1554:R,a<2018:A,m>124:R,R}
sbd{a>849:gmz,m<1017:zcx,qxd}
flm{x>1515:sxg,s<2410:zr,a<519:hj,snn}
xn{s<502:R,A}
mtc{m>2603:A,A}
sct{m<1975:A,x<1764:A,R}
sjt{x<1458:A,A}
dp{s>781:A,A}
ht{s<827:A,m>3792:R,a>249:A,R}
vfm{s<1503:fbc,a<2999:A,s<1550:hcn,cjp}
pvl{s<2160:hb,a<550:R,s<2214:R,bx}
xf{m<2649:A,R}
lfz{s>2444:lfh,vz}
kjt{a>191:xmt,vsr}
bvk{a<1012:A,m<692:qdp,x<828:A,A}
zx{a>3417:jv,x>905:bmb,ztk}
lhg{x<2971:A,R}
bhb{m<1459:hx,jqh}
pdn{a<142:R,a>245:A,m<162:R,R}
cgs{x>1008:R,x>659:R,a>1042:A,R}
ktl{x<3130:A,A}
hkh{s>1119:zc,A}
fx{m<2849:A,R}
js{a<1401:R,m<2305:A,a>1458:kgf,A}
ksz{x>1432:R,x<597:R,xt}
tq{m<2066:kh,x>1854:bfg,a>3974:R,hkz}
rhr{m>411:A,R}
bf{x<2951:qfd,m>3214:mvh,bkz}
kpp{a>202:xnh,xmp}
tdz{a<613:A,m<1521:R,m>3019:R,cb}
cm{a<1725:R,x>1263:A,m<1064:A,R}
lkh{m>2307:hl,s>828:A,m>1005:A,stn}
tjr{s>787:R,R}
kbd{a>3682:R,x>2067:A,A}
bd{m>336:R,s<3461:A,x<628:A,A}
hb{x>555:A,x>283:R,a>865:A,R}
knl{m<1464:R,m>2404:R,x>1065:R,R}
krv{a>1949:ldh,A}
sf{m>414:fvt,tjg}
szr{m>1415:A,R}
cc{a>595:R,a<555:R,m<3273:skk,A}
bgg{s>3682:qx,x<1313:A,xx}
ls{m>3309:czz,gh}
zcr{a<2752:kjd,a>2951:zbz,m>913:lf,ctf}
hds{a>1629:ldp,x>2034:tf,sj}
nj{s<220:R,A}
kh{a>3975:R,a<3967:A,A}
jzz{s>2039:R,m>2936:R,s<1719:R,R}
sgc{x>1922:ck,a<3467:zx,dg}
bx{a<816:R,x<546:R,x<735:A,R}
lmz{x>2952:A,a<1706:A,R}
mlp{x>608:R,s>2626:kb,x<385:R,lc}
nnz{s>2964:R,R}
cv{a>3915:R,x<3153:cl,px}
qfn{s<3186:R,A}
jq{m>3243:gx,R}

{x=331,m=147,a=1060,s=2496}
{x=213,m=1052,a=2303,s=924}
{x=926,m=3270,a=388,s=103}
{x=661,m=2284,a=821,s=1473}
{x=1721,m=420,a=129,s=1038}
{x=979,m=1211,a=90,s=2527}
{x=1587,m=29,a=902,s=1225}
{x=262,m=196,a=529,s=1416}
{x=465,m=864,a=420,s=354}
{x=1523,m=3,a=459,s=730}
{x=734,m=1664,a=401,s=1583}
{x=275,m=36,a=3408,s=1106}
{x=832,m=639,a=989,s=280}
{x=86,m=1327,a=156,s=275}
{x=1837,m=1693,a=112,s=425}
{x=249,m=498,a=2132,s=949}
{x=1417,m=343,a=68,s=1482}
{x=735,m=344,a=36,s=2572}
{x=2528,m=933,a=12,s=2714}
{x=258,m=1163,a=3036,s=618}
{x=888,m=794,a=3331,s=64}
{x=2447,m=2496,a=2160,s=1699}
{x=5,m=92,a=1301,s=2059}
{x=373,m=361,a=74,s=1225}
{x=667,m=320,a=2059,s=1704}
{x=426,m=1546,a=997,s=3}
{x=1853,m=2468,a=788,s=2870}
{x=48,m=1736,a=85,s=1186}
{x=16,m=39,a=12,s=34}
{x=2103,m=328,a=589,s=525}
{x=2431,m=199,a=173,s=22}
{x=465,m=850,a=284,s=47}
{x=449,m=687,a=447,s=328}
{x=1199,m=261,a=1981,s=247}
{x=1372,m=2700,a=378,s=348}
{x=1846,m=1319,a=1476,s=129}
{x=268,m=330,a=2422,s=1169}
{x=152,m=827,a=1067,s=421}
{x=368,m=1213,a=1676,s=37}
{x=202,m=843,a=617,s=1443}
{x=126,m=848,a=798,s=728}
{x=270,m=653,a=1522,s=1920}
{x=847,m=2881,a=246,s=229}
{x=104,m=696,a=241,s=243}
{x=205,m=1148,a=593,s=1053}
{x=875,m=3045,a=796,s=3295}
{x=714,m=299,a=252,s=1061}
{x=400,m=2262,a=405,s=1089}
{x=603,m=115,a=90,s=210}
{x=183,m=814,a=1313,s=1173}
{x=3264,m=996,a=1050,s=2615}
{x=1002,m=1180,a=108,s=12}
{x=365,m=422,a=281,s=750}
{x=2685,m=387,a=124,s=1873}
{x=715,m=1319,a=1447,s=297}
{x=651,m=2515,a=2214,s=2330}
{x=2092,m=2133,a=741,s=925}
{x=470,m=1434,a=1519,s=1630}
{x=2270,m=2552,a=854,s=38}
{x=406,m=577,a=24,s=66}
{x=91,m=281,a=881,s=1279}
{x=8,m=394,a=1341,s=343}
{x=819,m=195,a=801,s=1395}
{x=787,m=1458,a=414,s=302}
{x=163,m=3523,a=1403,s=624}
{x=435,m=1768,a=446,s=2575}
{x=54,m=1228,a=456,s=602}
{x=2123,m=600,a=3065,s=346}
{x=2377,m=463,a=374,s=1842}
{x=438,m=242,a=850,s=97}
{x=1488,m=986,a=177,s=2693}
{x=2152,m=1794,a=999,s=85}
{x=559,m=631,a=1304,s=1876}
{x=682,m=386,a=799,s=1443}
{x=1614,m=58,a=1267,s=2171}
{x=692,m=667,a=19,s=55}
{x=7,m=1898,a=181,s=4}
{x=503,m=21,a=336,s=104}
{x=122,m=25,a=1224,s=2443}
{x=1491,m=2578,a=1097,s=1140}
{x=216,m=484,a=506,s=1229}
{x=1633,m=2731,a=2475,s=1446}
{x=2642,m=652,a=69,s=2916}
{x=35,m=44,a=1073,s=239}
{x=43,m=675,a=190,s=1010}
{x=1449,m=3268,a=937,s=248}
{x=1702,m=1062,a=3277,s=2834}
{x=100,m=526,a=729,s=552}
{x=211,m=3868,a=927,s=1189}
{x=598,m=938,a=1888,s=2460}
{x=369,m=3413,a=135,s=1201}
{x=842,m=2597,a=1389,s=1361}
{x=453,m=19,a=1529,s=302}
{x=945,m=664,a=961,s=2884}
{x=1358,m=1292,a=3217,s=1144}
{x=1235,m=8,a=450,s=1121}
{x=2448,m=1922,a=2421,s=133}
{x=890,m=617,a=1108,s=1041}
{x=1426,m=133,a=1714,s=109}
{x=1668,m=68,a=1533,s=291}
{x=1770,m=1114,a=315,s=292}
{x=270,m=426,a=753,s=1331}
{x=134,m=157,a=928,s=828}
{x=505,m=203,a=767,s=2189}
{x=1090,m=85,a=183,s=162}
{x=348,m=1133,a=1235,s=861}
{x=285,m=931,a=481,s=2}
{x=1329,m=2438,a=527,s=133}
{x=579,m=546,a=2583,s=355}
{x=1269,m=2111,a=308,s=682}
{x=3769,m=875,a=1827,s=794}
{x=57,m=232,a=627,s=436}
{x=350,m=1658,a=1508,s=96}
{x=1351,m=1794,a=139,s=575}
{x=1642,m=1829,a=607,s=298}
{x=36,m=291,a=1458,s=613}
{x=3321,m=385,a=837,s=1083}
{x=306,m=565,a=1974,s=774}
{x=210,m=33,a=989,s=504}
{x=1119,m=1332,a=125,s=1884}
{x=927,m=2761,a=702,s=1671}
{x=19,m=475,a=741,s=2936}
{x=239,m=1711,a=2489,s=1749}
{x=24,m=3109,a=379,s=1106}
{x=145,m=787,a=2142,s=1437}
{x=1455,m=826,a=199,s=635}
{x=2061,m=791,a=2550,s=195}
{x=443,m=1094,a=565,s=1180}
{x=1475,m=79,a=1253,s=7}
{x=1808,m=641,a=32,s=1230}
{x=1192,m=235,a=2179,s=993}
{x=2194,m=1318,a=541,s=2111}
{x=1830,m=3434,a=434,s=193}
{x=523,m=981,a=39,s=1996}
{x=1012,m=546,a=86,s=88}
{x=1141,m=66,a=2979,s=1790}
{x=14,m=659,a=1290,s=1204}
{x=2285,m=76,a=1077,s=1495}
{x=11,m=496,a=994,s=11}
{x=182,m=567,a=90,s=278}
{x=973,m=1938,a=1231,s=136}
{x=1268,m=252,a=1892,s=457}
{x=1914,m=791,a=704,s=551}
{x=2241,m=8,a=315,s=119}
{x=228,m=53,a=416,s=971}
{x=299,m=2378,a=166,s=975}
{x=702,m=1229,a=1482,s=445}
{x=1418,m=2816,a=3145,s=135}
{x=298,m=382,a=912,s=1311}
{x=601,m=563,a=954,s=90}
{x=2152,m=683,a=922,s=681}
{x=200,m=1190,a=61,s=1069}
{x=714,m=22,a=413,s=1150}
{x=524,m=1450,a=808,s=994}
{x=432,m=76,a=2194,s=1267}
{x=145,m=227,a=453,s=2393}
{x=267,m=355,a=681,s=1050}
{x=2088,m=3514,a=2760,s=924}
{x=1003,m=508,a=25,s=732}
{x=1558,m=1229,a=448,s=2079}
{x=1405,m=2090,a=160,s=1242}
{x=460,m=267,a=406,s=2154}
{x=615,m=311,a=1557,s=2855}
{x=6,m=856,a=615,s=2067}
{x=1096,m=1381,a=143,s=851}
{x=2678,m=420,a=773,s=458}
{x=564,m=2174,a=980,s=41}
{x=649,m=2402,a=769,s=1813}
{x=882,m=679,a=1686,s=475}
{x=7,m=208,a=861,s=3390}
{x=1612,m=598,a=1602,s=947}
{x=1221,m=1209,a=292,s=1390}
{x=475,m=1234,a=982,s=667}
{x=41,m=1407,a=117,s=2913}
{x=2935,m=465,a=250,s=736}
{x=1950,m=1251,a=1489,s=619}
{x=312,m=2153,a=1610,s=1076}
{x=348,m=2053,a=518,s=43}
{x=991,m=2614,a=1301,s=799}
{x=1129,m=2899,a=2560,s=1889}
{x=427,m=260,a=408,s=2}
{x=1333,m=33,a=43,s=1948}
{x=596,m=477,a=1819,s=2788}
{x=972,m=1118,a=2401,s=354}
{x=2991,m=2658,a=127,s=2118}
{x=799,m=642,a=557,s=301}
{x=692,m=1197,a=1590,s=1491}
{x=848,m=303,a=228,s=732}
{x=525,m=152,a=590,s=366}
{x=446,m=952,a=919,s=841}
{x=39,m=3190,a=656,s=179}
{x=1685,m=430,a=239,s=3}
{x=310,m=778,a=452,s=605}
{x=69,m=890,a=4,s=143}
{x=2089,m=125,a=1382,s=1480}
{x=1279,m=717,a=209,s=1458}
{x=1091,m=51,a=100,s=1488}
{x=822,m=34,a=1002,s=819}
{x=2761,m=2020,a=2022,s=33}
{x=2927,m=900,a=112,s=880}
stdout
476889