Boolean Expression Compressor

source: ACM International Collegiate Programming Contest, Japan Domestic 2017

raw_problem:
Boolean Expression Compressor

You are asked to build a compressor for Boolean expressions
that transforms expressions to the shortest form keeping their meaning.

The grammar of the Boolean expressions has terminals
<tt>0</tt> <tt>1</tt> <tt>a</tt> <tt>b</tt> <tt>c</tt> <tt>d</tt> <tt>-</tt> <tt>^</tt> <tt>*</tt> <tt>(</tt> <tt>)</tt>, start symbol <E> and the following production rule:

<E>  ::=  <tt>0</tt>  |  <tt>1</tt>  |  <tt>a</tt>  |  <tt>b</tt>  |  <tt>c</tt>  |  <tt>d</tt>  |  <tt>-</tt><E>  |  <tt>(</tt><E><tt>^</tt><E><tt>)</tt>  |  <tt>(</tt><E><tt>*</tt><E><tt>)</tt>

Letters <tt>a</tt>, <tt>b</tt>, <tt>c</tt> and <tt>d</tt> represent Boolean
variables that have values of either  <tt>0</tt> or <tt>1</tt>.
Operators are evaluated as shown in the Table below.
In other words, <tt>-</tt> means negation (NOT),
<tt>^</tt> means exclusive disjunction (XOR), and
<tt>*</tt> means logical conjunction (AND).

Table: Evaluations of operators

Write a program that calculates the length of the shortest expression that
evaluates equal to the given expression with whatever values of the four variables.

For example, <tt>0</tt>, that is the first expression in the sample input,
cannot be shortened further.
Therefore the shortest length for this expression is 1.

For another example, <tt>(a*(1*b))</tt>, the second in the sample input,
always evaluates equal to <tt>(a*b)</tt> and <tt>(b*a)</tt>,
which are the shortest.   The output for this expression, thus, should be <tt>5</tt>.

Input

The input consists of multiple datasets.
A dataset consists of one line, containing an expression
conforming to the grammar described above.
The length of the expression is less than or equal to 16 characters.

The end of the input is indicated by a line containing one
<tt>.</tt> (period).
The number of datasets in the input is at most 200.

Output

For each dataset,
output a single line containing an integer which is the length of the
shortest expression that has the same value as the given expression for
all combinations of values in the variables.

Sample Input

0
(a*(1*b))
(1^a)
(-(-a*-b)*a)
(a^(b^(c^d)))
.

Output for the Sample Input

1
5
2
1
13

solutions: ["a=65280; b=61680; c=52428; d=43690; e=65535\nfrom heapq import heappush, heappop\nQ = [(1, a), (1, b), (1, c), (1, d)]\nL = {a: 1, b: 1, c: 1, d: 1, e: 1, e: 1, 0: 1}\nH = []\nget = L.get\npush = H.append\nwhile Q:\n    l, p = heappop(Q)\n    if L[p] < l: continue\n    if l+1 < get(p ^ e, 17):\n        L[p ^ e] = l+1\n        l < 15 and heappush(Q, (l+1, p ^ e))\n    if l < 13:\n        li = 13-l; l3 = 3+l\n        for q, r in H:\n            if r <= li:\n                k = p & q\n                if r < get(k, 17)-l3:\n                    L[k] = l3+r\n                    r < li and heappush(Q, (l3+r, k))\n                k = p ^ q\n                if r < get(k, 17)-l3:\n                    L[k] = l3+r\n                    r < li and heappush(Q, (l3+r, k))\n            else: break\n    if l < 7: push((p, l))\nprint(*map(L.__getitem__, eval(\"e&\"+\",e&\".join(open(0).read().replace(*\"-~\").replace(*\"*&\").replace(*\"1e\").split()[:-1]))),sep='\\n')\n", "a = b = c = d = 0\ndef expr():\n    global a, b, c, d, index\n    if s[index] == '0':\n        index += 1\n        return 0\n    elif s[index] == '1':\n        index += 1\n        return 1\n    elif s[index].isalpha():\n        ch = s[index]\n        index += 1\n        return eval(ch)\n    elif s[index] == '-':\n        index += 1\n        return 1 - expr()\n    elif s[index] == '(':\n        index += 1\n        t1 = expr()\n        ope = s[index]\n        index += 1\n        t2 = expr()\n        index += 1\n        return eval(f'{t1}' + ope + f'{t2}')\n\ndef truthtable():\n    global a, b, c, d, index\n    ans = []\n    for a in range(2):\n        for b in range(2):\n            for c in range(2):\n                for d in range(2):\n                    index = 0\n                    ans.append(expr())\n    return int(''.join(map(str, ans)), 2)\n\nindex = 0\n    \ndp = [set() for _ in range(17)]\ndp[1] = {0, 255, 3855, 13107, 21845, 65535}\ntable2length = [17] * 65536\nfor t in dp[1]:\n    table2length[t] = 1\nfor l in range(1, 17):\n    # -\n    for t in dp[l - 1]:\n        newt = t ^ 65535\n        if table2length[newt] > l:\n            table2length[newt] = l\n            dp[l].add(newt)\n    # *\n    for l1 in range(l):\n        l2 = l - l1 - 3\n        if not (l1 > 0 and l2 > 0):\n            continue\n        for t1 in dp[l1]:\n            for t2 in dp[l2]:\n                newt = t1 & t2\n                if table2length[newt] > l:\n                    table2length[newt] = l\n                    dp[l].add(newt)\n                newt = t1 ^ t2\n                if table2length[newt] > l:\n                    table2length[newt] = l\n                    dp[l].add(newt)\n\n# print(table2length[:100])\n\n\nfor _ in range(210):\n    s = input()\n    if s == '.':\n        exit()\n    print(table2length[truthtable()])\n", "def number(s):\n  global i\n  res=s[i]\n  i+=1\n  return int(res)\n\ndef expr(s):\n  global i\n  res=term(s)\n  while i<len(s):\n    if s[i]=='*':\n      i+=1\n      res*=term(s)\n    elif s[i]=='^':\n      i+=1\n      res^=term(s)\n    else:\n      break\n  return res\n\ndef term(s):\n  global i\n  c=0\n  while s[i]=='-':\n    i+=1\n    c^=1\n  return factor(s)^c\n\ndef factor(s):\n  global i\n  if s[i]=='(':\n    i+=1\n    res=expr(s)\n    if s[i]==')':\n      i+=1\n    return res\n  return number(s)\n\n\n\nzero =0b0000000000000000\none  =0b1111111111111111\na    =0b1111111100000000\nb    =0b1111000011110000\nc    =0b1100110011001100\nd    =0b1010101010101010\n\ncost=[1<<30]*(1<<16)\ncost[zero]=1\ncost[one]=1\ncost[a]=1\ncost[b]=1\ncost[c]=1\ncost[d]=1\n\nmask=(1<<16)-1\nmemo=[[] for i in range(20)]\nfor i in range(1,20):\n  for x in memo[i-1]:\n    cost[mask-x]=min(cost[mask-x],i)\n  for w1 in range(i-3):\n    w2=i-3-w1\n    for x in memo[w1]:\n      for y in memo[w2]:\n        cost[x^y]=min(cost[x^y],i)\n        cost[x&y]=min(cost[x&y],i)\n  for j in range(1<<16):\n    if cost[j]==i:\n      memo[i].append(j)\n\n  \nwhile True:\n  x=input()\n  if x=='.':\n    exit()\n  ans=[0]*(1<<4)\n  for bit in range(1<<4):\n    d={}\n    for i in range(4):\n      if (bit>>i)&1:\n        d['abcd'[i]]='1'\n      else:\n        d['abcd'[i]]='0'\n    s=''\n    for i in x:\n      if i in 'abcd':\n        s+=d[i]\n      else:\n        s+=i\n    i=0\n    ans[bit]=expr(s)\n  \n  res=0\n  for i in range(16):\n    if ans[i]:\n      res|=1<<i\n  print(cost[res])\n", "#!/usr/bin/env python3\n# -*- coding: utf-8 -*-\nimport itertools\n\ndef rdp_resolve(e: str) -> int:\n    def evaluate() -> int:\n        nonlocal p\n        if e[p] in env:\n            p += 1\n            return env[e[p - 1]]\n        if e[p] == '-':\n            p += 1\n            return 1 - evaluate()\n        p += 1\n        lval = evaluate()\n        op = e[p]\n        p += 1\n        rval = evaluate()\n        p += 1\n        if op == '^':\n            return lval ^ rval\n        else:\n            return lval & rval\n    res = 0\n    env = {\"0\": 0, \"1\": 1}\n    for a, b, c, d in itertools.product(range(2), range(2), range(2), range(2)):\n        env.update({\"a\": a, \"b\": b, \"c\": c, \"d\": d})\n        p = 0\n        res = (res << 1) | evaluate()\n    return res\n\ndef rdp_init() -> None:\n    global rdp_sessions\n    rdp_sessions = dict()\n    rookies = dict()\n    for ch in \"01abcd\":\n        rookies[rdp_resolve(ch)] = 1\n    while rookies:\n        rdp_sessions.update(rookies)\n        entries = dict()\n        for k, v in rookies.items():\n            candidate = 0xFFFF - k\n            weight = v + 1\n            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):\n                entries[candidate] = weight\n        for (k1, v1), (k2, v2) in itertools.product(rookies.items(), rdp_sessions.items()):\n            candidate = k1 ^ k2\n            weight = v1 + v2 + 3\n            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):\n                entries[candidate] = weight\n            candidate = k1 & k2\n            weight = v1 + v2 + 3\n            if weight <= 16 and weight <= rdp_sessions.get(candidate, 16) and weight <= entries.get(candidate, 16):\n                entries[candidate] = weight\n        rookies = entries\n\n        \nif __name__ == '__main__':\n    rdp_init()\n    while True:\n        line = input()\n        if line == '.':\n            break\n        print(rdp_sessions[rdp_resolve(line)])\n", "import heapq\nimport itertools\ndef evaluate(S,seq):\n    a,b,c,d=seq\n    return eval(S.replace(\"-\",\"-~-\").replace(\"*\",\"&\"))\ndef sikidata(S):\n    res=0\n    for seq in itertools.product(range(2),repeat=4):\n        tmp=seq[0]+seq[1]*2+seq[2]*4+seq[3]*8\n        if evaluate(S,seq):\n            res+=(1<<tmp)\n    return res\nans=[17 for i in range(65536)]\nq=[]\nX=[(1,\"0\"),(1,\"1\"),(1,\"a\"),(1,\"b\"),(1,\"c\"),(1,\"d\")]\nsiki={}\nfor t in X:\n    heapq.heappush(q,t)\n    ans[sikidata(t[1])]=t[0]\n    siki[t[0]]=t[1]\nkitei=[]\nwhile(q):\n    #print(len(kitei),len(q))\n    len1,siki1=heapq.heappop(q)\n    sikiid1=sikidata(siki1)\n    if ans[sikiid1]<len1:\n        continue\n    kitei.append((len1,siki1))\n    sikilist=[]\n    if siki1[0]!=\"-\":\n        sikilist.append(\"-\"+siki1)\n    for len2,siki2 in kitei:\n        sikilist.append(\"(\"+siki1+\"*\"+siki2+\")\")\n        sikilist.append(\"(\"+siki1+\"^\"+siki2+\")\")\n    for siki3 in sikilist:\n        if len(siki3)>17:\n            continue\n        sikiid3=sikidata(siki3)\n        if ans[sikiid3]>len(siki3):\n            ans[sikiid3]=len(siki3)\n            siki[sikiid3]=siki3\n            heapq.heappush(q,(len(siki3),siki3))\n\n\n#print(len(siki))\nwhile(True):\n    S=input()\n    if S==\".\":\n        break\n    print(ans[sikidata(S)])\n\n\n\n", "import heapq\nimport itertools\ndef evaluate(siki):\n    return lambda a,b,c,d:eval(siki.replace(\"-\",\"-~\"))%2\ndef changenum(siki):\n    res=0\n    for seq in itertools.product(range(2),repeat=4):\n        a,b,c,d=seq\n        if evaluate(siki)(a,b,c,d)==1:\n            res+=2**(a+2*b+4*c+8*d)\n    return res\nD=dict()\ndef dget(m):\n    if m in D:\n        return D[m]\n    else:\n        return 17\nq=[]\nheapq.heappush(q,(1,changenum(\"a\")))\nheapq.heappush(q,(1,changenum(\"b\")))\nheapq.heappush(q,(1,changenum(\"c\")))\nheapq.heappush(q,(1,changenum(\"d\")))\nheapq.heappush(q,(1,changenum(\"0\")))\nheapq.heappush(q,(1,changenum(\"1\")))\nD[changenum(\"a\")]=1\nD[changenum(\"b\")]=1\nD[changenum(\"c\")]=1\nD[changenum(\"d\")]=1\nD[changenum(\"0\")]=1\nD[changenum(\"1\")]=1\nwhile(len(q)>0):\n    le,n=heapq.heappop(q)\n    #print(le,n,dget(240),dget(255))\n    if D[n]<le:\n        continue\n    D[n]=min(D[n],le)\n    cost=1\n    if dget(65535^n)>D[n]+cost and D[n]+cost<=16:\n        D[65535^n]=D[n]+cost\n        heapq.heappush(q,(D[65535^n],65535^n))\n    tmp=dict()\n    for k in D:\n        if dget(n^k)>D[n]+D[k]+3 and D[n]+D[k]+3<=16:\n            tmp[n^k]=D[n]+D[k]+3\n            heapq.heappush(q,(tmp[n^k],n^k))\n        if dget(n&k)>D[n]+D[k]+3 and D[n]+D[k]+3<=16:\n            tmp[n&k]=D[n]+D[k]+3\n            heapq.heappush(q,(tmp[n&k],n&k))\n    for k in tmp:\n        D[k]=tmp[k]\nwhile(True):\n    S=input()\n    if S==\".\":\n        break\n    print(D[changenum(S)])\n\n", "import sys\ntry:\n    import os\n    f = open('input.txt', 'r')\n    sys.stdin = f\nexcept FileNotFoundError:\n    None\nfrom math import sqrt, ceil\nfrom collections import deque, Counter, defaultdict\n# defaultdict(int)\ninput=lambda: sys.stdin.readline().strip()\nsys.setrecursionlimit(11451419)\nfrom decimal import ROUND_HALF_UP,Decimal  #\u5909\u63db\u5f8c\u306e\u672b\u5c3e\u6841\u30920\u30840.01\u3067\u6307\u5b9a\n  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))\nfrom functools import lru_cache\nfrom bisect import bisect_left as bileft, bisect_right as biright\nfrom fractions import Fraction as frac  #frac(a,b)\u3067\u6b63\u78ba\u306aa/b\n# @lru_cache(maxsize=10**10)\n#######\u3053\u3053\u307e\u3067\u30c6\u30f3\u30d7\u30ec#######\n#\u30bd\u30fc\u30c8\u3001\"a\"+\"b\"\u3001\u518d\u5e30\u306a\u3089Python3\u306e\u65b9\u304c\u3044\u3044\n#######\u3053\u3053\u304b\u3089\u5929\u3077\u3089########\n\nO=  0b1111111111111111\nA=  0b1111111100000000\nB=  0b1111000011110000\nC=  0b1100110011001100\nD=  0b1010101010101010\n\nif 1:\n    ddd={0: 1, 2: 16, 3: 12, 4: 16, 5: 12, 6: 15, 7: 16, 8: 15, 9: 16, 10: 11, 12: 11, 15: 7, 16: 16, 17: 12, 18: 15, 19: 16, 20: 15, 21: 16, 32: 15, 33: 16, 34: 11, 40: 14, 42: 15, 45: 16, 48: 11, 51: 7, 57: 16, 60: 10, 63: 11, 64: 15, 65: 16, 68: 11, 72: 14, 75: 16, 76: 15, 80: 11, 85: 7, 89: 16, 90: 10, 95: 11, 96: 14, 99: 16, 101: 16, 102: 10, 105: 15, 106: 14, 108: 14, 111: 16, 112: 15, 119: 11, 120: 14, 123: 16, 125: 16, 127: 15, 128: 14, 130: 15, 132: 15, 135: 15, 136: 10, 138: 16, 140: 16, 143: 16, 144: 15, 147: 15, 149: 15, 150: 14, 153: 11, 154: 15, 156: 15, 159: 15, 160: 10, 162: 16, 165: 11, 166: 15, 169: 16, 170: 6, 175: 12, 176: 16, 179: 16, 180: 15, 183: 15, 187: 12, 191: 16, 192: 10, 195: 11, 196: 16, 198: 15, 201: 16, 204: 6, 207: 12, 208: 16, 210: 15, 213: 16, 215: 15, 221: 12, 223: 16, 225: 16, 235: 16, 237: 16, 238: 13, 240: 6, 243: 12, 245: 12, 247: 16, 249: 16, 250: 13, 252: 13, 255: 2, 256: 16, 257: 12, 258: 15, 259: 16, 260: 15, 261: 16, 272: 15, 273: 16, 512: 15, 513: 16, 514: 11, 520: 14, 522: 15, 525: 16, 544: 14, 546: 15, 561: 16, 680: 16, 765: 16, 768: 11, 771: 7, 777: 16, 780: 10, 783: 11, 801: 16, 816: 10, 819: 11, 937: 16, 960: 13, 963: 15, 972: 14, 975: 14, 1008: 14, 1011: 14, 1020: 12, 1023: 13, 1024: 15, 1025: 16, 1028: 11, 1032: 14, 1035: 16, 1036: 15, 1088: 14, 1092: 15, 1105: 16, 1224: 16, 1275: 16, 1280: 11, 1285: 7, 1289: 16, 1290: 10, 1295: 11, 1345: 16, 1360: 10, 1365: 11, 1440: 13, 1445: 15, 1450: 14, 1455: 14, 1481: 16, 1520: 14, 1525: 14, 1530: 12, 1535: 13, 1536: 14, 1539: 16, 1541: 16, 1542: 10, 1545: 15, 1546: 14, 1548: 14, 1551: 16, 1632: 13, 1638: 14, 1785: 15, 1791: 16, 1792: 15, 1799: 11, 1800: 14, 1803: 16, 1805: 16, 1807: 15, 1904: 14, 1911: 15, 2040: 16, 2048: 14, 2050: 15, 2052: 15, 2055: 15, 2056: 10, 2058: 16, 2060: 16, 2063: 16, 2176: 13, 2184: 14, 2210: 15, 2218: 16, 2244: 15, 2252: 16, 2295: 15, 2303: 16, 2304: 15, 2307: 15, 2309: 15, 2310: 14, 2313: 11, 2314: 15, 2316: 15, 2319: 15, 2448: 14, 2457: 15, 2550: 16, 2560: 10, 2562: 16, 2565: 11, 2566: 15, 2569: 16, 2570: 6, 2575: 12, 2600: 16, 2617: 16, 2640: 13, 2645: 15, 2650: 14, 2655: 14, 2690: 15, 2698: 16, 2720: 9, 2730: 10, 2758: 15, 2800: 15, 2805: 11, 2810: 14, 2815: 12, 2816: 16, 2819: 16, 2820: 15, 2823: 15, 2827: 12, 2831: 16, 2992: 15, 3003: 16, 3072: 10, 3075: 11, 3076: 16, 3078: 15, 3081: 16, 3084: 6, 3087: 12, 3120: 13, 3123: 15, 3132: 14, 3135: 14, 3144: 16, 3161: 16, 3204: 15, 3212: 16, 3238: 15, 3264: 9, 3276: 10, 3312: 15, 3315: 11, 3324: 14, 3327: 12, 3328: 16, 3330: 15, 3333: 16, 3335: 15, 3341: 12, 3343: 16, 3536: 15, 3549: 16, 3585: 16, 3595: 16, 3597: 16, 3598: 13, 3808: 16, 3840: 6, 3843: 12, 3845: 12, 3847: 16, 3849: 16, 3850: 13, 3852: 13, 3855: 2, 3885: 16, 3888: 14, 3891: 14, 3900: 12, 3903: 13, 3915: 16, 3920: 14, 3925: 14, 3930: 12, 3935: 13, 3945: 15, 3951: 16, 3960: 16, 3975: 15, 3983: 16, 3990: 16, 4000: 15, 4005: 11, 4010: 14, 4015: 12, 4032: 15, 4035: 11, 4044: 14, 4047: 12, 4080: 5, 4095: 6, 4096: 15, 4097: 16, 4112: 11, 4128: 14, 4131: 16, 4144: 15, 4160: 14, 4165: 16, 4176: 15, 4320: 16, 4335: 16, 4352: 11, 4369: 7, 4385: 16, 4386: 10, 4403: 11, 4417: 16, 4420: 10, 4437: 11, 4488: 13, 4505: 15, 4522: 14, 4539: 14, 4556: 14, 4573: 14, 4577: 16, 4590: 12, 4607: 13, 4608: 14, 4611: 16, 4625: 16, 4626: 10, 4641: 15, 4642: 14, 4656: 14, 4659: 16, 4680: 13, 4698: 14, 4845: 15, 4863: 16, 4864: 15, 4883: 11, 4896: 14, 4899: 16, 4913: 16, 4915: 15, 4940: 14, 4959: 15, 5100: 16, 5120: 14, 5125: 16, 5137: 16, 5140: 10, 5160: 13, 5180: 14, 5185: 15, 5188: 14, 5200: 14, 5205: 16, 5355: 15, 5375: 16, 5376: 15, 5397: 11, 5418: 14, 5439: 15, 5440: 14, 5445: 16, 5457: 16, 5461: 15, 5610: 16, 6168: 13, 6425: 15, 6682: 14, 6939: 14, 7196: 14, 7453: 14, 7680: 16, 7695: 16, 7697: 16, 7710: 12, 7725: 15, 7740: 16, 7755: 15, 7770: 16, 7905: 15, 7918: 16, 7920: 16, 7935: 16, 7967: 13, 7983: 16, 8015: 16, 8160: 16, 8175: 16, 8192: 14, 8194: 15, 8208: 15, 8211: 15, 8224: 10, 8226: 16, 8240: 16, 8243: 16, 8320: 13, 8330: 15, 8352: 14, 8362: 16, 8400: 15, 8415: 15, 8432: 16, 8447: 16, 8448: 15, 8451: 15, 8465: 15, 8466: 14, 8481: 11, 8482: 15, 8496: 15, 8499: 15, 8580: 14, 8613: 15, 8670: 16, 8704: 10, 8706: 16, 8721: 11, 8722: 15, 8737: 16, 8738: 6, 8744: 16, 8749: 16, 8755: 12, 8772: 13, 8789: 15, 8806: 14, 8823: 14, 8834: 15, 8840: 9, 8866: 16, 8874: 10, 8908: 15, 8914: 15, 8925: 11, 8942: 14, 8959: 12, 8960: 16, 8963: 16, 8976: 15, 8979: 15, 8995: 12, 9011: 16, 9100: 15, 9135: 16, 9252: 13, 9509: 15, 9766: 14, 10023: 14, 10240: 13, 10250: 15, 10260: 14, 10274: 15, 10280: 9, 10300: 15, 10370: 14, 10376: 13, 10400: 13, 10410: 15, 10455: 14, 10495: 15, 10752: 14, 10762: 16, 10773: 15, 10786: 16, 10794: 10, 10815: 16, 10880: 13, 10890: 15, 10914: 15, 10922: 14, 10965: 15, 11007: 16, 11308: 15, 11520: 15, 11535: 15, 11550: 16, 11554: 15, 11565: 11, 11655: 14, 11685: 15, 11730: 14, 11741: 15, 11760: 15, 11775: 15, 11822: 14, 12032: 16, 12047: 16, 12079: 12, 12175: 15, 12207: 16, 12240: 15, 12255: 15, 12287: 16, 12288: 10, 12291: 11, 12300: 13, 12303: 15, 12304: 16, 12306: 15, 12321: 16, 12336: 6, 12339: 12, 12348: 14, 12351: 14, 12384: 16, 12389: 16, 12432: 15, 12442: 15, 12464: 16, 12480: 9, 12492: 15, 12495: 11, 12528: 10, 12540: 14, 12543: 12, 12544: 16, 12546: 15, 12561: 16, 12563: 15, 12593: 12, 12595: 16, 12740: 15, 12789: 16, 12801: 16, 12835: 16, 12849: 16, 12850: 13, 13000: 16, 13056: 6, 13059: 12, 13068: 14, 13071: 14, 13073: 12, 13075: 16, 13089: 16, 13090: 13, 13104: 13, 13107: 2, 13113: 16, 13116: 12, 13119: 13, 13124: 14, 13141: 14, 13155: 16, 13158: 12, 13161: 15, 13164: 16, 13175: 13, 13179: 16, 13192: 15, 13203: 15, 13206: 16, 13209: 11, 13226: 14, 13235: 16, 13243: 12, 13248: 15, 13251: 11, 13260: 5, 13296: 14, 13299: 12, 13311: 6, 13364: 14, 13621: 14, 13824: 16, 13829: 16, 13875: 16, 13878: 12, 13881: 15, 13884: 16, 13923: 15, 13926: 16, 14025: 15, 14028: 16, 14074: 16, 14079: 16, 14135: 13, 14139: 16, 14195: 16, 14280: 16, 14331: 16, 14392: 15, 14592: 15, 14602: 15, 14643: 15, 14646: 16, 14649: 11, 14739: 14, 14745: 15, 14790: 14, 14796: 15, 14837: 15, 14847: 15, 14906: 14, 15104: 16, 15155: 16, 15163: 12, 15283: 15, 15291: 16, 15300: 15, 15351: 15, 15359: 16, 15360: 9, 15372: 15, 15375: 11, 15380: 15, 15400: 16, 15408: 15, 15411: 11, 15420: 5, 15465: 15, 15468: 16, 15480: 16, 15510: 14, 15516: 15, 15540: 15, 15555: 10, 15564: 9, 15600: 9, 15612: 15, 15615: 11, 16128: 10, 16140: 14, 16143: 12, 16149: 16, 16176: 14, 16179: 12, 16191: 6, 16234: 16, 16239: 16, 16251: 16, 16277: 15, 16287: 15, 16311: 15, 16319: 16, 16320: 9, 16332: 15, 16335: 11, 16368: 15, 16371: 11, 16380: 16, 16383: 10, 16384: 14, 16388: 15, 16400: 15, 16405: 15, 16448: 10, 16452: 16, 16464: 16, 16469: 16, 16512: 13, 16524: 15, 16560: 15, 16575: 15, 16576: 14, 16588: 16, 16624: 16, 16639: 16, 16640: 15, 16645: 15, 16657: 15, 16660: 14, 16705: 11, 16708: 15, 16720: 15, 16725: 15, 16770: 14, 16830: 16, 16835: 15, 16962: 13, 17219: 15, 17408: 10, 17412: 16, 17425: 11, 17428: 15, 17442: 13, 17459: 15, 17473: 16, 17476: 6, 17480: 16, 17483: 16, 17493: 12, 17510: 14, 17527: 14, 17540: 15, 17544: 9, 17578: 15, 17588: 15, 17595: 11, 17604: 16, 17612: 10, 17646: 14, 17663: 12, 17664: 16, 17669: 16, 17680: 15, 17685: 15, 17733: 12, 17749: 16, 17802: 15, 17871: 16, 17990: 14, 18247: 14, 18432: 13, 18444: 15, 18450: 14, 18500: 15, 18504: 9, 18522: 15, 18564: 14, 18568: 13, 18615: 14, 18624: 13, 18636: 15, 18687: 15, 19018: 15, 19200: 15, 19215: 15, 19230: 16, 19268: 15, 19275: 11, 19335: 14, 19380: 14, 19387: 15, 19395: 15, 19440: 15, 19455: 15, 19456: 14, 19468: 16, 19475: 15, 19524: 16, 19532: 10, 19551: 16, 19584: 13, 19596: 15, 19635: 15, 19652: 15, 19660: 14, 19711: 16, 20046: 14, 20224: 16, 20239: 16, 20303: 12, 20367: 15, 20400: 15, 20415: 15, 20431: 16, 20479: 16, 20480: 10, 20485: 11, 20490: 13, 20495: 15, 20496: 16, 20500: 15, 20545: 16, 20560: 6, 20565: 12, 20570: 14, 20575: 14, 20576: 16, 20579: 16, 20624: 15, 20636: 15, 20640: 9, 20650: 15, 20655: 11, 20688: 16, 20720: 10, 20730: 14, 20735: 12, 20736: 16, 20740: 15, 20753: 16, 20757: 15, 20817: 12, 20821: 16, 20898: 15, 20979: 16, 21074: 14, 21331: 14, 21505: 16, 21573: 16, 21585: 16, 21588: 13, 21672: 16, 21760: 6, 21765: 12, 21770: 14, 21775: 14, 21777: 12, 21781: 16, 21794: 14, 21811: 14, 21825: 16, 21828: 13, 21840: 13, 21845: 2, 21849: 16, 21850: 12, 21855: 13, 21861: 16, 21862: 12, 21865: 15, 21866: 16, 21879: 13, 21885: 16, 21896: 15, 21909: 15, 21910: 16, 21913: 11, 21920: 15, 21925: 11, 21930: 5, 21964: 14, 21973: 16, 21981: 12, 22000: 14, 22005: 12, 22015: 6, 22016: 16, 22019: 16, 22101: 16, 22102: 12, 22105: 15, 22106: 16, 22117: 15, 22118: 16, 22185: 15, 22186: 16, 22268: 16, 22271: 16, 22359: 13, 22365: 16, 22389: 16, 22440: 16, 22525: 16, 22616: 15, 22784: 15, 22796: 15, 22869: 15, 22870: 16, 22873: 11, 22933: 14, 22937: 15, 22950: 14, 22954: 15, 23027: 15, 23039: 15, 23040: 9, 23050: 15, 23055: 11, 23058: 15, 23112: 16, 23120: 15, 23125: 11, 23130: 5, 23145: 15, 23146: 16, 23160: 16, 23190: 14, 23194: 15, 23205: 10, 23210: 9, 23250: 15, 23280: 9, 23290: 15, 23295: 11, 23644: 14, 23808: 16, 23893: 16, 23901: 12, 23970: 15, 24021: 15, 24029: 16, 24055: 15, 24063: 16, 24320: 10, 24330: 14, 24335: 12, 24339: 16, 24400: 14, 24405: 12, 24415: 6, 24428: 16, 24431: 16, 24445: 16, 24467: 15, 24479: 15, 24480: 9, 24490: 15, 24495: 11, 24535: 15, 24543: 16, 24560: 15, 24565: 11, 24570: 16, 24575: 10, 24576: 13, 24582: 14, 24624: 15, 24656: 15, 24672: 9, 24678: 15, 24720: 14, 24735: 14, 24736: 13, 24768: 13, 24816: 15, 24831: 15, 25186: 15, 25344: 15, 25395: 15, 25398: 16, 25424: 15, 25443: 11, 25491: 14, 25500: 14, 25519: 15, 25539: 15, 25548: 15, 25599: 15, 25700: 15, 25856: 15, 25904: 15, 25941: 15, 25942: 16, 25957: 11, 26005: 14, 26010: 14, 26021: 15, 26026: 15, 26063: 15, 26111: 15, 26112: 9, 26118: 15, 26146: 15, 26163: 11, 26180: 15, 26197: 11, 26208: 16, 26214: 5, 26217: 15, 26218: 16, 26220: 16, 26262: 14, 26265: 10, 26278: 15, 26282: 9, 26310: 15, 26316: 9, 26350: 15, 26367: 11, 26880: 14, 26895: 14, 26931: 14, 26940: 14, 26965: 14, 26970: 14, 26982: 14, 26985: 10, 27030: 13, 27033: 14, 27045: 14, 27050: 14, 27075: 14, 27084: 14, 27120: 14, 27135: 14, 27136: 13, 27199: 15, 27221: 15, 27226: 15, 27238: 15, 27242: 9, 27285: 14, 27290: 14, 27302: 14, 27306: 13, 27328: 13, 27391: 15, 27648: 13, 27699: 15, 27708: 15, 27743: 15, 27750: 15, 27756: 9, 27795: 14, 27804: 14, 27808: 13, 27846: 14, 27852: 13, 27903: 15, 28270: 15, 28416: 15, 28431: 15, 28479: 15, 28511: 15, 28527: 11, 28560: 14, 28575: 14, 28591: 15, 28623: 15, 28662: 16, 28671: 15, 28672: 14, 28679: 15, 28720: 16, 28752: 16, 28784: 10, 28791: 16, 28800: 13, 28815: 15, 28848: 15, 28880: 15, 28912: 14, 28927: 16, 29298: 14, 29440: 16, 29491: 16, 29555: 12, 29580: 15, 29619: 15, 29631: 15, 29683: 16, 29695: 16, 29812: 14, 29952: 16, 30037: 16, 30069: 12, 30090: 15, 30165: 15, 30175: 15, 30197: 16, 30207: 16, 30464: 10, 30471: 16, 30498: 14, 30515: 12, 30532: 14, 30549: 12, 30583: 6, 30584: 16, 30587: 16, 30589: 16, 30599: 15, 30600: 9, 30634: 15, 30647: 15, 30651: 11, 30668: 15, 30679: 15, 30685: 11, 30702: 16, 30711: 16, 30719: 10, 30720: 13, 30735: 15, 30780: 15, 30810: 15, 30839: 15, 30840: 9, 30855: 14, 30856: 13, 30900: 14, 30930: 14, 30960: 13, 30975: 15, 31354: 15, 31488: 15, 31539: 15, 31551: 15, 31607: 15, 31611: 11, 31620: 14, 31671: 14, 31675: 15, 31710: 16, 31731: 15, 31743: 15, 31868: 15, 32000: 15, 32085: 15, 32095: 15, 32119: 15, 32125: 11, 32130: 14, 32190: 16, 32215: 14, 32221: 15, 32245: 15, 32255: 15, 32382: 16, 32512: 14, 32527: 16, 32563: 16, 32575: 16, 32597: 16, 32607: 16, 32631: 16, 32639: 10, 32640: 13, 32655: 15, 32691: 15, 32703: 15, 32725: 15, 32735: 15, 32759: 15, 32767: 14, 32768: 13, 32776: 14, 32800: 14, 32810: 14, 32832: 14, 32844: 14, 32880: 14, 32895: 14, 32896: 9, 32904: 15, 32928: 15, 32938: 15, 32960: 15, 32972: 15, 33008: 15, 33023: 15, 33153: 15, 33280: 14, 33290: 14, 33314: 14, 33320: 13, 33345: 15, 33405: 15, 33410: 10, 33416: 14, 33440: 14, 33450: 14, 33475: 16, 33535: 16, 33667: 16, 33792: 14, 33804: 14, 33825: 15, 33860: 14, 33864: 13, 33915: 15, 33924: 10, 33928: 14, 33957: 16, 33984: 14, 33996: 14, 34047: 16, 34181: 16, 34560: 14, 34575: 14, 34605: 15, 34635: 15, 34679: 14, 34680: 13, 34695: 10, 34696: 14, 34725: 16, 34755: 16, 34800: 14, 34815: 14, 34816: 9, 34824: 15, 34833: 15, 34850: 10, 34856: 14, 34867: 16, 34884: 10, 34888: 14, 34901: 16, 34935: 10, 34936: 14, 34944: 16, 34946: 15, 34948: 15, 34951: 15, 34952: 5, 34969: 16, 34986: 11, 35003: 15, 35020: 11, 35037: 15, 35071: 11, 35209: 16, 35328: 15, 35338: 15, 35360: 14, 35370: 14, 35397: 16, 35445: 16, 35466: 11, 35496: 16, 35498: 15, 35723: 15, 35840: 15, 35852: 15, 35875: 16, 35904: 14, 35916: 14, 35955: 16, 35980: 11, 36040: 16, 36044: 15, 36237: 15, 36608: 15, 36623: 15, 36655: 16, 36687: 16, 36720: 14, 36735: 14, 36751: 11, 36856: 16, 36863: 15, 36864: 14, 36873: 15, 36912: 14, 36944: 14, 36960: 13, 36975: 15, 37008: 10, 37017: 16, 37024: 14, 37056: 14, 37104: 14, 37119: 16, 37265: 16, 37632: 14, 37683: 14, 37689: 15, 37727: 14, 37731: 15, 37740: 13, 37779: 10, 37785: 16, 37792: 14, 37827: 16, 37836: 14, 37887: 14, 38144: 14, 38207: 14, 38229: 14, 38233: 15, 38245: 15, 38250: 13, 38293: 10, 38297: 16, 38309: 16, 38314: 14, 38336: 14, 38399: 14, 38400: 13, 38415: 15, 38451: 15, 38460: 13, 38485: 15, 38490: 13, 38502: 13, 38505: 14, 38550: 9, 38553: 15, 38565: 15, 38570: 13, 38595: 15, 38604: 13, 38640: 13, 38655: 15, 39168: 10, 39177: 16, 39185: 16, 39219: 10, 39225: 16, 39253: 10, 39257: 16, 39270: 9, 39273: 15, 39318: 16, 39321: 6, 39337: 16, 39338: 10, 39355: 16, 39369: 16, 39372: 10, 39389: 16, 39417: 16, 39423: 10, 39424: 14, 39472: 14, 39509: 16, 39514: 14, 39525: 15, 39530: 13, 39577: 16, 39578: 10, 39593: 15, 39594: 14, 39631: 16, 39679: 16, 39835: 16, 39936: 14, 39987: 16, 39996: 14, 40016: 14, 40035: 15, 40044: 13, 40089: 16, 40092: 10, 40111: 16, 40137: 15, 40140: 14, 40191: 16, 40349: 16, 40704: 14, 40719: 16, 40767: 14, 40799: 14, 40800: 13, 40815: 15, 40857: 16, 40863: 10, 40879: 16, 40911: 16, 40953: 15, 40959: 14, 40960: 9, 40965: 15, 40970: 10, 40975: 16, 40992: 15, 41000: 14, 41040: 10, 41045: 16, 41055: 10, 41056: 14, 41068: 14, 41088: 16, 41090: 15, 41104: 15, 41107: 15, 41120: 5, 41125: 16, 41130: 11, 41135: 15, 41200: 11, 41205: 15, 41215: 11, 41377: 16, 41472: 15, 41480: 14, 41506: 15, 41514: 14, 41553: 16, 41565: 16, 41634: 11, 41640: 16, 41642: 15, 41891: 15, 42240: 10, 42245: 16, 42255: 10, 42273: 16, 42285: 16, 42325: 10, 42330: 9, 42341: 16, 42345: 15, 42390: 16, 42405: 6, 42409: 16, 42410: 10, 42415: 16, 42465: 16, 42477: 16, 42480: 10, 42485: 16, 42495: 10, 42496: 14, 42508: 14, 42581: 16, 42585: 15, 42598: 14, 42602: 13, 42661: 16, 42662: 10, 42665: 15, 42666: 14, 42739: 16, 42751: 16, 42919: 16, 43008: 16, 43010: 15, 43144: 16, 43146: 15, 43168: 16, 43170: 15, 43176: 12, 43178: 16, 43264: 15, 43267: 15, 43350: 16, 43417: 15, 43418: 14, 43429: 15, 43430: 14, 43433: 11, 43434: 15, 43520: 5, 43525: 16, 43530: 11, 43535: 15, 43537: 16, 43554: 11, 43560: 16, 43562: 15, 43571: 15, 43605: 6, 43609: 16, 43610: 10, 43615: 16, 43621: 16, 43622: 10, 43625: 15, 43626: 14, 43639: 16, 43648: 16, 43650: 15, 43656: 12, 43658: 16, 43669: 15, 43670: 14, 43673: 11, 43674: 15, 43680: 12, 43682: 16, 43685: 11, 43686: 15, 43689: 16, 43690: 1, 43695: 14, 43707: 14, 43724: 13, 43741: 15, 43758: 13, 43760: 13, 43765: 15, 43770: 13, 43775: 7, 43947: 14, 44204: 13, 44461: 15, 44625: 16, 44637: 16, 44718: 13, 44778: 16, 44795: 16, 44800: 11, 44805: 15, 44815: 11, 44880: 10, 44885: 16, 44895: 10, 44899: 16, 44911: 16, 44960: 13, 44965: 15, 44970: 13, 44975: 7, 45035: 16, 45040: 14, 45045: 14, 45050: 12, 45055: 11, 45056: 15, 45067: 16, 45104: 15, 45120: 14, 45135: 16, 45168: 14, 45232: 11, 45280: 16, 45296: 15, 45489: 15, 45824: 15, 45875: 15, 45883: 16, 45900: 14, 45939: 16, 45951: 14, 46003: 11, 46060: 16, 46079: 15, 46080: 14, 46095: 16, 46140: 14, 46148: 14, 46155: 15, 46200: 13, 46245: 16, 46260: 10, 46267: 16, 46305: 15, 46320: 14, 46335: 16, 46517: 16, 46848: 14, 46899: 16, 46911: 14, 46920: 13, 46967: 14, 46971: 15, 47013: 16, 47031: 10, 47035: 16, 47085: 15, 47091: 16, 47103: 14, 47288: 13, 47545: 15, 47685: 16, 47733: 16, 47802: 13, 47850: 16, 47855: 16, 47872: 11, 47889: 15, 47923: 11, 47940: 10, 47947: 16, 47957: 16, 47991: 10, 47995: 16, 48008: 13, 48025: 15, 48042: 13, 48059: 7, 48076: 14, 48093: 14, 48107: 16, 48110: 12, 48127: 11, 48316: 14, 48573: 14, 48640: 16, 48700: 16, 48705: 15, 48765: 15, 48810: 16, 48815: 16, 48827: 16, 48830: 12, 48875: 15, 48878: 16, 48890: 16, 48895: 16, 48896: 15, 48959: 15, 48960: 14, 48975: 16, 49011: 16, 49023: 14, 49087: 11, 49130: 16, 49135: 16, 49147: 16, 49151: 15, 49152: 9, 49155: 15, 49164: 10, 49167: 16, 49200: 10, 49203: 16, 49215: 10, 49216: 15, 49224: 14, 49248: 14, 49258: 14, 49280: 16, 49284: 15, 49296: 15, 49301: 15, 49344: 5, 49347: 16, 49356: 11, 49359: 15, 49392: 11, 49395: 15, 49407: 11, 49601: 16, 49920: 10, 49923: 16, 49935: 10, 49971: 10, 49980: 9, 49985: 16, 49995: 16, 50019: 16, 50025: 15, 50070: 16, 50115: 6, 50121: 16, 50124: 10, 50127: 16, 50145: 16, 50155: 16, 50160: 10, 50163: 16, 50175: 10, 50176: 15, 50184: 14, 50225: 16, 50235: 16, 50244: 15, 50252: 14, 50372: 11, 50376: 16, 50380: 15, 50629: 15, 50688: 14, 50698: 14, 50739: 16, 50745: 15, 50790: 14, 50796: 13, 50883: 16, 50886: 10, 50889: 15, 50892: 14, 50933: 16, 50943: 16, 51143: 16, 51200: 16, 51204: 15, 51336: 16, 51340: 15, 51392: 16, 51396: 15, 51400: 12, 51404: 16, 51456: 15, 51461: 15, 51510: 16, 51609: 15, 51612: 14, 51651: 15, 51654: 14, 51657: 11, 51660: 15, 51914: 13, 52171: 15, 52224: 5, 52227: 16, 52236: 11, 52239: 15, 52241: 16, 52275: 6, 52281: 16, 52284: 10, 52287: 16, 52292: 11, 52296: 16, 52300: 15, 52309: 15, 52323: 16, 52326: 10, 52329: 15, 52332: 14, 52343: 16, 52352: 16, 52356: 15, 52360: 12, 52364: 16, 52371: 15, 52374: 14, 52377: 11, 52380: 15, 52394: 13, 52411: 15, 52416: 12, 52419: 11, 52420: 16, 52422: 15, 52425: 16, 52428: 1, 52431: 14, 52445: 14, 52462: 13, 52464: 13, 52467: 15, 52476: 13, 52479: 7, 52685: 14, 52785: 16, 52795: 16, 52942: 13, 52972: 16, 52989: 16, 52992: 11, 52995: 15, 53007: 11, 53040: 10, 53043: 16, 53055: 10, 53093: 16, 53103: 16, 53184: 13, 53187: 15, 53196: 13, 53199: 7, 53229: 16, 53232: 14, 53235: 14, 53244: 12, 53247: 11, 53248: 15, 53261: 16, 53280: 14, 53295: 16, 53328: 15, 53360: 14, 53456: 11, 53472: 16, 53488: 15, 53713: 15, 53760: 14, 53775: 16, 53794: 14, 53805: 15, 53850: 14, 53880: 13, 53955: 16, 53970: 10, 53981: 16, 53985: 15, 54000: 14, 54015: 16, 54227: 16, 54528: 15, 54570: 14, 54613: 15, 54621: 16, 54645: 16, 54655: 14, 54741: 11, 54762: 16, 54783: 15, 55040: 14, 55080: 13, 55125: 16, 55135: 14, 55159: 14, 55165: 15, 55235: 16, 55255: 10, 55261: 16, 55275: 15, 55285: 16, 55295: 14, 55512: 13, 55769: 15, 56026: 14, 56283: 14, 56355: 16, 56435: 16, 56540: 13, 56556: 16, 56559: 16, 56576: 11, 56593: 15, 56610: 10, 56621: 16, 56627: 16, 56661: 11, 56695: 10, 56701: 16, 56712: 13, 56729: 15, 56746: 14, 56763: 14, 56780: 13, 56797: 7, 56813: 16, 56814: 12, 56831: 11, 56832: 16, 56865: 15, 56922: 16, 56955: 15, 57036: 16, 57039: 16, 57053: 16, 57054: 12, 57069: 15, 57070: 16, 57084: 16, 57087: 16, 57088: 15, 57120: 14, 57135: 16, 57183: 15, 57205: 16, 57215: 14, 57311: 11, 57324: 16, 57327: 16, 57341: 16, 57343: 15, 57344: 16, 57360: 15, 57504: 16, 57520: 15, 57536: 16, 57552: 15, 57568: 12, 57584: 16, 57600: 15, 57617: 15, 57630: 16, 57765: 15, 57780: 14, 57795: 15, 57810: 14, 57825: 11, 57840: 15, 58082: 13, 58339: 15, 58596: 13, 58853: 15, 59110: 14, 59367: 14, 59904: 16, 59925: 15, 60074: 16, 60095: 15, 60096: 16, 60117: 15, 60138: 12, 60159: 16, 60160: 15, 60180: 14, 60335: 15, 60347: 15, 60350: 16, 60355: 15, 60375: 14, 60395: 11, 60415: 15, 60416: 16, 60435: 15, 60576: 16, 60595: 15, 60620: 16, 60639: 15, 60652: 12, 60671: 16, 60672: 15, 60690: 14, 60837: 15, 60855: 14, 60879: 15, 60893: 15, 60894: 16, 60909: 11, 60927: 15, 60928: 12, 60945: 11, 60962: 13, 60979: 15, 60996: 13, 61013: 15, 61030: 14, 61047: 14, 61098: 12, 61115: 11, 61132: 12, 61149: 11, 61166: 8, 61183: 12, 61184: 16, 61200: 15, 61359: 16, 61375: 15, 61391: 16, 61407: 15, 61423: 12, 61439: 16, 61440: 5, 61443: 16, 61445: 16, 61455: 6, 61485: 16, 61488: 11, 61491: 15, 61500: 10, 61503: 16, 61515: 16, 61520: 11, 61525: 15, 61530: 10, 61535: 16, 61536: 16, 61545: 15, 61552: 15, 61560: 14, 61568: 16, 61575: 15, 61584: 15, 61590: 14, 61600: 12, 61605: 11, 61610: 13, 61615: 15, 61616: 16, 61620: 15, 61632: 12, 61635: 11, 61644: 13, 61647: 15, 61648: 16, 61650: 15, 61665: 16, 61680: 1, 61683: 14, 61685: 14, 61690: 13, 61692: 13, 61695: 7, 61937: 14, 61965: 16, 61999: 16, 62194: 13, 62200: 16, 62205: 16, 62208: 11, 62211: 15, 62220: 10, 62223: 16, 62259: 11, 62271: 10, 62297: 16, 62331: 16, 62400: 13, 62403: 15, 62412: 14, 62415: 14, 62448: 13, 62451: 7, 62457: 16, 62460: 12, 62463: 11, 62475: 16, 62543: 16, 62708: 13, 62712: 16, 62715: 16, 62720: 11, 62725: 15, 62730: 10, 62735: 16, 62777: 16, 62805: 11, 62815: 10, 62845: 16, 62880: 13, 62885: 15, 62890: 14, 62895: 14, 62960: 13, 62965: 7, 62969: 16, 62970: 12, 62975: 11, 62976: 16, 62985: 15, 63078: 16, 63087: 15, 63216: 16, 63219: 16, 63221: 16, 63222: 12, 63225: 15, 63226: 16, 63228: 16, 63231: 16, 63232: 15, 63240: 14, 63291: 16, 63325: 16, 63351: 15, 63359: 14, 63479: 11, 63480: 16, 63483: 16, 63485: 16, 63487: 15, 63488: 16, 63495: 15, 63624: 16, 63631: 15, 63728: 16, 63735: 15, 63736: 12, 63743: 16, 63744: 15, 63750: 14, 63897: 15, 63903: 14, 63987: 15, 63989: 15, 63990: 16, 63993: 11, 63999: 15, 64000: 12, 64005: 11, 64010: 13, 64015: 15, 64080: 13, 64085: 15, 64090: 14, 64095: 14, 64170: 12, 64175: 11, 64240: 12, 64245: 11, 64250: 8, 64255: 12, 64256: 16, 64260: 15, 64443: 16, 64447: 15, 64499: 16, 64503: 15, 64507: 12, 64511: 16, 64512: 12, 64515: 11, 64524: 13, 64527: 15, 64560: 13, 64563: 15, 64572: 14, 64575: 14, 64716: 12, 64719: 11, 64752: 12, 64755: 11, 64764: 8, 64767: 12, 64768: 16, 64770: 15, 64989: 16, 64991: 15, 65013: 16, 65015: 15, 65021: 12, 65023: 16, 65025: 16, 65263: 16, 65275: 16, 65277: 16, 65278: 13, 65280: 1, 65283: 14, 65285: 14, 65290: 13, 65292: 13, 65295: 7, 65297: 14, 65314: 13, 65320: 16, 65325: 16, 65328: 13, 65331: 7, 65337: 16, 65340: 12, 65343: 11, 65348: 13, 65352: 16, 65355: 16, 65360: 13, 65365: 7, 65369: 16, 65370: 12, 65375: 11, 65376: 16, 65379: 16, 65381: 16, 65382: 12, 65385: 15, 65386: 16, 65388: 16, 65391: 16, 65399: 11, 65400: 16, 65403: 16, 65405: 16, 65407: 15, 65408: 16, 65415: 15, 65416: 12, 65423: 16, 65427: 15, 65429: 15, 65430: 16, 65433: 11, 65439: 15, 65440: 12, 65445: 11, 65450: 8, 65455: 12, 65459: 16, 65463: 15, 65467: 12, 65471: 16, 65472: 12, 65475: 11, 65484: 8, 65487: 12, 65493: 16, 65495: 15, 65501: 12, 65503: 16, 65515: 16, 65517: 16, 65518: 13, 65520: 8, 65523: 12, 65525: 12, 65527: 16, 65529: 16, 65530: 13, 65532: 13, 65535: 1}\n\n\n\ndef expr():\n    global now\n    ans=0\n    if s[now] in [\"0\",\"1\",\"a\",\"b\",\"c\",\"d\"]:\n        x = term()\n        now+=1\n        return x\n    elif s[now]==\"-\":\n        now+=1\n        x = expr()\n        return (~x)&O\n    else:\n        now+=1\n        x= expr()\n        ans=x\n        while now<len(s) and s[now] in [\"*\",\"^\"]:\n            op= s[now] ;now+=1\n            y= expr()\n            if op==\"^\":\n                ans^=y\n            else:\n                ans = ans&y\n        now+=1\n        return ans\n\n\n\ndef term(): #\u305f\u3060\u306e\u88dc\u52a9\u95a2\u6570\n    TMP= {\"0\":0, \"1\":O, \"a\":A, \"b\":B ,\"c\":C ,\"d\":D}\n    return TMP[s[now]]\n\n\nwhile 1:\n    s=input()\n    if s==\".\":exit()\n    now=0\n    id = expr()\n    print(ddd.get(id,31))\n\n", "import heapq\nimport itertools\ndef evaluate(siki):\n    return lambda a,b,c,d:eval(siki.replace(\"-\",\"-~\"))%2\ndef changenum(siki):\n    res=0\n    for seq in itertools.product(range(2),repeat=4):\n        a,b,c,d=seq\n        if evaluate(siki)(a,b,c,d)==1:\n            res+=2**(a+2*b+4*c+8*d)\n    return res\nD=dict()\ndef dget(m):\n    if m in D:\n        return D[m]\n    else:\n        return 17\nq=[]\nheapq.heappush(q,(1,changenum(\"a\")))\nheapq.heappush(q,(1,changenum(\"b\")))\nheapq.heappush(q,(1,changenum(\"c\")))\nheapq.heappush(q,(1,changenum(\"d\")))\nheapq.heappush(q,(1,changenum(\"0\")))\nheapq.heappush(q,(1,changenum(\"1\")))\nD[changenum(\"a\")]=1\nD[changenum(\"b\")]=1\nD[changenum(\"c\")]=1\nD[changenum(\"d\")]=1\nD[changenum(\"0\")]=1\nD[changenum(\"1\")]=1\nwhile(len(q)>0):\n    le,n=heapq.heappop(q)\n    #print(le,n,dget(240),dget(255))\n    if D[n]<le:\n        continue\n    D[n]=min(D[n],le)\n    cost=1\n    if dget(65535^n)>D[n]+cost and D[n]+cost<=16:\n        D[65535^n]=D[n]+cost\n        heapq.heappush(q,(D[65535^n],65535^n))\n    tmp=dict()\n    for k in D:\n        if dget(n^k)>D[n]+D[k]+3 and D[n]+D[k]+3<=16:\n            tmp[n^k]=D[n]+D[k]+3\n            heapq.heappush(q,(tmp[n^k],n^k))\n        if dget(n&k)>D[n]+D[k]+3 and D[n]+D[k]+3<=16:\n            tmp[n&k]=D[n]+D[k]+3\n            heapq.heappush(q,(tmp[n&k],n&k))\n    for k in tmp:\n        D[k]=tmp[k]\nwhile(True):\n    S=input()\n    if S==\".\":\n        break\n    print(D[changenum(S)])\n"]

source: aizu

question:
Boolean Expression Compressor

You are asked to build a compressor for Boolean expressions
that transforms expressions to the shortest form keeping their meaning.

The grammar of the Boolean expressions has terminals
0 1 a b c d - ^ * ( ), start symbol <E> and the following production rule:

<E>  ::=  0  |  1  |  a  |  b  |  c  |  d  |  -<E>  |  (<E>^<E>)  |  (<E>*<E>)

Letters a, b, c and d represent Boolean
variables that have values of either  0 or 1.
Operators are evaluated as shown in the Table below.
In other words, - means negation (NOT),
^ means exclusive disjunction (XOR), and
* means logical conjunction (AND).

Table: Evaluations of operators
![image](1.png)

Write a program that calculates the length of the shortest expression that
evaluates equal to the given expression with whatever values of the four variables.

For example, 0, that is the first expression in the sample input,
cannot be shortened further.
Therefore the shortest length for this expression is 1.

For another example, (a*(1*b)), the second in the sample input,
always evaluates equal to (a*b) and (b*a),
which are the shortest.   The output for this expression, thus, should be 5.

Input

The input consists of multiple datasets.
A dataset consists of one line, containing an expression
conforming to the grammar described above.
The length of the expression is less than or equal to 16 characters.

The end of the input is indicated by a line containing one
. (period).
The number of datasets in the input is at most 200.

Output

For each dataset,
output a single line containing an integer which is the length of the
shortest expression that has the same value as the given expression for
all combinations of values in the variables.

Sample Input

0
(a*(1*b))
(1^a)
(-(-a*-b)*a)
(a^(b^(c^d)))
.

Output for the Sample Input

1
5
2
1
13

data_split: test


E. Fox And Polygon

problem_index: E

time_limit: 2 seconds

memory_limit: 256 megabytes

source: codeforces

raw_problem:
E. Fox And Polygon

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Fox Ciel just designed a puzzle game called "Polygon"! It is played using triangulations of a regular n-edge polygon. The goal is to transform one triangulation to another by some tricky rules.

Triangulation of an n-edge poylgon is a set of n - 3 diagonals satisfying the condition that no two diagonals share a common internal point.

For example, the initial state of the game may look like (a) in above figure. And your goal may look like (c). In each step you can choose a diagonal inside the polygon (but not the one of edges of the polygon) and flip this diagonal.

Suppose you are going to flip a diagonal a – b. There always exist two triangles sharing a – b as a side, let's denote them as a – b – c and a – b – d. As a result of this operation, the diagonal a – b is replaced by a diagonal c – d. It can be easily proven that after flip operation resulting set of diagonals is still a triangulation of the polygon.

So in order to solve above case, you may first flip diagonal 6 – 3, it will be replaced by diagonal 2 – 4. Then you flip diagonal 6 – 4 and get figure (c) as result.

Ciel just proved that for any starting and destination triangulations this game has a solution. She wants you to solve it in no more than 20 000 steps for any puzzle satisfying n ≤ 1000.

Input

The first line contain an integer n (4 ≤ n ≤ 1000), number of edges of the regular polygon.

Then follows two groups of (n - 3) lines describing the original triangulation and goal triangulation.

Description of each triangulation consists of (n - 3) lines. Each line contains 2 integers ai and bi (1 ≤ ai, bi ≤ n), describing a diagonal ai – bi.

It is guaranteed that both original and goal triangulations are correct (i. e. no two diagonals share a common internal point in both of these triangulations).

Output

First, output an integer k (0 ≤ k ≤ 20, 000): number of steps.

Then output k lines, each containing 2 integers ai and bi: the endpoints of a diagonal you are going to flip at step i. You may output ai and bi in any order.

If there are several possible solutions, output any of them.

Examples

Input

4
1 3
2 4

Output

1
1 3

Input

6
2 6
3 6
4 6
6 2
5 2
4 2

Output

2
6 3
6 4

Input

8
7 1
2 7
7 3
6 3
4 6
6 1
6 2
6 3
6 4
6 8

Output

3
7 3
7 2
7 1

Note

Sample test 2 is discussed above and shown on the picture.

question:
Fox Ciel just designed a puzzle game called "Polygon"! It is played using triangulations of a regular n-edge polygon. The goal is to transform one triangulation to another by some tricky rules.
![image](1.png)Triangulation of an n-edge poylgon is a set of n - 3 diagonals satisfying the condition that no two diagonals share a common internal point.
For example, the initial state of the game may look like (a) in above figure. And your goal may look like (c). In each step you can choose a diagonal inside the polygon (but not the one of edges of the polygon) and flip this diagonal.
Suppose you are going to flip a diagonal a – b. There always exist two triangles sharing a – b as a side, let's denote them as a – b – c and a – b – d. As a result of this operation, the diagonal a – b is replaced by a diagonal c – d. It can be easily proven that after flip operation resulting set of diagonals is still a triangulation of the polygon.
So in order to solve above case, you may first flip diagonal 6 – 3, it will be replaced by diagonal 2 – 4. Then you flip diagonal 6 – 4 and get figure (c) as result.
Ciel just proved that for any starting and destination triangulations this game has a solution. She wants you to solve it in no more than 20 000 steps for any puzzle satisfying n ≤ 1000.

Input
The first line contain an integer n (4 ≤ n ≤ 1000), number of edges of the regular polygon.
Then follows two groups of (n - 3) lines describing the original triangulation and goal triangulation.
Description of each triangulation consists of (n - 3) lines. Each line contains 2 integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n), describing a diagonal a_{i} – b_{i}.
It is guaranteed that both original and goal triangulations are correct (i. e. no two diagonals share a common internal point in both of these triangulations).

Output
First, output an integer k (0 ≤ k ≤ 20, 000): number of steps.
Then output k lines, each containing 2 integers a_{i} and b_{i}: the endpoints of a diagonal you are going to flip at step i. You may output a_{i} and b_{i} in any order.
If there are several possible solutions, output any of them.

Examples
Input
4
1 3
2 4

Output
1
1 3

Input
6
2 6
3 6
4 6
6 2
5 2
4 2

Output
2
6 3
6 4

Input
8
7 1
2 7
7 3
6 3
4 6
6 1
6 2
6 3
6 4
6 8

Output
3
7 3
7 2
7 1

Note
Sample test 2 is discussed above and shown on the picture.

tags: ['Divide and conquer', 'Constructive algorithms']

raw_tags: ['divide and conquer', 'constructive algorithms']

data_split: test


D. Spaceship Exploration

problem_raw:
D. Spaceship Exploration

time limit per test
3 seconds

memory limit per test
1024 megabytes

input
standard input

output
standard output

In The ICPC Galaxy, there exists a zone filled with asteroids that is unsafe to enter. The map of the galaxy is represented in a 2D Cartesian coordinate system. The zone is in the shape of an $$$N$$$-sided convex polygon. Each corner is numbered from $$$1$$$ to $$$N$$$; corner $$$i$$$ is located at $$$(X_i, Y_i)$$$. At any moment, you should not be inside this polygon; however, it is safe to touch the side of the polygon.

There are $$$Q$$$ scenarios (numbered from $$$1$$$ to $$$Q$$$). In scenario $$$j$$$, you want to go from a starting point at $$$(A_j, B_j)$$$ to an ending point at $$$(C_j, D_j)$$$. You will be riding on a special spaceship that can only travel in a straight line. First, you set the direction of the spaceship, then the spaceship will start traveling in that direction. During the travel, you are only allowed to change direction at most once. Changing direction means you stop the spaceship, set a new direction, and then start traveling again in the new direction.

For each scenario, determine the minimum distance required to travel without being inside of the zone at any moment, or report if it is impossible to reach the ending point.

Input

The first line consists of an integer $$$N$$$ ($$$3 \leq N \leq 100\,000$$$).

Each of the next $$$N$$$ lines consists of two integers $$$X_i$$$ $$$Y_i$$$ ($$$-10^9 \leq X_i, Y_i \leq 10^9$$$). The points form a convex polygon in counterclockwise order. There are no three points which are collinear.

The following line consists of an integer $$$Q$$$ ($$$1 \leq Q \leq 100\,000$$$).

Each of the next $$$Q$$$ lines consists of four integers $$$A_j$$$ $$$B_j$$$ $$$C_j$$$ $$$D_j$$$ ($$$-10^9 \leq A_j, B_j, C_j, D_j \leq 10^9$$$). There are no starting points and ending points inside the zone. However, it is possible for the starting point and the ending point to be at the side of the zone.

All the coordinates in the input are integers.

Output

For each scenario, output the answer in a single line.

If it is possible to reach the ending point without being inside the zone at any moment, then output the minimum distance required to travel. Otherwise, output -1.

Your answer is considered correct if its absolute error or relative error does not exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer is accepted if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$.

Examples

Input

5
0 2
2 0
4 0
4 4
2 4
5
6 1 6 3
2 5 0 0
3 5 3 -1
1 4 5 4
3 4 3 0

Output

2
5.6055512755
8.48528137422
4
-1

Input

4
-10 -9
10 -9
10 9
-10 9
2
0 10 0 -10
-10 -10 -10 -10

Output

200.9975124224
0

Input

8
-20 -10
10 -20
25 -15
35 -5
30 10
15 20
-25 15
-30 5
6
-15 -15 -15 20
-30 -5 30 15
25 20 -5 -20
-5 25 20 -20
-30 10 30 -10
-30 -50 50 0

Output

59.0857761929
103.2455532034
94.7213595500
101.5640991922
164.8528137424
94.3398113206

Note

Explanation for the sample input/output #1

This sample is depicted in the following illustration.

During scenario $$$1$$$ and $$$4$$$, you can directly go to the ending point without changing the direction.

During scenario $$$2$$$, you can go to $$$(0, 2)$$$, then change direction to the ending point.

During scenario $$$3$$$, you can go to $$$(6, 2)$$$, then change direction to the ending point.

During scenario $$$5$$$, it can be shown that it is impossible to reach the ending point.

problem_index: D

time_limit: 3 seconds

memory_limit: 1024 megabytes

input:
5
0 2
2 0
4 0
4 4
2 4
5
6 1 6 3
2 5 0 0
3 5 3 -1
1 4 5 4
3 4 3 0

output:
2
5.6055512755
8.48528137422
4
-1

input:
4
-10 -9
10 -9
10 9
-10 9
2
0 10 0 -10
-10 -10 -10 -10

output:
200.9975124224
0

input:
8
-20 -10
10 -20
25 -15
35 -5
30 10
15 20
-25 15
-30 5
6
-15 -15 -15 20
-30 -5 30 15
25 20 -5 -20
-5 25 20 -20
-30 10 30 -10
-30 -50 50 0

output:
59.0857761929
103.2455532034
94.7213595500
101.5640991922
164.8528137424
94.3398113206

question:
In The ICPC Galaxy, there exists a zone filled with asteroids that is unsafe to enter. The map of the galaxy is represented in a 2D Cartesian coordinate system. The zone is in the shape of an $$$N$$$-sided convex polygon. Each corner is numbered from $$$1$$$ to $$$N$$$; corner $$$i$$$ is located at $$$(X_i, Y_i)$$$. At any moment, you should not be inside this polygon; however, it is safe to touch the side of the polygon.
There are $$$Q$$$ scenarios (numbered from $$$1$$$ to $$$Q$$$). In scenario $$$j$$$, you want to go from a starting point at $$$(A_j, B_j)$$$ to an ending point at $$$(C_j, D_j)$$$. You will be riding on a special spaceship that can only travel in a straight line. First, you set the direction of the spaceship, then the spaceship will start traveling in that direction. During the travel, you are only allowed to change direction at most once. Changing direction means you stop the spaceship, set a new direction, and then start traveling again in the new direction.
For each scenario, determine the minimum distance required to travel without being inside of the zone at any moment, or report if it is impossible to reach the ending point.

Input
The first line consists of an integer $$$N$$$ ($$$3 \leq N \leq 100\,000$$$).
Each of the next $$$N$$$ lines consists of two integers $$$X_i$$$ $$$Y_i$$$ ($$$-10^9 \leq X_i, Y_i \leq 10^9$$$). The points form a convex polygon in counterclockwise order. There are no three points which are collinear.
The following line consists of an integer $$$Q$$$ ($$$1 \leq Q \leq 100\,000$$$).
Each of the next $$$Q$$$ lines consists of four integers $$$A_j$$$ $$$B_j$$$ $$$C_j$$$ $$$D_j$$$ ($$$-10^9 \leq A_j, B_j, C_j, D_j \leq 10^9$$$). There are no starting points and ending points inside the zone. However, it is possible for the starting point and the ending point to be at the side of the zone.
All the coordinates in the input are integers.

Output
For each scenario, output the answer in a single line.
If it is possible to reach the ending point without being inside the zone at any moment, then output the minimum distance required to travel. Otherwise, output -1.
Your answer is considered correct if its absolute error or relative error does not exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer is accepted if $$$\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$$$.

Examples
Input

5
0 2
2 0
4 0
4 4
2 4
5
6 1 6 3
2 5 0 0
3 5 3 -1
1 4 5 4
3 4 3 0

Output

2
5.6055512755
8.48528137422
4
-1

Input

4
-10 -9
10 -9
10 9
-10 9
2
0 10 0 -10
-10 -10 -10 -10

Output

200.9975124224
0

Input

8
-20 -10
10 -20
25 -15
35 -5
30 10
15 20
-25 15
-30 5
6
-15 -15 -15 20
-30 -5 30 15
25 20 -5 -20
-5 25 20 -20
-30 10 30 -10
-30 -50 50 0

Output

59.0857761929
103.2455532034
94.7213595500
101.5640991922
164.8528137424
94.3398113206

Note
Explanation for the sample input/output #1
This sample is depicted in the following illustration.
 ![image](1.png) During scenario $$$1$$$ and $$$4$$$, you can directly go to the ending point without changing the direction.
During scenario $$$2$$$, you can go to $$$(0, 2)$$$, then change direction to the ending point.
During scenario $$$3$$$, you can go to $$$(6, 2)$$$, then change direction to the ending point.
During scenario $$$5$$$, it can be shown that it is impossible to reach the ending point.

source: codeforces

data_split: test


solutions: ["class Solution:\n\n\tdef projectionArea(self, grid: List[List[int]]) -> int:\n\t\tans = 0\n\t\tfor i in range(len(grid)):\n\t\t\trow = 0\n\t\t\tcol = 0\n\t\t\tfor j in range(len(grid[i])):\n\t\t\t\tif grid[i][j]:\n\t\t\t\t\tans += 1\n\t\t\t\trow = max(row, grid[i][j])\n\t\t\t\tcol = max(col, grid[j][i])\n\t\t\tans += row + col\n\t\treturn ans\n", "class Solution:\n\n\tdef projectionArea(self, grid: List[List[int]]) -> int:\n\t\tmax_rows = [0 for _ in grid]\n\t\tmax_cols = [0 for _ in grid]\n\t\ttotal_nonzero = 0\n\t\tfor r in range(len(grid)):\n\t\t\tfor c in range(len(grid[r])):\n\t\t\t\tif grid[r][c] > max_cols[c]:\n\t\t\t\t\tmax_cols[c] = grid[r][c]\n\t\t\t\tif grid[r][c] > max_rows[r]:\n\t\t\t\t\tmax_rows[r] = grid[r][c]\n\t\t\t\tif grid[r][c] > 0:\n\t\t\t\t\ttotal_nonzero += 1\n\t\tprint(max_rows)\n\t\tprint(max_cols)\n\t\tprint(total_nonzero)\n\t\treturn sum(max_rows) + sum(max_cols) + total_nonzero\n"]

starter_code:
class Solution:
    def projectionArea(self, grid: List[List[int]]) -> int:

difficulty: EASY

source: leetcode

tags: ['Geometry', 'Matrices', 'Data structures', 'Mathematics']

skill_types: ['Data structures']

raw_problem:
You are given an n x n grid where we place some 1 x 1 x 1 cubes that are axis-aligned with the x, y, and z axes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of the cell (i, j).

We view the projection of these cubes onto the xy, yz, and zx planes.

A projection is like a shadow, that maps our 3-dimensional figure to a 2-dimensional plane. We are viewing the "shadow" when looking at the cubes from the top, the front, and the side.

Return the total area of all three projections.

Example 1:

Input: grid = [[1,2],[3,4]]
Output: 17
Explanation: Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

Example 2:

Input: grid = [[2]]
Output: 5

Example 3:

Input: grid = [[1,0],[0,2]]
Output: 8

Constraints:

n == grid.length == grid[i].length

1 <= n <= 50

0 <= grid[i][j] <= 50

question:
You are given an n x n grid where we place some 1 x 1 x 1 cubes that are axis-aligned with the x, y, and z axes.
Each value v = grid[i][j] represents a tower of v cubes placed on top of the cell (i, j).
We view the projection of these cubes onto the xy, yz, and zx planes.
A projection is like a shadow, that maps our 3-dimensional figure to a 2-dimensional plane. We are viewing the "shadow" when looking at the cubes from the top, the front, and the side.
Return the total area of all three projections.

Example 1:
![image](1.png)

Input: grid = [[1,2],[3,4]]
Output: 17
Explanation: Here are the three projections ("shadows") of the shape made with each axis-aligned plane.

Example 2:

Input: grid = [[2]]
Output: 5

Example 3:

Input: grid = [[1,0],[0,2]]
Output: 8

Constraints:

- n == grid.length == grid[i].length
- 1 <= n <= 50
- 0 <= grid[i][j] <= 50

data_split: test


F. Nearest Leaf

problem_index: F

time_limit: 4 seconds

memory_limit: 512 megabytes

note:
In the first example, the tree looks like this:
![image](images/cf_1110_F/1.png)
In the first query, the nearest leaf for the vertex $$$1$$$ is vertex $$$4$$$ with distance $$$3$$$. In the second query, the nearest leaf for vertex $$$5$$$ is vertex $$$5$$$ with distance $$$0$$$. In the third query the nearest leaf for vertex $$$4$$$ is vertex $$$4$$$; however, it is not inside interval $$$[1, 2]$$$ of the query. The only leaf in interval $$$[1, 2]$$$ is vertex $$$2$$$ with distance $$$13$$$ from vertex $$$4$$$.

source: codeforces

raw_problem:
F. Nearest Leaf

time limit per test
4 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Let's define the Eulerian traversal of a tree (a connected undirected graph without cycles) as follows: consider a depth-first search algorithm which traverses vertices of the tree and enumerates them in the order of visiting (only the first visit of each vertex counts). This function starts from the vertex number $$$1$$$ and then recursively runs from all vertices which are connected with an edge with the current vertex and are not yet visited in increasing numbers order. Formally, you can describe this function using the following pseudocode:

next_id = 1
id = array of length n filled with -1
visited = array of length n filled with false

function dfs(v):
    visited[v] = true
    id[v] = next_id
    next_id += 1
    for to in neighbors of v in increasing order:
        if not visited[to]:
            dfs(to)

You are given a weighted tree, the vertices of which were enumerated with integers from $$$1$$$ to $$$n$$$ using the algorithm described above.

A leaf is a vertex of the tree which is connected with only one other vertex. In the tree given to you, the vertex $$$1$$$ is not a leaf. The distance between two vertices in the tree is the sum of weights of the edges on the simple path between them.

You have to answer $$$q$$$ queries of the following type: given integers $$$v$$$, $$$l$$$ and $$$r$$$, find the shortest distance from vertex $$$v$$$ to one of the leaves with indices from $$$l$$$ to $$$r$$$ inclusive.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \leq n \leq 500\,000, 1 \leq q \leq 500\,000$$$) — the number of vertices in the tree and the number of queries, respectively.

The $$$(i - 1)$$$-th of the following $$$n - 1$$$ lines contains two integers $$$p_i$$$ and $$$w_i$$$ ($$$1 \leq p_i < i, 1 \leq w_i \leq 10^9$$$), denoting an edge between vertices $$$p_i$$$ and $$$i$$$ with the weight $$$w_i$$$.

It's guaranteed that the given edges form a tree and the vertices are enumerated in the Eulerian traversal order and that the vertex with index $$$1$$$ is not a leaf.

The next $$$q$$$ lines describe the queries. Each of them contains three integers $$$v_i$$$, $$$l_i$$$, $$$r_i$$$ ($$$1 \leq v_i \leq n, 1 \leq l_i \leq r_i \leq n$$$), describing the parameters of the query. It is guaranteed that there is at least one leaf with index $$$x$$$ such that $$$l_i \leq x \leq r_i$$$.

Output

Output $$$q$$$ integers — the answers for the queries in the order they are given in the input.

Examples

Input

5 3
1 10
1 1
3 2
3 3
1 1 5
5 4 5
4 1 2

Output

3
0
13

Input

5 3
1 1000000000
2 1000000000
1 1000000000
1 1000000000
3 4 5
2 1 5
2 4 5

Output

3000000000
1000000000
2000000000

Input

11 8
1 7
2 1
1 20
1 2
5 6
6 2
6 3
5 1
9 10
9 11
5 1 11
1 1 4
9 4 8
6 1 4
9 7 11
9 10 11
8 1 11
11 4 5

Output

8
8
9
16
9
10
0
34

Note

In the first example, the tree looks like this:

In the first query, the nearest leaf for the vertex $$$1$$$ is vertex $$$4$$$ with distance $$$3$$$. In the second query, the nearest leaf for vertex $$$5$$$ is vertex $$$5$$$ with distance $$$0$$$. In the third query the nearest leaf for vertex $$$4$$$ is vertex $$$4$$$; however, it is not inside interval $$$[1, 2]$$$ of the query. The only leaf in interval $$$[1, 2]$$$ is vertex $$$2$$$ with distance $$$13$$$ from vertex $$$4$$$.

question:
Let's define the Eulerian traversal of a tree (a connected undirected graph without cycles) as follows: consider a depth-first search algorithm which traverses vertices of the tree and enumerates them in the order of visiting (only the first visit of each vertex counts). This function starts from the vertex number $$$1$$$ and then recursively runs from all vertices which are connected with an edge with the current vertex and are not yet visited in increasing numbers order. Formally, you can describe this function using the following pseudocode:

next_id = 1
id = array of length n filled with -1
visited = array of length n filled with false

function dfs(v):
    visited[v] = true
    id[v] = next_id
    next_id += 1
    for to in neighbors of v in increasing order:
        if not visited[to]:
            dfs(to)

You are given a weighted tree, the vertices of which were enumerated with integers from $$$1$$$ to $$$n$$$ using the algorithm described above.
A leaf is a vertex of the tree which is connected with only one other vertex. In the tree given to you, the vertex $$$1$$$ is not a leaf. The distance between two vertices in the tree is the sum of weights of the edges on the simple path between them.
You have to answer $$$q$$$ queries of the following type: given integers $$$v$$$, $$$l$$$ and $$$r$$$, find the shortest distance from vertex $$$v$$$ to one of the leaves with indices from $$$l$$$ to $$$r$$$ inclusive.

Input
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \leq n \leq 500\,000, 1 \leq q \leq 500\,000$$$) — the number of vertices in the tree and the number of queries, respectively.
The $$$(i - 1)$$$-th of the following $$$n - 1$$$ lines contains two integers $$$p_i$$$ and $$$w_i$$$ ($$$1 \leq p_i < i, 1 \leq w_i \leq 10^9$$$), denoting an edge between vertices $$$p_i$$$ and $$$i$$$ with the weight $$$w_i$$$.
It's guaranteed that the given edges form a tree and the vertices are enumerated in the Eulerian traversal order and that the vertex with index $$$1$$$ is not a leaf.
The next $$$q$$$ lines describe the queries. Each of them contains three integers $$$v_i$$$, $$$l_i$$$, $$$r_i$$$ ($$$1 \leq v_i \leq n, 1 \leq l_i \leq r_i \leq n$$$), describing the parameters of the query. It is guaranteed that there is at least one leaf with index $$$x$$$ such that $$$l_i \leq x \leq r_i$$$.

Output
Output $$$q$$$ integers — the answers for the queries in the order they are given in the input.

Examples
Input
5 3
1 10
1 1
3 2
3 3
1 1 5
5 4 5
4 1 2

Output
3
0
13

Input
5 3
1 1000000000
2 1000000000
1 1000000000
1 1000000000
3 4 5
2 1 5
2 4 5

Output
3000000000
1000000000
2000000000

Input
11 8
1 7
2 1
1 20
1 2
5 6
6 2
6 3
5 1
9 10
9 11
5 1 11
1 1 4
9 4 8
6 1 4
9 7 11
9 10 11
8 1 11
11 4 5

Output
8
8
9
16
9
10
0
34

Note
In the first example, the tree looks like this:
 ![image](1.png) In the first query, the nearest leaf for the vertex $$$1$$$ is vertex $$$4$$$ with distance $$$3$$$. In the second query, the nearest leaf for vertex $$$5$$$ is vertex $$$5$$$ with distance $$$0$$$. In the third query the nearest leaf for vertex $$$4$$$ is vertex $$$4$$$; however, it is not inside interval $$$[1, 2]$$$ of the query. The only leaf in interval $$$[1, 2]$$$ is vertex $$$2$$$ with distance $$$13$$$ from vertex $$$4$$$.

skill_types: ['Data structures']

data_split: test


Chain-Confined Path

source: ACM International Collegiate Programming Contest, Japan Domestic 2012

raw_problem:
Chain-Confined Path

There is a chain consisting of multiple circles on a plane.
The first (last) circle of the chain only intersects with the next (previous) circle,
and each intermediate circle intersects only with the two neighboring circles.

Your task is to find the shortest path that satisfies the following conditions.

The path connects the centers of the first circle and the last circle.

The path is confined in the chain, that is, all the points on the path are located within or on at least one of the circles.

Figure E-1 shows an example of such a chain and the corresponding shortest path.

Figure E-1: An  example chain and the corresponding shortest path

Input

The input consists of multiple datasets.
Each dataset represents the shape of a chain in the following format.

n

x1 y1 r1

x2 y2 r2

...

xn yn rn

The first line of a dataset contains an integer n (3 ≤ n ≤ 100)
representing the number of the circles.
Each of the following n lines contains three integers separated by a single space.
(xi, yi)
and ri represent
the center position and the radius of the i-th circle Ci.
You can assume that 0 ≤ xi ≤ 1000,
0 ≤ yi ≤ 1000, and
1 ≤ ri ≤ 25.

You can assume that Ci  and
Ci+1  (1 ≤ i ≤ n−1) intersect at two separate points.
When j ≥ i+2, Ci  and Cj  are apart and either of them does not contain the other.
In addition, you can assume that any circle does not contain the center of any other circle.

The end of the input is indicated by a line containing a zero.

Figure E-1 corresponds to the first dataset of Sample Input below.
Figure E-2 shows the shortest paths for the subsequent datasets of Sample Input.

Figure E-2: Example chains and the corresponding shortest paths

Output

For each dataset, output a single line containing the length of the shortest chain-confined path between the centers of the first circle and the last circle.
The value should not have an error greater than 0.001.
No extra characters should appear in the output.

Sample Input

10
802 0 10
814 0 4
820 1 4
826 1 4
832 3 5
838 5 5
845 7 3
849 10 3
853 14 4
857 18 3
3
0 0 5
8 0 5
8 8 5
3
0 0 5
7 3 6
16 0 5
9
0 3 5
8 0 8
19 2 8
23 14 6
23 21 6
23 28 6
19 40 8
8 42 8
0 39 5
11
0 0 5
8 0 5
18 8 10
8 16 5
0 16 5
0 24 5
3 32 5
10 32 5
17 28 8
27 25 3
30 18 5
0

Output for the Sample Input

58.953437
11.414214
16.0
61.874812
63.195179

solutions: ["def solve():\n    from math import acos\n    from cmath import phase, rect, pi\n    \n    from sys import stdin\n    file_input = stdin\n    \n    while True:\n        n = int(file_input.readline())\n        if n == 0:\n            break\n        \n        C = (map(int, file_input.readline().split()) for i in range(n))\n        P = []\n        x, y, r1 = next(C)\n        c1 = x + y * 1j\n        P.append(c1)\n        \n        # calculation of cross points of circles\n        for x, y, r2 in C:\n            c2 = x + y * 1j\n            \n            base = c2 - c1\n            d = abs(base)\n            a = acos((r1 ** 2 + d ** 2 - r2 ** 2) / (2 * r1 * d))\n            t = phase(base)\n            cp1 = c1 + rect(r1, t + a)\n            cp2 = c1 + rect(r1, t - a)\n            \n            P.append(cp1)\n            P.append(cp2)\n            \n            c1, r1 = c2, r2\n        \n        # search path and calculation of its cost\n        lim = 5000\n        dist = [lim] * (2 * n)\n        dist[0] = 0\n        goal = c1\n        g_idx = 2 * n - 1\n        indices = ((i + (i % 2) + 1, i + (i % 2) + 2) for i in range(g_idx))\n        \n        for tpl_idx, cp, d in zip(indices, P, dist):\n            j, k = tpl_idx\n            s1 = None\n            s2 = None\n            p_s1 = None\n            p_s2 = None\n            for l, cp1, cp2 in zip(range(j, g_idx, 2), P[j::2], P[k::2]):\n                t_s1 = cp1 - cp\n                t_s2 = cp2 - cp\n                if s1 is None or phase(s1 / t_s1) >= 0:\n                    s1 = t_s1\n                if s2 is None or phase(s2 / t_s2) <= 0:\n                    s2 = t_s2\n                if phase(s1 / s2) < 0:\n                    break\n                \n                if p_s1 != s1:\n                    dist[l] = min(dist[l], d + abs(s1))\n                    p_s1 = s1\n                if p_s2 != s2:\n                    dist[l+1] = min(dist[l+1], d + abs(s2))\n                    p_s2 = s2\n            else:\n                gs = goal - cp\n                if (s1 is None and s2 is None) or \\\n                phase(s1 / gs) >= 0 and phase(s2 / gs) <= 0:\n                    dist[g_idx] = min(dist[g_idx], d + abs(gs))\n        \n        print(dist[g_idx])\n\nsolve()\n", "def solve():\n  n=int(input())\n  if n==0:\n    exit()\n  C=[]\n  for i in range(n):\n    x,y,r=map(int,input().split())\n    C.append(Circle(point(x,y),r))\n  inf=1<<30\n  P=[[] for i in range(n+1)]\n  P[0].append(C[0].p)\n  P[0].append(C[0].p)\n  P[n].append(C[n-1].p)\n  P[n].append(C[n-1].p)\n  for i in range(1,n):\n    P[i]=CrossPointCircles(C[i-1],C[i])\n  dist=[[inf,inf] for i in range(n+1)]\n  dist[0]=[0,0]\n  for i in range(n+1):\n    for j in range(i+1,n+1):\n      for i0 in range(2):\n        for j0 in range(2):\n          flag=True\n          p0=P[i][i0]\n          p1=P[j][j0]\n          for k in range(i+1,j):\n            if not isIntersect(Segment(p0,p1),Segment(P[k][0],P[k][1])):\n              flag=False\n              break\n          if flag:\n            dist[j][j0]=min(dist[j][j0],dist[i][i0]+abs(p0-p1))\n  print_float(dist[n][0])\n  \n\n\n\n\n\n\n\n# \u5e7e\u4f55\u30e9\u30a4\u30d6\u30e9\u30ea\n\nfrom functools import cmp_to_key\nfrom typing import List\nfrom math import*\n\nPoint=complex\ndef point(a,b)->Point:\n  return a+b*1j\n\ndef print_Point(p:Point):\n  x,y=p.real,p.imag\n  print('{:.10f}'.format(x),'{:.10f}'.format(y))\n\ndef print_float(x:float):\n  print('{:.10f}'.format(x))\n\ndef str_float(x:float)->str:\n  return '{:.10f}'.format(x)\n\ndef norm(p:Point):\n  return p.real**2+p.imag**2\n\ndef cmp(a:Point,b:Point)->bool:\n  if not equal(a.real,b.real):\n    if a.real<b.real:return -1\n    else:return 1\n  else:\n    if a.imag<b.imag:return -1\n    else:return 1\n\neps=1e-9\n\n# \u540c\u3058\u304b\u5224\u5b9a\ndef equal(a:Point,b:Point)->float:\n  return abs(a-b)<eps\n\n# \u5358\u4f4d\u30d9\u30af\u30c8\u30eb\u3092\u6c42\u3081\u308b\ndef unitVector(a:Point)->Point:\n  return a/abs(a)\n\n# \u5185\u7a4d(dot product):a\u30fbb=|a||b|cos\u0398\ndef dot(a:Point,b:Point)->float:\n  return a.real*b.real+a.imag*b.imag\n\n# \u5916\u7a4d(cross product):a\u00d7b=|a||b|sin\u0398\ndef cross(a:Point,b:Point)->float:\n  return a.real*b.imag-a.imag*b.real\n\n# \u70b9p\u3092\u53cd\u6642\u8a08\u56de\u308a\u306btheta\u5ea6\u56de\u8ee2\ndef rotate(p:Point,theta:float)->Point:\n  return (cos(theta)*p.real-sin(theta)*p.imag)+(sin(theta)*p.real+cos(theta)*p.imag)*1j\n\n\nclass Line:\n  def __init__(self,a,b,c=False):\n    if c==False:\n      # a,b \u306f\u8907\u7d20\u6570\n      self.a=a\n      self.b=b\n    else:\n      # ax+by=c\n      # a,b,c \u306f\u5b9f\u6570\n      if equal(a,0):\n        self.a=(c/b)*1j\n        self.b=1+(c/b)*1j\n      elif equal(b,0):\n        self.a=(c/a)+0j\n        self.b=(c/a)+1j\n      else:\n        self.a=(c/b)*1j\n        self.b=(c/a)+0j\n\n\nclass Segment:\n  def __init__(self,a:Point,b:Point):\n    self.a=a\n    self.b=b\n\n\nclass Circle:\n  def __init__(self,p:Point,r:float):\n    self.p=p\n    self.r=r\n\n# \u5c04\u5f71(projection)\n# \u76f4\u7ddaL\u306b\u70b9p\u304b\u3089\u5f15\u3044\u305f\u5782\u7dda\u306e\u8db3\u3092\u6c42\u3081\u308b\ndef projection(L:Line,p:Point)->Point:\n  t=dot(p-L.a,L.a-L.b)/norm(L.a-L.b)\n  return L.a+(L.a-L.b)*t\n\n# \u53cd\u5c04(reflection)\n# \u76f4\u7ddaL\u3092\u5bfe\u79f0\u8ef8\u3068\u3057\u3066\u70b9p\u3068\u7dda\u5bfe\u79f0\u306e\u4f4d\u7f6e\u306b\u3042\u308b\u70b9\u3092\u6c42\u3081\u308b\ndef reflection(L:Line,p:Point)->Point:\n  return p+(projection(L,p)-p)*2\n\n# \u70b9\u306e\u56de\u8ee2\u65b9\u5411\ndef CounterClockWise(a:Point,b:Point,c:Point)->int:\n  p=b-a\n  q=c-a\n  \n  # a,b,c \u304c\u53cd\u6642\u8a08\u56de\u308a -> 1\n  # a,b,c \u304c\u6642\u8a08\u56de\u308a -> -1\n  # c,a,b \u304c\u3053\u306e\u9806\u3067\u540c\u4e00\u76f4\u7dda\u72b6 -> 2\n  # a,b,c \u304c\u3053\u306e\u9806\u3067\u540c\u4e00\u76f4\u7dda\u72b6 -> -2\n  # b,c,a \u304c\u3053\u306e\u9806\u3067\u540c\u4e00\u76f4\u7dda\u72b6 -> 0\n  \n  if cross(p,q)>eps:\n    return 1\n  if cross(p,q)<-eps:\n    return -1\n  if dot(p,q)<0:\n    return 2\n  if norm(p)<norm(q):\n    return -2\n  return 0\n\n\n# 2 \u76f4\u7dda\u306e\u76f4\u4ea4\u5224\u5b9a\ndef isOrthiogonal(a:Line,b:Line)->bool:\n  return equal(dot(a.b-a.a,b.b-b.a),0)\n\n# 2 \u76f4\u7dda\u306e\u5e73\u884c\u5224\u5b9a\ndef isParallel(a:Line,b:Line)->bool:\n  return equal(cross(a.b-a.a,b.b-b.a),0)\n\n# 2 \u7dda\u5206\u306e\u4ea4\u5dee\u5224\u5b9a\ndef isIntersect(s:Segment,t:Segment)->bool:\n  return CounterClockWise(s.a,s.b,t.a)*CounterClockWise(s.a,s.b,t.b)<=0 and CounterClockWise(t.a,t.b,s.a)*CounterClockWise(t.a,t.b,s.b)<=0\n\n# 2 \u76f4\u7dda\u306e\u4ea4\u70b9\ndef crossPoint(s:Line,t:Line)->Point:\n  d1=cross(s.b-s.a,t.b-t.a)\n  d2=cross(s.b-s.a,s.b-t.a)\n  if equal(abs(d1),0) and equal(abs(d2),0):\n    return t.a\n  return t.a+(t.b-t.a)*(d2/d1)\n\ndef distanceBetweenLineAndPoint(l:Segment,p:Point)->float:\n  return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a)\n\n# \u7dda\u5206l\u3068\u70b9p\u306e\u8ddd\u96e2\ndef distanceBetweenSegmentAndPoint(l:Segment,p:Point)->float:\n  if dot(l.b-l.a,p-l.a)<eps:\n    return abs(p-l.a)\n  if dot(l.a-l.b,p-l.b)<eps:\n    return abs(p-l.b)\n  return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a)\n\n# \u7dda\u5206s,t\u306e\u8ddd\u96e2\ndef distanceBetweenSegments(s:Segment,t:Segment)->float:\n  if(isIntersect(s,t)):\n    return 0\n  ans=distanceBetweenSegmentAndPoint(s,t.a)\n  ans=min(ans,distanceBetweenSegmentAndPoint(s,t.b))\n  ans=min(ans,distanceBetweenSegmentAndPoint(t,s.a))\n  ans=min(ans,distanceBetweenSegmentAndPoint(t,s.b))\n  return ans\n\n# \u591a\u89d2\u5f62\u306e\u9762\u7a4d\ndef PolygonArea(p:List[Point])->float:\n  res=0\n  n=len(p)\n  for i in range(n):\n    res+=cross(p[i],p[(i+1)%n])\n  return res/2\n\n# \u51f8\u5224\u5b9a\ndef isConvex(p:List[Point])->float:\n  # p \u306f\u53cd\u6642\u8a08\u56de\u308a\n  n=len(p)\n  for i in range(n):\n    if CounterClockWise(p[(i-1)%n],p[i],p[(i+1)%n])==-1:\n      return False\n  return True\n\n# \u591a\u89d2\u5f62 g \u306b\u70b9 p \u304c\u542b\u307e\u308c\u308b\u304b\ndef isContained(g:List[Point],p:Point)->int:\n  # \u542b\u3080:2,\u8fba\u4e0a:1,\u542b\u307e\u306a\u3044:0\n  IN=False\n  n=len(g)\n  for i in range(n):\n    a=g[i]-p\n    b=g[(i+1)%n]-p\n    if a.imag>b.imag:\n      a,b=b,a\n    if a.imag<=0 and 0<b.imag and cross(a,b)<0:\n      IN^=1\n    if cross(a,b)==0 and dot(a,b)<=0:\n      return 1\n  if IN:\n    return 2\n  return 0\n\n# \u51f8\u5305\ndef ConvexHull(g:List[Point])->List[Point]:        \n  g.sort(key=cmp_to_key(cmp))\n  CH=[]\n  n=len(g)\n  for p in g:\n    # \u540c\u4e00\u76f4\u7dda\u4e0a\u306e3\u70b9\u3092\u542b\u3081\u308b -> (<-eps)\n    # \u542b\u3081\u306a\u3044 -> (<eps)\n    while len(CH)>1 and cross(CH[-1]-CH[-2],p-CH[-1])<-eps:\n      CH.pop()\n    CH.append(p)\n  t=len(CH)\n  for i in range(n-2,-1,-1):\n    p=g[i]\n    while len(CH)>t and cross(CH[-1]-CH[-2],p-CH[-1])<-eps:\n      CH.pop()\n    CH.append(p)\n  return CH[:-1]\n\n# \u51f8\u591a\u89d2\u5f62\u306e\u76f4\u5f84\ndef ConvexDiameter(p:List[Point])->float:\n  n=len(p)\n  i0,j0=0,0\n  for i in range(1,n):\n    if p[i].imag>p[i0].imag:\n      i0=i\n    if p[i].imag<p[j0].imag:\n      j0=i\n  \n  mx=abs(p[i0]-p[j0])\n  i=i0\n  j=j0\n  while i!=j0 or j!=i0:\n    if(cross(p[(i+1)%n]-p[i],p[(j+1)%n]-p[j])>=0):\n      j=(j+1)%n\n    else:\n      i=(i+1)%n\n    if abs(p[i]-p[j])>mx:\n      mx=abs(p[i]-p[j])\n  return mx\n\n\n# \u51f8\u591a\u89d2\u5f62\u306e\u5207\u65ad\n# \u76f4\u7dda L.a-L.b \u3067\u5207\u65ad\u3057\u3066\uff0c\u305d\u306e\u5de6\u5074\u306e\u51f8\u591a\u89d2\u5f62\u3092\u8fd4\u3059\ndef ConvexCut(P:List[Point],L:Line)->List[Point]:\n  ret=[]\n  n=len(P)\n  for i in range(n):\n    now,nxt=P[i],P[(i+1)%n]\n    if CounterClockWise(L.a,L.b,now)!=-1:\n      ret.append(now)\n    if CounterClockWise(L.a,L.b,now)*CounterClockWise(L.a,L.b,nxt)<0:\n      ret.append(crossPoint(Line(now,nxt),L))\n  return ret\n\n\n# \u5186\u306e\u4ea4\u5dee\u5224\u5b9a\ndef IsIntersectCircle(c1:Circle,c2:Circle)->int:\n  d=abs(c1.p-c2.p)\n  \n  # 2 \u5186\u304c\u96e2\u308c\u3066\u3044\u308b\n  if d>c1.r+c2.r+eps:\n    return 4\n  # \u5916\u63a5\n  if equal(d,c1.r+c2.r):\n    return 3\n  # \u5185\u63a5\n  if equal(d,abs(c1.r-c2.r)):\n    return 1\n  # \u5185\u5305\n  if d<abs(c1.r-c2.r)-eps:\n    return 0\n  # 2 \u4ea4\u70b9\u3092\u6301\u3064\n  return 2\n\n# \u4e09\u89d2\u5f62\u306e\u5185\u5fc3\ndef InscribedCircle(a:Point,b:Point,c:Point)->Circle:\n  A,B,C=abs(b-c),abs(c-a),abs(b-a)\n  p=point(A*a.real+B*b.real+C*c.real,A*a.imag+B*b.imag+C*c.imag)\n  p/=(A+B+C)\n  r=distanceBetweenSegmentAndPoint(Line(a,b),p)\n  return Circle(p,r)\n\n# \u4e09\u89d2\u5f62\u306e\u5916\u5fc3\ndef CircumscribedCircle(a:Point,b:Point,c:Point)->Circle:\n  p=(a-b)*norm(c)+(b-c)*norm(a)+(c-a)*norm(b)\n  p/=(a-b)*c.conjugate()+(b-c)*a.conjugate()+(c-a)*b.conjugate()\n  r=abs(p-a)\n  return Circle(p,r)\n\n# \u5186C\u3068\u76f4\u7ddaL\u306e\u4ea4\u70b9\ndef CrossPoint_Circle_Line(C:Circle,L:Line)->List[Point]:\n  res=[]\n  d=distanceBetweenLineAndPoint(L,C.p)\n  if d>C.r+eps:\n    return res\n  h=projection(L,C.p)\n  if equal(d,C.r):\n    return [h]\n  e=unitVector(L.b-L.a)\n  ph=sqrt(C.r**2-d**2)\n  res.append(h-e*ph)\n  res.append(h+e*ph)\n  return res\n\n# 2 \u5186\u306e\u4ea4\u70b9\ndef CrossPointCircles(C1:Circle,C2:Circle)->List[Point]:\n  res=[]\n  mode=IsIntersectCircle(C1,C2)\n  d=abs(C1.p-C2.p)\n  if mode==4 or mode==0:\n    return res\n  if mode==3:\n    t=C1.r/(C1.r+C2.r)\n    res.append(C1.p+(C2.p-C1.p)*t)\n    return res\n  if mode==1:\n    if C2.r<C1.r-eps:\n      res.append(C1.p+(C2.p-C1.p)*(C1.r/d))\n    else:\n      res.append(C2.p+(C1.p-C2.p)*(C2.r/d))\n    return res\n  rc1=(C1.r**2+d**2-C2.r**2)/(2*d)\n  rs1=sqrt(C1.r**2-rc1**2)\n  if C1.r-abs(rc1)<eps:\n    rs1=0\n  e12=(C2.p-C1.p)/abs(C2.p-C1.p)\n  res.append(C1.p+rc1*e12+rs1*e12*point(0,1))\n  res.append(C1.p+rc1*e12+rs1*e12*point(0,-1))\n  return res\n\n# \u70b9p\u3092\u901a\u308b\u5186c\u306e\u63a5\u7dda\ndef tangentToCircle(p:Point,c:Circle)->List[Point]:\n  return CrossPointCircles(c,Circle(p,sqrt(norm(c.p-p)-c.r**2)))\n\n# 2\u5186\u306e\u5171\u901a\u63a5\u7dda\ndef tangent(c1:Circle,c2:Circle)->List[Line]:\n  res=[]\n  d=abs(c1.p-c2.p)\n  if equal(d,0):\n    return []\n  u=unitVector(c2.p-c1.p)\n  v=rotate(u,pi/2)\n  for s in [-1,1]:\n    h=(c1.r+c2.r*s)/d\n    if equal(h**2,1):\n      res.append(Line(c1.p+h*u*c1.r,c1.p+h*u*c1.r+v))\n    elif 1-h*h>0:\n      U=u*h\n      V=v*sqrt(1-h*h)\n      res.append(Line(c1.p+(U+V)*c1.r,c2.p-(U+V)*c2.r*s))\n      res.append(Line(c1.p+(U-V)*c1.r,c2.p-(U-V)*c2.r*s))\n  return res\n\nwhile True:\n  solve()\n", "from heapq import heappop, heappush\n\ndef cross(a,b):\n    return a[0]*b[1]-a[1]*b[0]\n\ndef calc(r1,r2):\n    a = ((r1[0]-r2[0])**2+(r1[1]-r2[1])**2)**0.5\n    b = r1[2]\n    c = r2[2]\n    cos = (a**2+b**2-c**2)/(2*a*b)\n    s = b*cos\n    t = (b**2-s**2)**0.5\n    e = ((r2[0]-r1[0])/a,(r2[1]-r1[1])/a)\n    h = (-e[1],e[0])\n    return [[r1[0]+s*e[0]+t*h[0], r1[1]+s*e[1]+t*h[1]],[r1[0]+s*e[0]-t*h[0], r1[1]+s*e[1]-t*h[1]]]\n\ndef check(a,b,s,t):\n    v = (b[0]-a[0],b[1]-a[1])\n    v1 = (s[0]-a[0],s[1]-a[1])\n    v2 = (t[0]-a[0],t[1]-a[1])\n    if cross(v,v1)*cross(v,v2) > 0:\n        return 0\n    v = (t[0]-s[0],t[1]-s[1])\n    v1 = (a[0]-s[0],a[1]-s[1])\n    v2 = (b[0]-s[0],b[1]-s[1])\n    if cross(v,v1)*cross(v,v2) > 0:\n        return 0\n    return 1\n\ndef dijkstra(m,v):\n    dist = [float(\"inf\")]*m\n    q = [(0,0)]\n    dist[0] = 0\n    while q:\n        dx,x = heappop(q)\n        for y,d in v[x]:\n            if dist[y] > dx+d:\n                dist[y] = dx+d\n                heappush(q,(dx+d,y))\n    return dist[m-1]\ndef solve(n):\n    r = [[int(x) for x in input().split()] for i in range(n)]\n    p = [[r[0][0],r[0][1]]]\n    for i in range(n-1):\n        p += calc(r[i],r[i+1])\n    p.append([r[-1][0],r[-1][1]])\n    m = 2*n\n    v = [[] for i in range(m)]\n    gate = []\n    for i in range(1,n):\n        gate.append([p[2*i-1],p[2*i]])\n\n    for i in range(m):\n        x = p[i]\n        for j in range(i+1,m):\n            y = p[j]\n            for g1,g2 in gate[(i-1)//2+1:(j-1)//2]:\n                if not check(x,y,g1,g2):\n                    break\n            else:\n                d = ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5\n                v[i].append((j,d))\n                v[j].append((i,d))\n    print(dijkstra(m,v))\n\nwhile 1:\n    n = int(input())\n    if n == 0:\n        break\n    solve(n)\n\n", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\neps = 1.0 / 10**13\nmod = 10**9+7\ndd = [(-1,0),(0,1),(1,0),(0,-1)]\nddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]\n\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\ndef pf(s): return print(s, flush=True)\n\ndef _kosa(a1, a2, b1, b2):\n    x1,y1 = a1\n    x2,y2 = a2\n    x3,y3 = b1\n    x4,y4 = b2\n\n    tc = (x1-x2)*(y3-y1)+(y1-y2)*(x1-x3)\n    td = (x1-x2)*(y4-y1)+(y1-y2)*(x1-x4)\n    return tc*td < 0\n\ndef kosa(a1, a2, b1, b2):\n    return _kosa(a1,a2,b1,b2) and _kosa(b1,b2,a1,a2)\n\ndef distance(x1, y1, x2, y2):\n    return math.sqrt((x1-x2)**2 + (y1-y2)**2)\n\ndef distance_p(a, b):\n    return distance(a[0], a[1], b[0], b[1])\n\ndef polar(a, r):\n    return (math.cos(r) * a, math.sin(r) * a)\n\ndef intersection_c(ap, bp):\n    ax,ay,ar = ap\n    bx,by,br = bp\n    d = distance(ax,ay,bx,by)\n    if d > ar + br or d < abs(ar - br):\n        return None\n\n    ac = math.acos((ar**2 + d**2 - br**2) / (2 * ar * d))\n    t = math.atan2(by - ay, bx - ax)\n    r1 = polar(ar, t + ac)\n    r2 = polar(ar, t - ac)\n    return [(ax+r1[0], ay+r1[1]), (ax+r2[0], ay+r2[1])]\n\ndef main():\n    rr = []\n\n    def f(n):\n        a = [LI() for _ in range(n)]\n        inters = []\n        for i in range(n-1):\n            inters.append(intersection_c(a[i], a[i+1]))\n        dp = [[inf]*2 for _ in range(n-1)]\n        s = a[0][:2]\n        rt = a[-1][:2]\n        rf = True\n        for k in range(n-1):\n            if not kosa(s,rt,inters[k][0],inters[k][1]):\n                rf = False\n                break\n        if rf:\n            return distance_p(s,rt)\n\n        for i in range(n-1):\n            for j in range(2):\n                t = inters[i][j]\n                f = True\n                for k in range(i):\n                    if not kosa(s,t, inters[k][0], inters[k][1]):\n                        f = False\n                        break\n                if f:\n                    dp[i][j] = distance_p(s,t)\n\n        r = inf\n        # print('dp', dp)\n        for i in range(n-1):\n            for j in range(2):\n                s = inters[i][j]\n                sd = dp[i][j]\n                for k in range(i+1,n-1):\n                    for l in range(2):\n                        t = inters[k][l]\n                        f = True\n                        for m in range(i+1,k):\n                            if not kosa(s,t,inters[m][0], inters[m][1]):\n                                f = False\n                                break\n                        # print('s,t,f',s,t,f)\n                        if f:\n                            nd = sd + distance_p(s,t)\n                            if dp[k][l] > nd:\n                                dp[k][l] = nd\n                t = a[-1][:2]\n                f = True\n                for k in range(i+1,n-1):\n                    if not kosa(s,t,inters[k][0], inters[k][1]):\n                        f = False\n                        break\n                if f:\n                    nd = sd + distance_p(s,t)\n                    if r > nd:\n                        r = nd\n            # print('i',i,inters[i])\n            # print('dp', dp)\n            # print('r', r)\n        return '{:0.5f}'.format(r)\n\n    while 1:\n        n = I()\n        if n == 0:\n            break\n        rr.append(f(n))\n\n    return '\\n'.join(map(str,rr))\n\n\nprint(main())\n\n", "inf = 10**10\nfrom heapq import heappop, heappush\ndef Intersection(x1, y1, r1, x2, y2, r2):\n    d = ((x1 - x2)**2 + (y1 - y2)**2)**(1/2)\n    x, y = x2 - x1, y2 - y1\n    x, y = x / d, y / d \n    costheta = (r1**2 + d**2 - r2**2) / (2 * r1 * d)\n    sintheta = (1 - costheta**2)**(1/2)\n    x_, y_ = x1 + r1 * (x * costheta - y * sintheta), y1 + r1 * (x * sintheta + y * costheta)\n    x__, y__ = x1 + r1 * (x * costheta + y * sintheta), y1 + r1 * ((-x) * sintheta + y * costheta)\n    return x_, y_, x__, y__\n\ndef calc(x1, y1, x2, y2):\n    return ((x1 - x2)**2 + (y1 - y2)**2)**(1/2)\n\ndef judge(idx, x1, y1, x2, y2):\n    x3, y3 = Intersection_list[idx][0]\n    x4, y4 = Intersection_list[idx][1]\n    f1 = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)\n    f2 = (x2 - x1)*(y4 - y1) - (y2 - y1)*(x4 - x1)\n    f = f1 * f2\n    if f <= 0:\n        return True\n    return False\n\ndef dijkstra(s, graph):\n    d = [inf]*(2*n)\n    d[s] = 0\n    h = [(0,s)]\n    while h:\n        c,v = heappop(h)\n        if d[v] < c:\n            continue\n        for t,cost in graph[v]:\n            if d[v] + cost < d[t]:\n                d[t] = d[v] + cost\n                heappush(h,(d[t],t))\n    return d\n\nres = []\nwhile 1:\n    n = int(input())\n    if n == 0:\n        break\n    xyr = [list(map(int, input().split())) for _ in range(n)]\n    Intersection_list = [[] for _ in range(n-1)]\n    for i in range(n-1):\n        x1, y1, r1 = xyr[i]\n        x2, y2, r2 = xyr[i+1]\n        x_, y_, x__, y__ = Intersection(x1, y1, r1, x2, y2, r2)\n        Intersection_list[i].append([x_, y_])\n        Intersection_list[i].append([x__, y__])\n    ans = inf\n    edges = [[] for _ in range(2*n)]\n    for i in range(n):\n        if i == 0:\n            xi1, yi1 = xyr[0][0], xyr[0][1]\n            for j in range(i, n-1):\n                xj1, yj1 = Intersection_list[j][0]\n                for k in range(i, j+1):\n                    if not judge(k, xi1, yi1, xj1, yj1):\n                        break\n                else:\n                    dist = calc(xi1, yi1, xj1, yj1)\n                    edges[0].append((2*j+1, dist))\n                xj2, yj2 = Intersection_list[j][1]\n                for k in range(i, j+1):\n                    if not judge(k, xi1, yi1, xj2, yj2):\n                        break\n                else:\n                    dist = calc(xi1, yi1, xj2, yj2)\n                    edges[0].append((2*(j+1), dist))\n        else:\n            xi1, yi1 = Intersection_list[i-1][0]\n            for j in range(i, n-1):\n                xj1, yj1 = Intersection_list[j][0]\n                for k in range(i, j):\n                    if not judge(k, xi1, yi1, xj1, yj1):\n                        break\n                else:\n                    dist = calc(xi1, yi1, xj1, yj1)\n                    edges[2*i-1].append((2*j+1, dist))\n                xj2, yj2 = Intersection_list[j][1]\n                for k in range(i, j):\n                    if not judge(k, xi1, yi1, xj2, yj2):\n                        break\n                else:\n                    dist = calc(xi1, yi1, xj2, yj2)\n                    edges[2*i-1].append((2*(j+1), dist))\n            xi2, yi2 = Intersection_list[i-1][1]\n            for j in range(i, n-1):\n                xj1, yj1 = Intersection_list[j][0]\n                for k in range(i, j):\n                    if not judge(k, xi2, yi2, xj1, yj1):\n                        break\n                else:\n                    dist = calc(xi2, yi2, xj1, yj1)\n                    edges[2*i].append((2*j+1, dist))\n                xj2, yj2 = Intersection_list[j][1]\n                for k in range(i, j):\n                    if not judge(k, xi2, yi2, xj2, yj2):\n                        break\n                else:\n                    dist = calc(xi2, yi2, xj2, yj2)\n                    edges[2*i].append((2*(j+1), dist))\n    x, y = xyr[-1][0], xyr[-1][1]\n    for i in range(n):\n        if i == 0:\n            xi1, yi1 = xyr[0][0], xyr[0][1]\n            for j in range(n-1):\n                if not judge(j, x, y, xi1, yi1):\n                    break\n            else:\n                dist = calc(x, y, xi1, yi1)\n                edges[0].append((2*n-1, dist))\n\n        else:\n            xi1, yi1 = Intersection_list[i-1][0]\n            for j in range(i, n-1):\n                if not judge(j, x, y, xi1, yi1):\n                    break\n            else:\n                dist = calc(x, y, xi1, yi1)\n                edges[2*i-1].append((2*n-1, dist))\n            xi2, yi2 = Intersection_list[i-1][1]\n            for j in range(i, n-1):\n                if not judge(j, x, y, xi2, yi2):\n                    break\n            else:\n                dist = calc(x, y, xi2, yi2)\n                edges[2*i].append((2*n-1, dist))\n            \n    d = dijkstra(0, edges)\n    ans = d[2*n-1]\n    \n    res.append(ans)\n\nfor i in res:\n    print(i)\n\n\n\n\n", "import sys\ninput=sys.stdin.buffer.readline\nimport heapq\ndef cross(a,b,c,x,y,r):\n    d=abs(a*x+b*y+c)\n    A=(a*d-b*((a**2+b**2)*r**2-d**2)**.5)/(a**2+b**2)+x,(b*d+a*((a**2+b**2)*r**2-d**2)**.5)/(a**2+b**2)+y\n    B=(a*d+b*((a**2+b**2)*r**2-d**2)**.5)/(a**2+b**2)+x,(b*d-a*((a**2+b**2)*r**2-d**2)**.5)/(a**2+b**2)+y\n    return A,B\ndef solve(a,b):\n    x1,y1,r1=a\n    x2,y2,r2=b\n    a,b,c=2*(x2-x1),2*(y2-y1),(x1+x2)*(x1-x2)+(y1+y2)*(y1-y2)+(r2+r1)*(r2-r1)\n    return cross(a,b,c,x1,y1,r1)\ndef f(p1,p2,p3):\n    return (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])\ndef intersect(p1,p2,p3,p4):\n    if p1==p3 or p1==p4 or p2==p3 or p2==p4:return True\n    t1=f(p1,p2,p3)\n    t2=f(p1,p2,p4)\n    t3=f(p3,p4,p1)\n    t4=f(p3,p4,p2)\n    return t1*t2<0>t3*t4\ndef dist(p1,p2):\n    x1,y1=p1\n    x2,y2=p2\n    return((x1-x2)**2+(y1-y2)**2)**.5\ndef main():\n    res=[]\n    while 1:\n        n=int(input())\n        if n==0:break\n        z=[[*map(int,input().split())]for _ in range(n)]\n        c=[solve(z[i],z[i+1])for i in range(n-1)]\n        m=(n-1)*3+1\n        e=[[]for _ in range(m)]\n        for i in range(n-1):\n            for j in range(i+1,n):\n                p1=z[i][:2]\n                p2=c[j-1][0]\n                if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                    e[i*3].append((dist(p1,p2),j*3-2))\n                p2=c[j-1][1]\n                if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                    e[i*3].append((dist(p1,p2),j*3-1))\n                p2=z[j][:2]\n                if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                    e[i*3].append((dist(p1,p2),j*3))\n                if i:\n                    p1=c[i-1][0]\n                    p2=c[j-1][0]\n                    if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                        e[i*3-2].append((dist(p1,p2),j*3-2))\n                    p2=c[j-1][1]\n                    if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                        e[i*3-2].append((dist(p1,p2),j*3-1))\n                    p2=z[j][:2]\n                    if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                        e[i*3-2].append((dist(p1,p2),j*3))\n                    p1=c[i-1][1]\n                    p2=c[j-1][0]\n                    if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                        e[i*3-1].append((dist(p1,p2),j*3-2))\n                    p2=c[j-1][1]\n                    if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                        e[i*3-1].append((dist(p1,p2),j*3-1))\n                    p2=z[j][:2]\n                    if all(intersect(p1,p2,p3,p4)for p3,p4 in c[i:j]):\n                        e[i*3-1].append((dist(p1,p2),j*3))\n        i=n-1\n        j=n-1\n        p1=c[i-1][0]\n        p2=z[j][:2]\n        e[i*3-2].append((dist(p1,p2),j*3))\n        p1=c[i-1][1]\n        p2=z[j][:2]\n        e[i*3-1].append((dist(p1,p2),j*3))\n        d = [1e18] * m\n        used = [True] * m\n        d[0] = 0\n        used[0] = False\n        edgelist = []\n        for v in e[0]:\n            heapq.heappush(edgelist,v)\n        while edgelist:\n            minedge = heapq.heappop(edgelist)\n            if not used[minedge[1]]:\n                continue\n            v = minedge[1]\n            d[v] = minedge[0]\n            used[v] = False\n            for w in e[v]:\n                if used[w[1]]:\n                    heapq.heappush(edgelist,(w[0]+d[v],w[1]))\n        #print(e)\n        res.append(d[-1])\n    print('\\n'.join(map(str,res)))\nmain()\n", "import math\n\n\nclass Vec:\n    def __init__(self, x, y):\n        self.x = x\n        self.y = y\n\n    def __mul__(self, other):\n        return Vec(self.x * other, self.y * other)\n\n    def length(self):\n        return math.sqrt(self.x * self.x + self.y * self.y)\n\n    def __str__(self):\n        return \"({},{})\".format(self.x, self.y)\n\n    def __sub__(self, other):\n        return Vec(self.x - other.x, self.y - other.y)\n\n    def __add__(self, other):\n        return Vec(self.x + other.x, self.y + other.y)\n\n    def __truediv__(self, other):\n        return Vec(self.x / other, self.y / other)\n\n    def turn90(self):\n        return Vec(-self.y, self.x)\n\n    def normalized(self):\n        return self / self.length()\n\n    def is_clock(self, other):\n        return self.x * other.y - self.y * other.x < 0\n\n\nclass Circle:\n    def __init__(self, x, y, r):\n        self.r = r\n        self.center = Vec(x, y)\n\n    def intersection(self, other):\n        d = (self.center - other.center).length()\n        r1 = self.r\n        r2 = other.r\n        d1 = (d * d + r1 * r1 - r2 * r2) / 2 / d\n        x = math.sqrt(r1 * r1 - d1 * d1)\n        e1 = (other.center - self.center).normalized()\n        e2 = e1.turn90()\n\n        p1 = self.center + e1 * d1 + e2 * x\n        p2 = self.center + e1 * d1 - e2 * x\n        return p1, p2\n\n    def __str__(self):\n        return \"({},{})\".format(self.center, self.r)\n\n\ndef solve(ps: [Circle]):\n    intersects = []\n    for i in range(len(ps) - 1):\n        ci = ps[i]\n        ci_next = ps[i + 1]\n        intersection1, intersection2 = ci.intersection(ci_next)\n        intersects.append((intersection1, intersection2))\n\n    res = [[ps[0].center, -1, 0]]  # \u5019\u88dc\u5ea7\u6a19\u3068\u305d\u306e\u6df1\u5ea6\u3068\u5de6\u53f3(0,1)\n    dists = [[2 ** 32, 2 ** 32] for _ in range(len(intersects))]  # \u5404\u4ea4\u70b9\u306e\u8ddd\u96e2\u30d0\u30c3\u30d5\u30a1\n\n    min_path_length = 2 ** 32\n\n    while len(res) != 0:\n        res = sorted(res, key=lambda a: a[1], reverse=True)\n\n        c, depth, lr = res.pop()\n        current_path_length = dists[depth][lr] if depth != -1 else 0\n        if depth == len(intersects) - 1:\n            last_path = ps[-1].center - c\n            min_path_length = min(min_path_length, current_path_length + last_path.length())\n            continue\n\n        l_limit_min, r_limit_min = [a - c for a in intersects[depth + 1]]  # \u5de6\u53f3\u306e\u9650\u754c\n        l_limit, r_limit = l_limit_min, r_limit_min  # \u5230\u9054\u53ef\u80fd\u9650\u754c\n        l_limit_d, r_limit_d = depth + 1, depth + 1\n\n        flag = True\n        for i in range(depth + 2, len(intersects)):\n            l_limit2, r_limit2 = [a - c for a in intersects[i]]\n\n            if l_limit_min.is_clock(l_limit2):  # \u9650\u754c\u66f4\u65b0\n                l_limit_min = l_limit2\n                if l_limit2.is_clock(r_limit_min):  # \u5230\u9054\u53ef\u80fd\u306a\u3089\u3001\u3053\u3063\u3061\u3082\u66f4\u65b0\n                    l_limit = l_limit2\n                    l_limit_d = i\n            if r_limit2.is_clock(r_limit_min):  # \u9650\u754c\u66f4\u65b0\n                r_limit_min = r_limit2\n                if l_limit_min.is_clock(r_limit2):  # \u5230\u9054\u53ef\u80fd\u306a\u3089\u3001\u3053\u3063\u3061\u3082\u66f4\u65b0\n                    r_limit = r_limit2\n                    r_limit_d = i\n            if r_limit_min.is_clock(l_limit_min):\n                flag = False\n                break\n        last_path = ps[-1].center - c\n        if flag and l_limit_min.is_clock(last_path) and last_path.is_clock(r_limit_min):  # \u3053\u306e\u70b9\u304b\u3089\u30b4\u30fc\u30eb\u307e\u3067\u884c\u3051\u308b\n            min_path_length = min(min_path_length, current_path_length + last_path.length())\n            continue\n        if dists[l_limit_d][0] > l_limit.length() + current_path_length:\n            dists[l_limit_d][0] = l_limit.length() + current_path_length\n            res.append([l_limit + c, l_limit_d, 0])\n        if dists[r_limit_d][1] > r_limit.length() + current_path_length:\n            dists[r_limit_d][1] = r_limit.length() + current_path_length\n            res.append([r_limit + c, r_limit_d, 1])\n    return min_path_length\n\n\ndef main():\n    while True:\n        n = int(input())\n        if n == 0:\n            break\n\n        ps = [Circle(*[int(a) for a in input().split()]) for _ in range(n)]\n\n        print(solve(ps))\n\n\nif __name__ == '__main__':\n    main()\n\n"]

source: aizu

question:
Chain-Confined Path

There is a chain consisting of multiple circles on a plane.
The first (last) circle of the chain only intersects with the next (previous) circle,
and each intermediate circle intersects only with the two neighboring circles.

Your task is to find the shortest path that satisfies the following conditions.

- The path connects the centers of the first circle and the last circle.
- The path is confined in the chain, that is, all the points on the path are located within or on at least one of the circles.

Figure E-1 shows an example of such a chain and the corresponding shortest path.

![image](1.png)

Figure E-1: An  example chain and the corresponding shortest path

Input

The input consists of multiple datasets.
Each dataset represents the shape of a chain in the following format.

n
x_{1} y_{1} r_{1}
x_{2} y_{2} r_{2}
...
x_{n} y_{n} r_{n}

The first line of a dataset contains an integer n (3 ≤ n ≤ 100)
representing the number of the circles.
Each of the following n lines contains three integers separated by a single space.
(x_{i}, y_{i})
and r_{i} represent
the center position and the radius of the i-th circle C_{i}.
You can assume that 0 ≤ x_{i} ≤ 1000,
0 ≤ y_{i} ≤ 1000, and
1 ≤ r_{i} ≤ 25.

You can assume that C_{i}  and
C_{i+1}  (1 ≤ i ≤ n−1) intersect at two separate points.
When j ≥ i+2, C_{i}  and C_{j}  are apart and either of them does not contain the other.
In addition, you can assume that any circle does not contain the center of any other circle.

The end of the input is indicated by a line containing a zero.

Figure E-1 corresponds to the first dataset of Sample Input below.
Figure E-2 shows the shortest paths for the subsequent datasets of Sample Input.

![image](2.png)

Figure E-2: Example chains and the corresponding shortest paths

Output

For each dataset, output a single line containing the length of the shortest chain-confined path between the centers of the first circle and the last circle.
The value should not have an error greater than 0.001.
No extra characters should appear in the output.

Sample Input

10
802 0 10
814 0 4
820 1 4
826 1 4
832 3 5
838 5 5
845 7 3
849 10 3
853 14 4
857 18 3
3
0 0 5
8 0 5
8 8 5
3
0 0 5
7 3 6
16 0 5
9
0 3 5
8 0 8
19 2 8
23 14 6
23 21 6
23 28 6
19 40 8
8 42 8
0 39 5
11
0 0 5
8 0 5
18 8 10
8 16 5
0 16 5
0 24 5
3 32 5
10 32 5
17 28 8
27 25 3
30 18 5
0

Output for the Sample Input

58.953437
11.414214
16.0
61.874812
63.195179

image_tags:
2D Geometry
2D Geometry

data_split: test