S_XY += (X[i] - avg_X) * (Y[i] - avg_Y)
return (S_XY / n)
-##----------------------------------
+##---------------------------------------------------------------------
## variance : variance
## param X data vector ( ..x_i.. )
## (S_X)^2 = (Sum ( x_i - avg(x) )^2 ) / n
-##----------------------------------
+##---------------------------------------------------------------------
def variance (X):
n = len(X)
avg_X = avg (X)
S_X2 += (X[i] - avg_X) ** 2
return (S_X2 / n)
+##---------------------------------------------------------------------
+## calibrate : output correction factors, c_lat on latency, c_bw on bw
+## such that bandwidth * c_bw = bw_regr, latency * c_lat = lat_regr
+## where bw_regr and lat_regr are the values approximating experimental
+## observations.
+##
+## param links number of links traversed during ping-pong
+## param latency as specified on command line, in s
+## param bandwidth as specified on command line, in Byte/s
+## param sizes vector of data sizes, in Bytes
+## param timings vector of time taken: timings[i] for sizes[i], in us
+##---------------------------------------------------------------------
def calibrate (links, latency, bandwidth, sizes, timings):
assert len(sizes) == len(timings)
if len(sizes) < 2:
return None
+ # compute linear regression : find an affine form time = a*size+b
S_XY = cov(sizes, timings)
S_X2 = variance(sizes)
a = S_XY / S_X2
b = avg(timings) - a * avg(sizes)
- return (b * 1e-6) / (latency * links), 1e6 / (a * bandwidth)
+ # corresponding bandwith, in byte/s (was in byte/us in skampi dat)
+ bw_regr = 1e6 / a
+ # corresponding latency, in s (was in us in skampi dat)
+ lat_regr = b*1e-6
+ print("\nregression: {0} * x + {1}".format(a,b))
+ print("corr_bw = bw_regr/bandwidth= {0}/{1}={2} lat_regr/(lat_xml*links)={3}/({4}*{5}))".format(bw_regr,bandwidth,bw_regr/bandwidth,lat_regr,latency,links))
+ # return linear regression result and corresponding correction factors c_bw,c_lat
+ return a,b, bw_regr/bandwidth, lat_regr/(latency*links)
+
+
+##---------------------------------------------------------------------
+## outputs a C formatted conditional return value for factor
+##
+## param lb lower bound
+## param ub upper bound
+## param lb_included boolean to tell if bound is included (<=) or exclude (<)
+## param ub_included boolean to tell if bound is included (<=) or exclude (<)
+##---------------------------------------------------------------------
+def c_code_print (lb,ub, retval, lb_included, ub_included):
+ lb_cmp = ub_cmp = "<"
+ if lb_included:
+ lb_cmp ="<="
+ if ub_included:
+ ub_cmp ="<="
+
+ ub_kib=ub/1024.
+ lb_kib=lb/1024.
+ print("\t /* case {0:.1f} KiB {1} size {2} {3:.1f} KiB */".format(lb_kib,lb_cmp,ub_cmp,ub_kib))
+ print("\t if ({0:d} {1} size && size {2} {3:d}) ".format(lb,lb_cmp,ub_cmp,ub))
+ print("\t return({0});" . format(retval))
+
##-----------------------------------------------------------------------------------------------
## main
## ---------------
#count= 8388608 8388608 144916.1 7.6 32 144916.1 143262.0
#("%s %d %d %f %f %d %f %f\n" % (countlbl, count, countn, time, stddev, iter, mini, maxi)
- readdata.append( (int(l[1]),float(l[3]) / 2 ) ); # divide by 2 because of ping-pong measured
+ readdata.append( (int(l[1]),float(l[3]) / 2) ); # divide by 2 because of ping-pong measured
## These may not be sorted so sort it by message size before processing.
sorteddata = sorted( readdata, key=lambda pair: pair[0])
-sizes,timings = zip(*sorteddata);
+sizes,timings= zip(*sorteddata)
## adds message sizes of interest: if values are specified starting from the 6th command line arg
limits += [idx for idx in range(len(sizes)) if sizes[idx] == int(sys.argv[i])]
limits.append(len(sizes) - 1)
+factors = []
low = 0
for lim in limits:
correc = calibrate(links, latency, bandwidth, sizes[low:lim + 1], timings[low:lim + 1])
if correc:
- print("Segment [%d:%d] -- Latency factor=%g -- Bandwidth factor=%g" % (sizes[low], sizes[lim], correc[0], correc[1]))
+ # save interval [lb,ub] correction, regression line direction and origin
+ # and corresponding correction factors for bw and lat resp.
+ (dircoef,origin,factor_bw,factor_lat) = correc
+ factors.append( (sizes[low],sizes[lim], dircoef, origin, factor_bw,factor_lat) )
+ print("Segment [%d:%d] --Bandwidth factor=%g --Latency factor=%g " % (sizes[low], sizes[lim], factor_bw,factor_lat))
low = lim + 1
+
+# now computes joining lines between segments
+joinseg=[]
+
+print("\n/**\n *------------------ <copy/paste C code snippet in surf/network.c> ----------------------")
+print(" *\n * produced by: {0}\n *".format(' '.join(sys.argv)))
+print(" *---------------------------------------------------------------------------------------\n **/")
+
+# print correction factor for bandwidth for each segment
+print("static double smpi_bandwidth_factor(double size)\n{")
+for (lb,ub,a,b,factor_bw,factor_lat) in factors:
+ c_code_print(lb,ub,factor_bw,True,True)
+
+ # save ends and starts of segments
+ if lb != sizes[0]:
+ joinseg.append( (lb,timings[sizes.index(lb)]) )
+ if ub != sizes[-1]:
+ joinseg.append( (ub,timings[sizes.index(ub)]) )
+
+# print correction factor for bandwidth between segments
+joinseg.reverse()
+print("\n\t /* ..:: inter-segment corrections ::.. */");
+inx=len(joinseg)-1
+while inx>=1:
+ (x0,y0) = joinseg[inx]
+ inx = inx -1
+ (x1,y1) = joinseg[inx]
+ inx = inx -1
+ # line eq. is y = (y1-y0)/(x0-x1) * x + (y0 x1 - y1 x0)/(x1-x0)
+ a = (y1-y0) / (x1-x0)
+ bw_join = 1e6 / a
+ factor_join_bw = bw_join / bandwidth
+ #print("Joining points (%f,%f) -> (%f,%f) : line dir : a=%g\n" % (x0,y0,x1,y1,a))
+ c_code_print(x0,x1,factor_join_bw,False,False)
+
+print("}\n")
+
+# print correction factor for latency for each segment
+print("static double smpi_latency_factor(double size)\n{")
+for (lb,ub,a,b,factor_bw,factor_lat) in factors:
+ c_code_print(lb,ub,factor_lat,True,True)
+
+print("\n\t /* ..:: inter-segment corrections ::.. */");
+while joinseg:
+ (x0,y0) = joinseg.pop()
+ (x1,y1) = joinseg.pop()
+ # line eq. is y = (y0-y1)/(x0-x1) * x + (y0 x1 - y1 x0)/(x1-x0)
+ #print("(%f,%f) -> (%f,%f)\n" % (x0,y0,x1,y1))
+ b = 1e-6 * (y0*x1-y1*x0) / (x1-x0)
+ factor_join_lat = b / (latency*links)
+ c_code_print(x0,x1,factor_join_lat,False,False)
+
+print("}\n")
+
+print("\n/**\n *------------------ <copy/paste C code snippet in surf/network.c> ----------------------\n **/")
--- /dev/null
+# SkaMPI pt2pt test
+# on cluster : griffon (nancy) Grid5000. See Grid5000 website for technical data.
+
+#vendor_id : GenuineIntel
+#cpu family : 6
+#model : 23
+#model name : Intel(R) Xeon(R) CPU L5420 @ 2.50GHz
+#stepping : 10
+#cpu MHz : 2493.757
+#cache size : 6144 KB
+
+
+# /home/sgenaud/openmpi.install/bin/mpiexec --mca btl_tcp_if_include eth0 --mca btl_tcp_if_exclude ib0 --mca btl tcp,self -mca orte_base_help_aggregate 0 -mca plm_rsh_agent oarsh -machinefile machinefile -n 2 skampi -i ski_smpi/skampi_pt2pt.ski
+
+# Finished at Fri Jul 9 16:19:24 2010
+# SKaMPI Version 5.0.4 rev. 355
+# Started at Fri Jul 9 16:19:02 2010
+# Total runtime 22 seconds
+# begin result "Pingpong_Send_Recv"
+# duration = 22.49 sec
+# end result "Pingpong_Send_Recv"
+
+count= 1 1 109.2 0.2 32 106.7 107.7
+count= 2 2 109.3 0.3 32 107.6 107.0
+count= 4 4 111.7 0.7 32 107.8 109.7
+count= 8 8 109.0 0.3 32 106.8 107.0
+count= 16 16 109.1 0.4 32 108.0 106.7
+count= 32 32 111.1 0.4 32 110.5 107.4
+count= 64 64 110.2 0.2 32 107.8 108.6
+count= 128 128 118.9 1.2 32 109.9 116.2
+count= 256 256 145.8 0.4 32 138.4 144.9
+count= 512 512 161.7 0.3 32 154.7 161.6
+count= 1024 1024 190.4 0.2 32 182.7 190.4
+count= 1024 1024 193.4 0.3 32 185.9 193.0
+count= 1536 1536 237.3 0.5 32 226.9 237.3
+count= 2048 2048 248.0 0.8 32 238.4 247.9
+count= 2048 2048 249.2 1.0 32 240.1 247.7
+count= 2560 2560 262.9 0.6 32 251.7 262.9
+count= 3072 3072 277.9 0.4 32 272.7 275.0
+count= 3584 3584 285.0 0.5 32 275.0 285.0
+count= 4096 4096 303.0 0.9 32 293.5 298.9
+count= 4096 4096 303.4 0.8 32 297.2 301.6
+count= 4608 4608 310.0 0.8 32 310.0 291.7
+count= 5120 5120 321.4 0.7 32 321.4 291.5
+count= 5632 5632 343.7 0.7 32 343.7 312.0
+count= 6144 6144 320.7 0.5 32 320.7 282.6
+count= 6656 6656 339.4 0.4 32 339.4 296.6
+count= 7168 7168 353.3 0.7 32 353.3 308.5
+count= 7680 7680 386.7 0.8 32 385.3 378.8
+count= 8192 8192 389.1 0.6 32 389.1 373.8
+count= 8192 8192 393.7 0.8 32 391.1 380.4
+count= 16384 16384 627.7 0.7 32 627.7 533.9
+count= 32768 32768 1060.2 0.9 32 1060.2 828.9
+count= 32768 32768 1062.0 1.0 32 1062.0 836.4
+count= 33792 33792 1096.1 0.8 32 1096.1 838.2
+count= 34816 34816 1109.6 0.7 32 1109.6 835.3
+count= 35840 35840 1125.7 1.7 32 1125.7 856.3
+count= 36864 36864 1168.1 1.4 32 1168.1 930.2
+count= 37888 37888 1208.8 0.6 32 1208.8 937.2
+count= 38912 38912 1229.7 1.0 32 1229.7 952.2
+count= 39936 39936 1255.4 1.2 32 1255.4 969.3
+count= 40960 40960 1292.8 0.9 32 1292.8 978.8
+count= 41984 41984 1300.8 1.6 32 1300.8 976.3
+count= 43008 43008 1322.0 1.2 32 1322.0 988.2
+count= 44032 44032 1365.8 1.0 32 1365.8 1064.5
+count= 45056 45056 1400.6 0.8 32 1400.6 1072.9
+count= 46080 46080 1426.9 0.9 32 1426.9 1096.7
+count= 47104 47104 1445.7 0.9 32 1445.7 1101.4
+count= 48128 48128 1489.7 0.9 32 1489.7 1119.3
+count= 49152 49152 1516.2 0.6 32 1516.2 1137.3
+count= 50176 50176 1515.0 0.9 32 1515.0 1124.5
+count= 51200 51200 1558.4 1.4 32 1558.4 1202.6
+count= 52224 52224 1595.4 0.8 32 1595.4 1209.2
+count= 53248 53248 1614.3 1.0 32 1614.3 1219.8
+count= 54272 54272 1647.7 0.8 32 1647.7 1244.3
+count= 55296 55296 1684.2 0.9 32 1684.2 1258.9
+count= 56320 56320 1714.6 0.8 32 1714.6 1281.8
+count= 57344 57344 1710.3 1.4 32 1710.3 1262.5
+count= 58368 58368 1757.1 1.1 32 1757.1 1344.3
+count= 59392 59392 1793.4 1.3 32 1793.4 1350.9
+count= 60416 60416 1817.8 0.7 32 1817.8 1366.0
+count= 61440 61440 1850.5 1.5 32 1850.5 1392.2
+count= 62464 62464 1884.3 1.3 32 1884.3 1398.8
+count= 63488 63488 1896.7 1.2 32 1896.7 1403.7
+count= 64512 64512 1907.1 1.0 32 1907.1 1405.3
+count= 65536 65536 2250.0 1.2 32 2250.0 1648.1
+count= 65536 65536 2253.6 1.8 32 2253.6 1653.3
+count= 66560 66560 2263.2 0.8 32 2263.2 1654.2
+count= 67584 67584 2284.4 1.4 32 2284.4 1655.7
+count= 68608 68608 2308.5 1.7 32 2308.5 1685.1
+count= 69632 69632 2299.3 2.7 32 2299.3 1672.3
+count= 70656 70656 2342.2 2.4 32 2342.2 1708.0
+count= 71680 71680 2385.5 2.4 32 2385.5 1733.6
+count= 72704 72704 2422.9 2.5 32 2422.9 1765.7
+count= 73728 73728 2441.9 1.7 32 2441.9 1783.1
+count= 74752 74752 2465.0 1.9 32 2465.0 1781.5
+count= 75776 75776 2482.6 2.5 32 2482.6 1806.1
+count= 76800 76800 2490.0 2.1 32 2490.0 1808.3
+count= 77824 77824 2503.4 2.8 32 2503.4 1815.1
+count= 78848 78848 2568.6 2.6 32 2568.6 1864.5
+count= 79872 79872 2618.4 2.2 32 2618.4 1897.0
+count= 80896 80896 2615.7 2.6 32 2615.7 1891.0
+count= 81920 81920 2641.5 2.1 32 2641.5 1919.9
+count= 82944 82944 2647.5 2.4 32 2647.5 1919.4
+count= 83968 83968 2662.6 1.8 32 2662.6 1929.4
+count= 84992 84992 2693.4 1.7 32 2693.4 1954.6
+count= 86016 86016 2733.1 2.3 32 2733.1 1974.2
+count= 87040 87040 2784.9 2.0 32 2784.9 2013.4
+count= 88064 88064 2792.3 1.9 32 2792.3 2014.1
+count= 89088 89088 2820.0 1.8 32 2820.0 2032.9
+count= 90112 90112 2833.6 1.7 32 2833.6 2045.1
+count= 91136 91136 2861.4 1.1 32 2861.4 2056.6
+count= 92160 92160 2873.4 1.5 32 2873.4 2071.6
+count= 93184 93184 2926.1 0.8 32 2926.1 2103.4
+count= 94208 94208 2960.6 1.8 32 2960.6 2128.3
+count= 95232 95232 2970.0 1.6 32 2970.0 2145.8
+count= 96256 96256 2993.8 1.7 32 2993.8 2147.2
+count= 97280 97280 3010.7 2.4 32 3010.7 2169.1
+count= 98304 98304 3039.6 1.7 32 3039.6 2180.1
+count= 99328 99328 3048.7 2.0 32 3048.7 2186.0
+count= 100352 100352 3107.2 1.4 32 3107.2 2227.0
+count= 101376 101376 3147.7 1.4 32 3147.7 2258.1
+count= 102400 102400 3145.7 1.8 32 3145.7 2256.1
+count= 103424 103424 3171.8 1.3 32 3171.8 2266.4
+count= 104448 104448 3200.2 2.4 32 3200.2 2300.5
+count= 105472 105472 3219.3 2.7 32 3219.3 2301.5
+count= 106496 106496 3229.6 2.1 32 3229.6 2308.6
+count= 107520 107520 3284.7 2.3 32 3284.7 2344.4
+count= 108544 108544 3311.8 2.2 32 3311.8 2364.9
+count= 109568 109568 3323.4 1.7 32 3323.4 2376.3
+count= 110592 110592 3354.0 2.0 32 3354.0 2399.0
+count= 111616 111616 3376.2 1.7 32 3376.2 2419.3
+count= 112640 112640 3397.4 2.4 32 3397.4 2429.9
+count= 113664 113664 3401.1 1.4 32 3401.1 2430.6
+count= 114688 114688 3458.1 2.7 32 3458.1 2470.8
+count= 115712 115712 3481.2 3.4 32 3481.2 2484.3
+count= 116736 116736 3512.1 2.2 32 3512.1 2502.9
+count= 117760 117760 3532.9 2.1 32 3532.9 2524.1
+count= 118784 118784 3544.9 1.9 32 3544.9 2527.8
+count= 119808 119808 3575.5 1.4 32 3575.5 2544.6
+count= 120832 120832 3584.4 2.2 32 3584.4 2554.0
+count= 121856 121856 3641.5 2.3 32 3641.5 2593.2
+count= 122880 122880 3662.0 1.7 32 3662.0 2608.6
+count= 123904 123904 3695.2 1.7 32 3695.2 2638.5
+count= 124928 124928 3711.6 1.6 32 3711.6 2643.5
+count= 125952 125952 3737.9 1.3 32 3737.9 2659.9
+count= 126976 126976 3750.0 1.8 32 3750.0 2673.3
+count= 128000 128000 3761.6 2.2 32 3761.6 2678.8
+count= 129024 129024 3822.9 1.8 32 3822.9 2725.9
+count= 130048 130048 3838.5 2.3 32 3838.5 2727.5
+count= 131072 131072 3870.2 1.8 32 3870.2 2750.0
+count= 131072 131072 3873.2 1.8 32 3873.2 2757.4
+count= 262144 262144 7121.5 1.0 32 7121.5 4980.9
+count= 524288 524288 10740.7 4.1 32 10740.7 9458.5
+count= 1048576 1048576 19872.8 4.9 32 19872.8 18373.7
+count= 2097152 2097152 37947.8 63.3 32 37947.8 36227.3
+count= 4194304 4194304 73299.4 7.8 32 73299.4 71898.5
+count= 8388608 8388608 144965.0 15.2 32 144965.0 143205.7
--- /dev/null
+0 98
+1 100
+2 100
+3 100
+4 100
+5 100
+6 100
+7 100
+8 100
+9 100
+10 100
+11 99
+12 97
+13 95
+14 90
+15 83
+16 82
+17 82
+18 82
+19 92
+20 87
+21 82
+22 76
+23 76
+24 89
+25 94
+26 97
+27 100
+28 100
+29 100
+30 100
+31 100
+32 100
+33 100
+34 100
+35 100
+36 100
+37 100
+38 100
+39 99
+40 96
+41 94
+42 89
+43 83
+44 82
+45 86
+46 94
+47 79
+48 76
+49 82
+50 84
+51 92
+52 97
+53 98
+54 100
+55 100
+56 100
+57 100
+58 100
+59 100
+60 100
+61 100
+62 100
+63 100
+64 100
+65 100
+66 99
+67 97
+68 94
+69 86
+70 82
+71 82
+72 91
+73 94
+74 90
+75 88
+76 89
+77 93
+78 97
+79 100
+80 100
+81 100
+82 100
+83 100
+84 100
+85 100
+86 100
+87 100
+88 100
+89 100
+90 100
+91 100
+92 99
+93 97
+94 94
+95 90
+96 82
+97 82
+98 87
+99 94
+100 93
+101 88
+102 90
+103 92
+104 98
+105 99
+106 100
+107 100
+108 100
+109 100
+110 100
+111 100
+112 100
+113 100
+114 100
+115 100
+116 99
+117 100
+118 100
+119 100
+120 99
+121 97
+122 95
+123 92
+124 90
+125 82
+126 82
+127 94
+128 86
+129 85
+130 95
+131 97
+132 99
+133 100
+134 100
+135 100
+136 100
+137 100
+138 100
+139 100
+140 100
+141 100
+142 100
+143 100
+144 100
+145 100
+146 100
+147 100
+148 98
+149 96
+150 94
+151 94
+152 87
+153 88
+154 94
+155 94
+156 92
+157 97
+158 98
+159 100
+160 100
+161 100
+162 100
+163 100
+164 100
+165 100
+166 100
+167 100
+168 100
+169 100
+170 100
+171 100
+172 100
+173 100
+174 100
+175 100
+176 98
+177 103
+178 84
+179 94
+180 87
+181 85
+182 97
+183 97
+184 99
+185 100
+186 100
+187 100
+188 100
+189 100
+190 100
+191 100
+192 100
+193 100
+194 100
+195 100
+196 100
+197 100
+198 100
+199 100
+200 100
+201 100
+202 99
+203 103
+204 93
+205 86
+206 95
+207 82
+208 96
+209 100
+210 98
+211 100
+212 100
+213 100
+214 100
+215 100
+216 100
+217 100
+218 100
+219 100
+220 100
+221 100
+222 100
+223 100
+224 100
+225 100
+226 100
+227 100
+228 100
+229 100
+230 102
+231 107
+232 94
+233 82
+234 94
+235 95
+236 101
+237 102
+238 100
+239 100
+240 100
+241 100
+242 100
+243 100
+244 100
+245 100
+246 100
+247 100
+248 100
+249 100
+250 100
+251 100
+252 100
+253 100
+254 100
+255 91
+256 84
+257 98
+258 103
+259 103
+260 100
+261 101
+262 100
+263 100
+264 100
+265 100
+266 100
+267 100
+268 100
+269 100
+270 100
+271 100
+272 100
+273 100
+274 100
+275 100
+276 100
+277 100
+278 100
+279 100
+280 109
+281 96
+282 99
+283 97
+284 92
+285 101
+286 103
+287 104
+288 102
+289 100
+290 100
+291 100
+292 100
+293 100
+294 100
+295 100
+296 100
+297 100
+298 100
+299 100
+300 100
+301 100
+302 100
+303 100
+304 100
+305 101
+306 103
+307 112
+308 98
+309 101
+310 101
+311 101
+312 104
+313 105
+314 107
+315 104
+316 100
+317 100
+318 100
+319 100
+320 100
+321 100
+322 100
+323 100
+324 100
+325 100
+326 100
+327 100
+328 100
+329 100
+330 100
+331 100
+332 100
+333 112
+334 112
+335 98
+336 108
+337 103
+338 99
+339 104
+340 106
+341 107
+342 106
+343 102
+344 100
+345 100
+346 100
+347 100
+348 100
+349 100
+350 100
+351 100
+352 100
+353 100
+354 100
+355 100
+356 100
+357 100
+358 100
+359 104
+360 111
+361 107
+362 111
+363 104
+364 107
+365 107
+366 104
+367 106
+368 106
+369 106
+370 101
+371 100
+372 100
+373 100
+374 100
+375 100
+376 100
+377 100
+378 100
+379 100
+380 100
+381 100
+382 100
+383 100
+384 100
+385 100
+386 106
+387 100
+388 100
+389 100
+390 110
+391 103
+392 109
+393 106
+394 105
+395 106
+396 107
+397 105
+398 101
+399 100
+400 100
+401 100
+402 100
+403 100
+404 100
+405 100
+406 100
+407 100
+408 100
+409 100
+410 100
+411 100
+412 100
+413 105
+414 112
+415 100
+416 100
+417 100
+418 107
+419 117
+420 114
+421 108
+422 106
+423 106
+424 107
+425 100
+426 100
+427 100
+428 101
+429 100
+430 100
+431 100
+432 100
+433 101
+434 106
+435 112
+436 113
+437 112
+438 113
+439 114
+440 117
+441 116
+442 107
+443 106
+444 107
+445 106
+446 102
+447 100
+448 100
+449 100
+450 100
+451 100
+452 100
+453 100
+454 100
+455 100
+456 100
+457 100
+458 100
+459 101
+460 100
+461 106
+462 113
+463 112
+464 101
+465 113
+466 118
+467 119
+468 116
+469 108
+470 107
+471 107
+472 107
+473 105
+474 100
+475 100
+476 100
+477 100
+478 100
+479 100
+480 100
+481 100
+482 100
+483 100
+484 100
+485 100
+486 100
+487 105
+488 112
+489 100
+490 113
+491 103
+492 119
+493 119
+494 119
+495 114
+496 107
+497 106
+498 106
+499 106
+500 104
+501 100
+502 100
+503 100
+504 100
+505 100
+506 100
+507 100
+508 100
+509 100
+510 100
+511 100
+512 100
+513 102
+514 104
+515 112
+516 112
+517 107
+518 113
+519 117
+520 119
+521 120
+522 120
+523 116
+524 109
+525 107
+526 106
+527 107
+528 104
+529 101
+530 100
+531 100
+532 100
+533 100
+534 100
+535 100
+536 100
+537 100
+538 100
+539 100
+540 100
+541 105
+542 100
+543 113
+544 112
+545 101
+546 115
+547 121
+548 121
+549 123
+550 121
+551 118
+552 112
+553 107
+554 106
+555 107
+556 106
+557 104
+558 100
+559 100
+560 100
+561 100
+562 100
+563 100
+564 100
+565 100
+566 100
+567 102
+568 110
+569 100
+570 112
+571 100
+572 112
+573 118
+574 120
+575 122
+576 123
+577 122
+578 119
+579 112
+580 107
+581 107
+582 107
+583 106
+584 102
+585 101
+586 100
+587 100
+588 100
+589 100
+590 100
+591 100
+592 100
+593 101
+594 101
+595 105
+596 100
+597 116
+598 118
+599 120
+600 121
+601 124
+602 106
+603 107
+604 104
+605 101
+606 100
+607 100
+608 100
+609 100
+610 100
+611 100
+612 101
+613 100
+614 101
+615 110
+616 100
+617 112
+618 112
+619 112
+620 119
+621 122
+622 124
+623 124
+624 122
+625 121
+626 114
+627 108
+628 107
+629 106
+630 106
+631 104
+632 100
+633 100
+634 100
+635 100
+636 100
+637 100
+638 100
+639 100
+640 100
+641 105
+642 111
+643 107
+644 100
+645 112
+646 113
+647 116
+648 121
+649 123
+650 125
+651 124
+652 122
+653 120
+654 114
+655 107
+656 107
+657 108
+658 106
+659 105
+660 102
+661 100
+662 100
+663 100
+664 100
+665 100
+666 100
+667 100
+668 100
+669 103
+670 106
+671 107
+672 106
+673 102
+674 117
+675 121
+676 123
+677 125
+678 125
+679 125
+680 122
+681 119
+682 113
+683 107
+684 106
+685 107
+686 107
+687 104
+688 100
+689 100
+690 101
+691 100
+692 100
+693 100
+694 102
+695 107
+696 111
+697 113
+698 111
+699 111
+700 116
+701 121
+702 122
+703 125
+704 125
+705 125
+706 123
+707 122
+708 115
+709 108
+710 107
+711 107
+712 106
+713 103
+714 100
+715 100
+716 101
+717 100
+718 100
+719 100
+720 102
+721 110
+722 106
+723 112
+724 113
+725 115
+726 120
+727 122
+728 123
+729 124
+730 125
+731 125
+732 123
+733 122
+734 119
+735 109
+736 108
+737 107
+738 106
+739 105
+740 101
+741 100
+742 100
+743 100
+744 100
+745 100
+746 100
+747 108
+748 115
+749 106
+750 110
+751 116
+752 107
+753 120
+754 123
+755 124
+756 125
+757 125
+758 125
+759 125
+760 124
+761 120
+762 121
+763 112
+764 107
+765 110
+766 106
+767 108
+768 100
+769 101
+770 101
+771 113
+772 108
+773 108
+774 106
+775 122
+776 125
+777 125
+778 125
+779 124
+780 124
+781 123
+782 121
+783 118
+784 112
+785 110
+786 107
+787 110
+788 102
+789 102
+790 100
+791 100
+792 100
+793 101
+794 103
+795 100
+796 100
+797 100
+798 113
+799 106
+800 113
+801 120
+802 124
+803 124
+804 125
+805 125
+806 125
+807 125
+808 124
+809 122
+810 123
+811 117
+812 110
+813 108
+814 111
+815 106
+816 106
+817 101
+818 100
+819 100
+820 100
+821 104
+822 100
+823 100
+824 117
+825 101
+826 108
+827 119
+828 120
+829 124
+830 125
+831 125
+832 125
+833 125
+834 125
+835 124
+836 121
+837 121
+838 116
+839 111
+840 104
+841 108
+842 107
+843 106
+844 103
+845 100
+846 101
+847 100
+848 101
+849 106
+850 112
+851 106
+852 106
+853 113
+854 116
+855 121
+856 124
+857 125
+858 125
+859 125
+860 124
+861 125
+862 125
+863 124
+864 123
+865 121
+866 114
+867 108
+868 107
+869 106
+870 107
+871 106
+872 101
+873 101
+874 100
+875 101
+876 108
+877 100
+878 112
+879 100
+880 113
+881 109
+882 121
+883 122
+884 124
+885 124
+886 125
+887 125
+888 124
+889 125
+890 125
+891 124
+892 122
+893 119
+894 114
+895 108
+896 106
+897 107
+898 107
+899 104
+900 100
+901 101
+902 103
+903 100
+904 112
+905 101
+906 106
+907 114
+908 117
+909 119
+910 123
+911 123
+912 125
+913 125
+914 125
+915 125
+916 124
+917 124
+918 125
+919 124
+920 122
+921 122
+922 115
+923 109
+924 107
+925 107
+926 107
+927 105
+928 103
+929 101
+930 101
+931 111
+932 107
+933 113
+934 101
+935 115
+936 118
+937 121
+938 122
+939 125
+940 125
+941 125
+942 125
+943 125
+944 124
+945 122
+946 120
+947 115
+948 110
+949 108
+950 108
+951 107
+952 100
+953 100
+954 112
+955 101
+956 113
+957 120
+958 122
+959 123
+960 125
+961 125
+962 125
+963 125
+964 125
+965 125
+966 125
+967 125
+968 124
+969 124
+970 122
+971 120
+972 114
+973 110
+974 107
+975 106
+976 106
+977 105
+978 106
+979 113
+980 113
+981 100
+982 108
+983 107
+984 119
+985 121
+986 124
+987 125
+988 125
+989 125
+990 124
+991 125
+992 125
+993 125
+994 125
+995 125
+996 124
+997 123
+998 122
+999 120
+1000 112
+1001 108
+1002 107
+1003 107
+1004 106
+1005 109
+1006 101
+1007 113
+1008 108
+1009 114
+1010 102
+1011 117
+1012 121
+1013 123
+1014 125
+1015 125
+1016 125
+1017 125
+1018 125
+1019 125
+1020 125
+1021 125
+1022 125
+1023 124
+1024 125
+1026 123
+1028 122
+1030 118
+1032 109
+1034 107
+1036 107
+1038 107
+1040 108
+1042 109
+1044 101
+1046 113
+1048 107
+1050 102
+1052 111
+1054 115
+1056 120
+1058 124
+1060 125
+1062 125
+1064 125
+1066 125
+1068 125
+1070 125
+1072 125
+1074 125
+1076 125
+1078 125
+1080 125
+1082 125
+1084 125
+1086 125
+1088 123
+1090 121
+1092 116
+1094 107
+1096 108
+1098 106
+1100 112
+1102 118
+1104 100
+1106 107
+1108 114
+1110 119
+1112 122
+1114 123
+1116 125
+1118 125
+1120 125
+1122 124
+1124 125
+1126 125
+1128 125
+1130 125
+1132 125
+1134 125
+1136 125
+1138 125
+1140 125
+1142 125
+1144 123
+1146 122
+1148 118
+1150 112
+1152 109
+1154 116
+1156 113
+1158 119
+1160 114
+1162 114
+1164 112
+1166 119
+1168 122
+1170 124
+1172 125
+1174 125
+1176 125
+1178 125
+1180 125
+1182 125
+1184 125
+1186 125
+1188 125
+1190 125
+1192 124
+1194 125
+1196 125
+1198 125
+1200 124
+1202 124
+1204 121
+1206 120
+1208 117
+1210 119
+1212 119
+1214 108
+1216 120
+1218 119
+1220 120
+1222 125
+1224 125
+1226 125
+1228 125
+1230 125
+1232 125
+1234 125
+1236 125
+1238 125
+1240 125
+1242 124
+1244 123
+1246 122
+1248 119
+1250 120
+1252 108
+1254 115
+1256 113
+1258 117
+1260 121
+1262 123
+1264 124
+1266 125
+1268 124
+1270 125
+1272 125
+1274 125
+1276 125
+1278 125
+1280 125
+1282 125
+1284 125
+1286 125
+1288 125
+1290 125
+1292 125
+1294 125
+1296 125
+1298 124
+1300 125
+1302 131
+1304 116
+1306 123
+1308 120
+1310 115
+1312 120
+1314 126
+1316 126
+1318 126
+1320 125
+1322 125
+1324 125
+1326 125
+1328 125
+1330 124
+1332 125
+1334 124
+1336 125
+1338 125
+1340 125
+1342 125
+1344 125
+1346 125
+1348 125
+1350 125
+1352 125
+1354 134
+1356 123
+1358 121
+1360 128
+1362 123
+1364 121
+1366 128
+1368 129
+1370 128
+1372 126
+1374 125
+1376 125
+1378 125
+1380 125
+1382 125
+1384 125
+1386 125
+1388 125
+1390 125
+1392 125
+1394 125
+1396 125
+1398 125
+1400 125
+1402 125
+1404 125
+1406 125
+1408 128
+1410 125
+1412 136
+1414 135
+1416 119
+1418 127
+1420 127
+1422 129
+1424 130
+1426 100
+1428 100
+1430 101
+1432 96
+1434 100
+1436 101
+1438 100
+1440 101
+1442 99
+1444 101
+1446 101
+1448 97
+1450 99
+1452 98
+1454 100
+1456 99
+1458 99
+1460 98
+1462 100
+1464 100
+1466 100
+1468 101
+1470 100
+1472 100
+1474 100
+1476 100
+1478 100
+1480 100
+1482 100
+1484 100
+1486 100
+1488 101
+1490 100
+1492 104
+1494 102
+1496 99
+1498 98
+1500 94
+1502 100
+1504 101
+1506 101
+1508 100
+1510 100
+1512 99
+1514 101
+1516 100
+1518 100
+1520 97
+1522 101
+1524 100
+1526 100
+1528 100
+1530 100
+1532 100
+1534 100
+1536 101
+1538 100
+1540 100
+1542 100
+1544 100
+1546 100
+1548 101
+1550 101
+1552 101
+1554 101
+1556 99
+1558 99
+1560 100
+1562 97
+1564 103
+1566 99
+1568 100
+1570 100
+1572 99
+1574 102
+1576 99
+1578 99
+1580 100
+1582 100
+1584 100
+1586 100
+1588 100
+1590 100
+1592 101
+1594 99
+1596 96
+1598 99
+1600 95
+1602 100
+1604 96
+1606 102
+1608 102
+1610 97
+1612 96
+1614 98
+1616 99
+1618 101
+1620 101
+1622 100
+1624 100
+1626 100
+1628 100
+1630 100
+1632 100
+1634 100
+1636 100
+1638 100
+1640 100
+1642 100
+1644 100
+1646 100
+1648 100
+1650 100
+1652 98
+1654 98
+1656 101
+1658 101
+1660 100
+1662 100
+1664 101
+1666 97
+1668 101
+1670 99
+1672 95
+1674 98
+1676 98
+1678 101
+1680 99
+1682 98
+1684 101
+1686 100
+1688 100
+1690 100
+1692 100
+1694 100
+1696 100
+1698 100
+1700 100
+1702 100
+1704 100
+1706 100
+1708 101
+1710 99
+1712 98
+1714 100
+1716 100
+1718 103
+1720 100
+1722 103
+1724 100
+1726 102
+1728 97
+1730 100
+1732 99
+1734 101
+1736 103
+1738 101
+1740 101
+1742 101
+1744 100
+1746 100
+1748 100
+1750 100
+1752 100
+1754 101
+1756 100
+1758 100
+1760 100
+1762 100
+1764 100
+1766 102
+1768 103
+1770 98
+1772 101
+1774 103
+1776 100
+1778 104
+1780 96
+1782 101
+1784 99
+1786 103
+1788 102
+1790 102
+1792 98
+1794 102
+1796 102
+1798 100
+1800 100
+1802 100
+1804 100
+1806 100
+1808 100
+1810 100
+1812 100
+1814 100
+1816 100
+1818 101
+1820 100
+1822 102
+1824 100
+1826 99
+1828 99
+1830 104
+1832 103
+1834 104
+1836 104
+1838 104
+1840 100
+1842 105
+1844 101
+1846 103
+1848 103
+1850 102
+1852 102
+1854 102
+1856 101
+1858 100
+1860 100
+1862 100
+1864 101
+1866 100
+1868 101
+1870 100
+1872 100
+1874 100
+1876 100
+1878 100
+1880 100
+1882 101
+1884 104
+1886 106
+1888 102
+1890 101
+1892 106
+1894 105
+1896 103
+1898 106
+1900 106
+1902 104
+1904 104
+1906 105
+1908 104
+1910 102
+1912 103
+1914 101
+1916 100
+1918 101
+1920 100
+1922 100
+1924 100
+1926 100
+1928 100
+1930 100
+1932 100
+1934 100
+1936 100
+1938 101
+1940 100
+1942 101
+1944 100
+1946 105
+1948 103
+1950 106
+1952 107
+1954 106
+1956 104
+1958 105
+1960 105
+1962 103
+1964 106
+1966 105
+1968 102
+1970 101
+1972 101
+1974 100
+1976 100
+1978 100
+1980 100
+1982 100
+1984 101
+1986 101
+1988 101
+1990 101
+1992 101
+1994 101
+1996 102
+1998 100
+2000 105
+2002 109
+2004 105
+2006 104
+2008 105
+2010 105
+2012 106
+2014 106
+2016 108
+2018 106
+2020 104
+2022 102
+2024 103
+2026 103
+2028 102
+2030 100
+2032 101
+2034 101
+2036 101
+2038 100
+2040 101
+2042 100
+2044 101
+2046 100
+2048 100
+2052 101
+2056 101
+2060 105
+2064 106
+2068 102
+2072 109
+2076 107
+2080 108
+2084 107
+2088 107
+2092 108
+2096 104
+2100 108
+2104 107
+2108 109
+2112 105
+2116 105
+2120 101
+2124 103
+2128 101
+2132 102
+2136 100
+2140 100
+2144 100
+2148 100
+2152 100
+2156 101
+2160 100
+2164 100
+2168 106
+2172 108
+2176 107
+2180 108
+2184 109
+2188 111
+2192 108
+2196 107
+2200 107
+2204 112
+2208 108
+2212 106
+2216 104
+2220 102
+2224 101
+2228 100
+2232 100
+2236 101
+2240 101
+2244 101
+2248 100
+2252 101
+2256 101
+2260 102
+2264 103
+2268 101
+2272 101
+2276 107
+2280 103
+2284 109
+2288 110
+2292 112
+2296 108
+2300 111
+2304 112
+2308 111
+2312 109
+2316 112
+2320 110
+2324 111
+2328 107
+2332 105
+2336 104
+2340 101
+2344 101
+2348 102
+2352 102
+2356 101
+2360 101
+2364 101
+2368 101
+2372 100
+2376 102
+2380 101
+2384 101
+2388 101
+2392 103
+2396 107
+2400 109
+2404 111
+2408 107
+2412 112
+2416 108
+2420 111
+2424 113
+2428 113
+2432 112
+2436 114
+2440 107
+2444 112
+2448 113
+2452 109
+2456 103
+2460 101
+2464 100
+2468 103
+2472 101
+2476 101
+2480 101
+2484 101
+2488 100
+2492 101
+2496 105
+2500 101
+2504 107
+2508 103
+2512 111
+2516 112
+2520 111
+2524 108
+2528 113
+2532 112
+2536 116
+2540 116
+2544 114
+2548 115
+2552 112
+2556 113
+2560 113
+2564 111
+2568 109
+2572 109
+2576 102
+2580 102
+2584 101
+2588 104
+2592 101
+2596 100
+2600 101
+2604 104
+2608 101
+2612 101
+2616 106
+2620 108
+2624 112
+2628 112
+2632 116
+2636 115
+2640 115
+2644 117
+2648 113
+2652 114
+2656 112
+2660 114
+2664 111
+2668 106
+2672 102
+2676 102
+2680 102
+2684 103
+2688 102
+2692 102
+2696 101
+2700 101
+2704 101
+2708 101
+2712 101
+2716 103
+2720 109
+2724 112
+2728 112
+2732 113
+2736 117
+2740 118
+2744 113
+2748 118
+2752 115
+2756 114
+2760 117
+2764 114
+2768 115
+2772 113
+2776 113
+2780 111
+2784 108
+2788 103
+2792 101
+2796 104
+2800 102
+2804 105
+2808 101
+2812 107
+2816 106
+2820 106
+2824 102
+2828 104
+2832 108
+2836 112
+2840 111
+2844 116
+2848 114
+2852 118
+2856 118
+2860 119
+2864 118
+2868 117
+2872 118
+2876 124
+2880 126
+2884 119
+2888 124
+2892 118
+2896 121
+2900 114
+2904 118
+2908 123
+2912 116
+2916 116
+2920 123
+2924 121
+2928 120
+2932 121
+2936 125
+2940 105
+2944 126
+2948 111
+2952 129
+2956 116
+2960 111
+2964 116
+2968 129
+2972 128
+2976 119
+2980 128
+2984 123
+2988 127
+2992 130
+2996 129
+3000 118
+3004 128
+3008 122
+3012 115
+3016 127
+3020 114
+3024 119
+3028 118
+3032 119
+3036 126
+3040 102
+3044 111
+3048 103
+3052 111
+3056 104
+3060 109
+3064 104
+3068 109
+3072 131
+3076 131
+3080 114
+3084 117
+3088 129
+3092 127
+3096 127
+3100 128
+3104 125
+3108 127
+3112 124
+3116 127
+3120 121
+3124 128
+3128 117
+3132 122
+3136 113
+3140 121
+3144 112
+3148 126
+3152 104
+3156 105
+3160 114
+3164 102
+3168 114
+3172 124
+3176 127
+3180 109
+3184 131
+3188 117
+3192 115
+3196 129
+3200 129
+3204 122
+3208 121
+3212 122
+3216 129
+3220 129
+3224 126
+3228 127
+3232 127
+3236 126
+3240 124
+3244 120
+3248 119
+3252 125
+3256 112
+3260 121
+3264 106
+3268 125
+3272 126
+3276 121
+3280 117
+3284 126
+3288 126
+3292 131
+3296 111
+3300 105
+3304 117
+3308 116
+3312 116
+3316 120
+3320 130
+3324 129
+3328 126
+3332 128
+3336 129
+3340 127
+3344 121
+3348 125
+3352 115
+3356 127
+3360 126
+3364 127
+3368 111
+3372 121
+3376 131
+3380 118
+3384 111
+3388 131
+3392 132
+3396 132
+3400 130
+3404 128
+3408 127
+3412 129
+3416 128
+3420 125
+3424 127
+3428 129
+3432 126
+3436 120
+3440 125
+3444 126
+3448 116
+3452 131
+3456 124
+3460 129
+3464 117
+3468 130
+3472 130
+3476 133
+3480 102
+3484 133
+3488 135
+3492 115
+3496 131
+3500 120
+3504 120
+3508 123
+3512 124
+3516 126
+3520 129
+3524 132
+3528 129
+3532 129
+3536 127
+3540 130
+3544 123
+3548 129
+3552 132
+3556 127
+3560 129
+3564 129
+3568 121
+3572 131
+3576 117
+3580 135
+3584 121
+3588 131
+3592 112
+3596 121
+3600 136
+3604 119
+3608 123
+3612 119
+3616 121
+3620 132
+3624 131
+3628 129
+3632 127
+3636 132
+3640 128
+3644 131
+3648 127
+3652 129
+3656 130
+3660 128
+3664 133
+3668 124
+3672 125
+3676 122
+3680 128
+3684 120
+3688 116
+3692 114
+3696 127
+3700 112
+3704 125
+3708 127
+3712 114
+3716 136
+3720 136
+3724 135
+3728 133
+3732 133
+3736 134
+3740 133
+3744 128
+3748 129
+3752 127
+3756 129
+3760 131
+3764 132
+3768 129
+3772 129
+3776 131
+3780 134
+3784 128
+3788 123
+3792 126
+3796 126
+3800 115
+3804 128
+3808 127
+3812 133
+3816 136
+3820 114
+3824 138
+3828 122
+3832 128
+3836 140
+3840 116
+3844 127
+3848 134
+3852 136
+3856 131
+3860 129
+3864 128
+3868 129
+3872 132
+3876 131
+3880 128
+3884 130
+3888 131
+3892 132
+3896 131
+3900 127
+3904 130
+3908 127
+3912 134
+3916 123
+3920 129
+3924 135
+3928 128
+3932 118
+3936 117
+3940 142
+3944 132
+3948 124
+3952 138
+3956 139
+3960 136
+3964 131
+3968 132
+3972 132
+3976 127
+3980 130
+3984 130
+3988 129
+3992 129
+3996 132
+4000 132
+4004 132
+4008 130
+4012 133
+4016 132
+4020 136
+4024 128
+4028 131
+4032 121
+4036 130
+4040 138
+4044 142
+4048 121
+4052 132
+4056 123
+4060 130
+4064 123
+4068 134
+4072 135
+4076 135
+4080 134
+4084 132
+4088 131
+4092 131
+4096 131
+4104 136
+4112 131
+4120 137
+4128 135
+4136 128
+4144 128
+4152 131
+4160 120
+4168 143
+4176 144
+4184 143
+4192 143
+4200 126
+4208 139
+4216 138
+4224 136
+4232 133
+4240 133
+4248 137
+4256 132
+4264 135
+4272 133
+4280 135
+4288 132
+4296 134
+4304 131
+4312 131
+4320 131
+4328 143
+4336 148
+4344 141
+4352 140
+4360 136
+4368 137
+4376 138
+4384 136
+4392 142
+4400 139
+4408 140
+4416 136
+4424 140
+4432 141
+4440 133
+4448 140
+4456 138
+4464 146
+4472 139
+4480 139
+4488 141
+4496 138
+4504 139
+4512 138
+4520 136
+4528 140
+4536 146
+4544 146
+4552 145
+4560 145
+4568 143
+4576 139
+4584 140
+4592 141
+4600 141
+4608 146
+4616 146
+4624 140
+4632 137
+4640 144
+4648 138
+4656 140
+4664 139
+4672 140
+4680 143
+4688 144
+4696 142
+4704 142
+4712 140
+4720 142
+4728 141
+4736 137
+4744 139
+4752 140
+4760 141
+4768 141
+4776 142
+4784 145
+4792 146
+4800 140
+4808 146
+4816 138
+4824 141
+4832 144
+4840 136
+4848 142
+4856 146
+4864 143
+4872 147
+4880 140
+4888 143
+4896 146
+4904 146
+4912 144
+4920 145
+4928 142
+4936 142
+4944 139
+4952 143
+4960 139
+4968 140
+4976 142
+4984 144
+4992 145
+5000 139
+5008 145
+5016 147
+5024 140
+5032 146
+5040 148
+5048 140
+5056 140
+5064 144
+5072 142
+5080 143
+5088 143
+5096 145
+5104 146
+5112 144
+5120 147
+5128 142
+5136 146
+5144 147
+5152 143
+5160 141
+5168 142
+5176 140
+5184 137
+5192 140
+5200 144
+5208 144
+5216 143
+5224 143
+5232 144
+5240 147
+5248 143
+5256 146
+5264 140
+5272 146
+5280 146
+5288 142
+5296 2984
+5304 1277
+5312 142
+5320 286
+5328 239
+5336 267
+5344 211
+5352 140
+5360 141
+5368 144
+5376 145
+5384 145
+5392 148
+5400 144
+5408 149
+5416 146
+5424 150
+5432 143
+5440 144
+5448 149
+5456 148
+5464 145
+5472 146
+5480 146
+5488 147
+5496 146
+5504 143
+5512 141
+5520 145
+5528 137
+5536 145
+5544 143
+5552 142
+5560 143
+5568 146
+5576 145
+5584 148
+5592 145
+5600 145
+5608 145
+5616 149
+5624 143
+5632 150
+5640 150
+5648 148
+5656 145
+5664 147
+5672 146
+5680 148
+5688 149
+5696 148
+5704 150
+5712 147
+5720 149
+5728 144
+5736 146
+5744 147
+5752 140
+5760 148
+5768 211
+5776 147
+5784 151
+5792 150
+5800 151
+5808 149
+5816 146
+5824 153
+5832 159
+5840 146
+5848 154
+5856 151
+5864 149
+5872 152
+5880 147
+5888 150
+5896 149
+5904 151
+5912 149
+5920 148
+5928 151
+5936 150
+5944 150
+5952 150
+5960 150
+5968 148
+5976 149
+5984 148
+5992 147
+6000 148
+6008 150
+6016 150
+6024 150
+6032 149
+6040 146
+6048 158
+6056 144
+6064 149
+6072 147
+6080 152
+6088 153
+6096 149
+6104 151
+6112 150
+6120 150
+6128 149
+6136 149
+6144 150
+6152 151
+6160 151
+6168 151
+6176 150
+6184 150
+6192 151
+6200 150
+6208 149
+6216 149
+6224 151
+6232 151
+6240 153
+6248 153
+6256 152
+6264 148
+6272 150
+6280 150
+6288 153
+6296 151
+6304 152
+6312 149
+6320 152
+6328 148
+6336 150
+6344 151
+6352 152
+6360 151
+6368 150
+6376 153
+6384 153
+6392 151
+6400 151
+6408 151
+6416 150
+6424 151
+6432 151
+6440 152
+6448 151
+6456 153
+6464 152
+6472 151
+6480 151
+6488 155
+6496 155
+6504 155
+6512 158
+6520 155
+6528 154
+6536 152
+6544 154
+6552 152
+6560 152
+6568 151
+6576 153
+6584 152
+6592 152
+6600 152
+6608 153
+6616 151
+6624 151
+6632 153
+6640 151
+6648 154
+6656 152
+6664 153
+6672 151
+6680 151
+6688 160
+6696 160
+6704 151
+6712 152
+6720 155
+6728 158
+6736 153
+6744 158
+6752 878
+6760 157
+6768 780
+6776 152
+6784 175
+6792 154
+6800 153
+6808 154
+6816 156
+6824 152
+6832 157
+6840 155
+6848 158
+6856 159
+6864 158
+6872 155
+6880 154
+6888 150
+6896 154
+6904 155
+6912 154
+6920 154
+6928 151
+6936 153
+6944 152
+6952 152
+6960 152
+6968 154
+6976 154
+6984 151
+6992 153
+7000 154
+7008 157
+7016 157
+7024 156
+7032 156
+7040 153
+7048 160
+7056 158
+7064 156
+7072 156
+7080 157
+7088 161
+7096 162
+7104 156
+7112 156
+7120 158
+7128 157
+7136 155
+7144 155
+7152 157
+7160 155
+7168 152
+7176 153
+7184 152
+7192 155
+7200 152
+7208 154
+7216 177
+7224 157
+7232 158
+7240 156
+7248 160
+7256 155
+7264 158
+7272 155
+7280 155
+7288 156
+7296 157
+7304 154
+7312 162
+7320 160
+7328 158
+7336 161
+7344 162
+7352 163
+7360 161
+7368 162
+7376 164
+7384 161
+7392 162
+7400 160
+7408 162
+7416 162
+7424 161
+7432 161
+7440 161
+7448 157
+7456 156
+7464 157
+7472 154
+7480 160
+7488 156
+7496 156
+7504 162
+7512 157
+7520 156
+7528 161
+7536 160
+7544 164
+7552 162
+7560 163
+7568 163
+7576 164
+7584 164
+7592 163
+7600 162
+7608 164
+7616 162
+7624 161
+7632 162
+7640 163
+7648 163
+7656 160
+7664 161
+7672 162
+7680 161
+7688 157
+7696 160
+7704 161
+7712 156
+7720 157
+7728 155
+7736 162
+7744 156
+7752 161
+7760 159
+7768 162
+7776 164
+7784 163
+7792 165
+7800 167
+7808 166
+7816 165
+7824 165
+7832 165
+7840 164
+7848 164
+7856 166
+7864 166
+7872 163
+7880 164
+7888 163
+7896 162
+7904 165
+7912 157
+7920 155
+7928 163
+7936 160
+7944 163
+7952 162
+7960 163
+7968 162
+7976 160
+7984 162
+7992 164
+8000 165
+8008 166
+8016 166
+8024 164
+8032 168
+8040 168
+8048 167
+8056 166
+8064 167
+8072 167
+8080 167
+8088 166
+8096 164
+8104 165
+8112 166
+8120 167
+8128 168
+8136 164
+8144 161
+8152 162
+8160 167
+8168 167
+8176 165
+8184 165
+8192 164
+8208 165
+8224 168
+8240 167
+8256 168
+8272 169
+8288 167
+8304 167
+8320 168
+8336 167
+8352 166
+8368 167
+8384 166
+8400 169
+8416 166
+8432 170
+8448 170
+8464 167
+8480 167
+8496 167
+8512 168
+8528 159
+8544 168
+8560 168
+8576 168
+8592 169
+8608 169
+8624 169
+8640 171
+8656 170
+8672 172
+8688 172
+8704 173
+8720 171
+8736 171
+8752 170
+8768 173
+8784 169
+8800 171
+8816 168
+8832 170
+8848 170
+8864 171
+8880 171
+8896 169
+8912 171
+8928 166
+8944 170
+8960 166
+8976 169
+8992 172
+9008 173
+9024 173
+9040 172
+9056 172
+9072 173
+9088 172
+9104 172
+9120 173
+9136 172
+9152 172
+9168 172
+9184 173
+9200 173
+9216 172
+9232 172
+9248 170
+9264 173
+9280 174
+9296 175
+9312 174
+9328 173
+9344 173
+9360 173
+9376 240
+9392 244
+9408 244
+9424 243
+9440 249
+9456 250
+9472 247
+9488 244
+9504 251
+9520 250
+9536 250
+9552 259
+9568 252
+9584 250
+9600 251
+9616 250
+9632 251
+9648 250
+9664 251
+9680 250
+9696 250
+9712 251
+9728 250
+9744 251
+9760 251
+9776 251
+9792 251
+9808 250
+9824 250
+9840 252
+9856 251
+9872 251
+9888 251
+9904 251
+9920 251
+9936 252
+9952 251
+9968 251
+9984 251
+10000 251
+10016 251
+10032 251
+10048 251
+10064 251
+10080 251
+10096 250
+10112 251
+10128 277
+10144 274
+10160 276
+10176 275
+10192 275
+10208 275
+10224 278
+10240 276
+10256 274
+10272 277
+10288 279
+10304 277
+10320 275
+10336 277
+10352 280
+10368 277
+10384 272
+10400 275
+10416 281
+10432 279
+10448 278
+10464 279
+10480 279
+10496 275
+10512 277
+10528 278
+10544 279
+10560 280
+10576 282
+10592 281
+10608 277
+10624 278
+10640 281
+10656 279
+10672 280
+10688 277
+10704 277
+10720 279
+10736 280
+10752 277
+10768 279
+10784 274
+10800 278
+10816 282
+10832 277
+10848 276
+10864 283
+10880 283
+10896 282
+10912 280
+10928 281
+10944 283
+10960 281
+10976 283
+10992 282
+11008 280
+11024 282
+11040 280
+11056 285
+11072 283
+11088 369
+11104 279
+11120 282
+11136 280
+11152 279
+11168 281
+11184 285
+11200 283
+11216 277
+11232 283
+11248 284
+11264 282
+11280 280
+11296 280
+11312 284
+11328 279
+11344 284
+11360 281
+11376 282
+11392 281
+11408 280
+11424 278
+11440 282
+11456 283
+11472 282
+11488 280
+11504 281
+11520 284
+11536 282
+11552 293
+11568 283
+11584 296
+11600 279
+11616 277
+11632 282
+11648 302
+11664 293
+11680 285
+11696 279
+11712 285
+11728 280
+11744 279
+11760 282
+11776 278
+11792 282
+11808 285
+11824 281
+11840 281
+11856 280
+11872 281
+11888 281
+11904 307
+11920 281
+11936 283
+11952 286
+11968 281
+11984 283
+12000 296
+12016 279
+12032 285
+12048 286
+12064 294
+12080 297
+12096 307
+12112 277
+12128 277
+12144 281
+12160 283
+12176 308
+12192 286
+12208 281
+12224 291
+12240 286
+12256 279
+12272 304
+12288 290
+12304 298
+12320 282
+12336 278
+12352 290
+12368 278
+12384 281
+12400 281
+12416 288
+12432 280
+12448 298
+12464 302
+12480 310
+12496 280
+12512 282
+12528 302
+12544 304
+12560 306
+12576 278
+12592 279
+12608 301
+12624 286
+12640 283
+12656 280
+12672 286
+12688 280
+12704 286
+12720 313
+12736 279
+12752 281
+12768 307
+12784 294
+12800 304
+12816 285
+12832 280
+12848 316
+12864 302
+12880 289
+12896 286
+12912 328
+12928 294
+12944 281
+12960 312
+12976 294
+12992 335
+13008 298
+13024 320
+13040 292
+13056 319
+13072 282
+13088 307
+13104 285
+13120 283
+13136 290
+13152 293
+13168 325
+13184 281
+13200 310
+13216 284
+13232 286
+13248 284
+13264 301
+13280 309
+13296 286
+13312 285
+13328 316
+13344 309
+13360 287
+13376 298
+13392 292
+13408 319
+13424 300
+13440 284
+13456 320
+13472 304
+13488 332
+13504 312
+13520 303
+13536 293
+13552 321
+13568 288
+13584 296
+13600 286
+13616 311
+13632 322
+13648 287
+13664 324
+13680 313
+13696 334
+13712 319
+13728 288
+13744 287
+13760 340
+13776 297
+13792 284
+13808 322
+13824 339
+13840 328
+13856 288
+13872 335
+13888 297
+13904 286
+13920 294
+13936 285
+13952 290
+13968 332
+13984 286
+14000 338
+14016 290
+14032 297
+14048 348
+14064 290
+14080 288
+14096 340
+14112 332
+14128 291
+14144 330
+14160 327
+14176 307
+14192 311
+14208 294
+14224 338
+14240 342
+14256 356
+14272 321
+14288 330
+14304 321
+14320 289
+14336 330
+14352 287
+14368 288
+14384 288
+14400 330
+14416 347
+14432 288
+14448 316
+14464 299
+14480 311
+14496 298
+14512 295
+14528 328
+14544 319
+14560 338
+14576 341
+14592 326
+14608 313
+14624 334
+14640 320
+14656 315
+14672 318
+14688 314
+14704 361
+14720 352
+14736 296
+14752 307
+14768 325
+14784 363
+14800 340
+14816 363
+14832 301
+14848 326
+14864 366
+14880 323
+14896 341
+14912 359
+14928 356
+14944 334
+14960 337
+14976 371
+14992 319
+15008 287
+15024 344
+15040 322
+15056 366
+15072 346
+15088 317
+15104 301
+15120 330
+15136 345
+15152 324
+15168 346
+15184 352
+15200 327
+15216 334
+15232 344
+15248 334
+15264 367
+15280 338
+15296 338
+15312 364
+15328 368
+15344 315
+15360 357
+15376 348
+15392 325
+15408 334
+15424 374
+15440 358
+15456 360
+15472 351
+15488 356
+15504 372
+15520 346
+15536 363
+15552 334
+15568 352
+15584 369
+15600 359
+15616 326
+15632 341
+15648 372
+15664 370
+15680 374
+15696 366
+15712 368
+15728 369
+15744 349
+15760 355
+15776 368
+15792 354
+15808 366
+15824 346
+15840 342
+15856 363
+15872 371
+15888 347
+15904 324
+15920 368
+15936 367
+15952 373
+15968 367
+15984 372
+16000 364
+16016 372
+16032 356
+16048 372
+16064 371
+16080 372
+16096 366
+16112 370
+16128 363
+16144 371
+16160 374
+16176 352
+16192 359
+16208 364
+16224 359
+16240 362
+16256 330
+16272 369
+16288 322
+16304 362
+16320 381
+16336 370
+16352 375
+16368 374
+16384 372
+16416 378
+16448 373
+16480 373
+16512 372
+16544 380
+16576 377
+16608 372
+16640 371
+16672 376
+16704 374
+16736 363
+16768 372
+16800 373
+16832 375
+16864 379
+16896 383
+16928 381
+16960 376
+16992 374
+17024 373
+17056 381
+17088 373
+17120 385
+17152 373
+17184 383
+17216 378
+17248 376
+17280 376
+17312 385
+17344 384
+17376 383
+17408 383
+17440 387
+17472 379
+17504 393
+17536 382
+17568 379
+17600 391
+17632 390
+17664 383
+17696 384
+17728 388
+17760 388
+17792 382
+17824 388
+17856 394
+17888 388
+17920 388
+17952 383
+17984 385
+18016 379
+18048 390
+18080 394
+18112 387
+18144 392
+18176 385
+18208 396
+18240 388
+18272 393
+18304 386
+18336 480
+18368 402
+18400 398
+18432 395
+18464 399
+18496 390
+18528 392
+18560 388
+18592 392
+18624 391
+18656 389
+18688 393
+18720 385
+18752 395
+18784 390
+18816 393
+18848 393
+18880 389
+18912 392
+18944 391
+18976 390
+19008 392
+19040 396
+19072 389
+19104 389
+19136 393
+19168 394
+19200 390
+19232 390
+19264 399
+19296 392
+19328 394
+19360 397
+19392 396
+19424 389
+19456 392
+19488 395
+19520 397
+19552 399
+19584 395
+19616 403
+19648 397
+19680 396
+19712 396
+19744 397
+19776 398
+19808 389
+19840 396
+19872 401
+19904 401
+19936 399
+19968 398
+20000 401
+20032 395
+20064 399
+20096 395
+20128 401
+20160 394
+20192 396
+20224 397
+20256 394
+20288 396
+20320 396
+20352 392
+20384 402
+20416 409
+20448 392
+20480 396
+20512 390
+20544 392
+20576 394
+20608 397
+20640 393
+20672 399
+20704 393
+20736 411
+20768 396
+20800 400
+20832 394
+20864 399
+20896 398
+20928 398
+20960 400
+20992 413
+21024 398
+21056 396
+21088 416
+21120 397
+21152 395
+21184 411
+21216 400
+21248 396
+21280 397
+21312 398
+21344 393
+21376 400
+21408 418
+21440 401
+21472 396
+21504 399
+21536 398
+21568 397
+21600 399
+21632 396
+21664 399
+21696 399
+21728 410
+21760 412
+21792 415
+21824 410
+21856 405
+21888 409
+21920 411
+21952 408
+21984 415
+22016 396
+22048 409
+22080 412
+22112 411
+22144 415
+22176 412
+22208 410
+22240 412
+22272 414
+22304 415
+22336 412
+22368 417
+22400 411
+22432 413
+22464 419
+22496 413
+22528 415
+22560 409
+22592 414
+22624 413
+22656 421
+22688 411
+22720 408
+22752 414
+22784 414
+22816 400
+22848 395
+22880 413
+22912 421
+22944 416
+22976 416
+23008 417
+23040 416
+23072 395
+23104 415
+23136 417
+23168 421
+23200 416
+23232 410
+23264 411
+23296 412
+23328 410
+23360 398
+23392 412
+23424 411
+23456 412
+23488 412
+23520 407
+23552 412
+23584 415
+23616 411
+23648 411
+23680 413
+23712 409
+23744 411
+23776 418
+23808 414
+23840 410
+23872 410
+23904 417
+23936 414
+23968 414
+24000 413
+24032 412
+24064 419
+24096 411
+24128 421
+24160 416
+24192 417
+24224 414
+24256 413
+24288 414
+24320 418
+24352 416
+24384 409
+24416 418
+24448 412
+24480 421
+24512 417
+24544 421
+24576 418
+24608 434
+24640 428
+24672 430
+24704 430
+24736 434
+24768 438
+24800 432
+24832 434
+24864 429
+24896 432
+24928 430
+24960 434
+24992 428
+25024 432
+25056 435
+25088 434
+25120 424
+25152 429
+25184 433
+25216 433
+25248 426
+25280 430
+25312 434
+25344 429
+25376 439
+25408 432
+25440 440
+25472 434
+25504 431
+25536 436
+25568 441
+25600 436
+25632 449
+25664 449
+25696 443
+25728 437
+25760 439
+25792 441
+25824 441
+25856 442
+25888 451
+25920 448
+25952 450
+25984 443
+26016 434
+26048 457
+26080 461
+26112 456
+26144 457
+26176 464
+26208 450
+26240 465
+26272 451
+26304 455
+26336 467
+26368 463
+26400 453
+26432 456
+26464 456
+26496 455
+26528 463
+26560 447
+26592 455
+26624 455
+26656 462
+26688 457
+26720 466
+26752 465
+26784 460
+26816 458
+26848 454
+26880 458
+26912 463
+26944 453
+26976 477
+27008 455
+27040 460
+27072 471
+27104 475
+27136 459
+27168 488
+27200 464
+27232 459
+27264 472
+27296 469
+27328 461
+27360 476
+27392 465
+27424 473
+27456 472
+27488 484
+27520 482
+27552 491
+27584 482
+27616 471
+27648 480
+27680 481
+27712 482
+27744 484
+27776 476
+27808 486
+27840 484
+27872 485
+27904 494
+27936 478
+27968 478
+28000 490
+28032 478
+28064 481
+28096 480
+28128 478
+28160 487
+28192 487
+28224 481
+28256 491
+28288 479
+28320 495
+28352 486
+28384 480
+28416 480
+28448 501
+28480 478
+28512 491
+28544 489
+28576 472
+28608 497
+28640 483
+28672 494
+28704 474
+28736 491
+28768 494
+28800 503
+28832 490
+28864 503
+28896 500
+28928 493
+28960 495
+28992 492
+29024 496
+29056 487
+29088 498
+29120 491
+29152 491
+29184 502
+29216 489
+29248 489
+29280 488
+29312 497
+29344 506
+29376 495
+29408 494
+29440 491
+29472 504
+29504 498
+29536 501
+29568 512
+29600 496
+29632 488
+29664 489
+29696 503
+29728 502
+29760 490
+29792 502
+29824 494
+29856 510
+29888 501
+29920 1673
+29952 506
+29984 490
+30016 504
+30048 497
+30080 491
+30112 509
+30144 489
+30176 495
+30208 500
+30240 502
+30272 508
+30304 498
+30336 527
+30368 517
+30400 514
+30432 509
+30464 524
+30496 520
+30528 527
+30560 520
+30592 510
+30624 525
+30656 524
+30688 509
+30720 518
+30752 533
+30784 525
+30816 515
+30848 520
+30880 525
+30912 519
+30944 502
+30976 516
+31008 510
+31040 518
+31072 526
+31104 533
+31136 513
+31168 519
+31200 513
+31232 519
+31264 518
+31296 535
+31328 519
+31360 549
+31392 527
+31424 527
+31456 518
+31488 544
+31520 527
+31552 518
+31584 515
+31616 527
+31648 510
+31680 525
+31712 539
+31744 519
+31776 532
+31808 516
+31840 560
+31872 534
+31904 575
+31936 555
+31968 547
+32000 526
+32032 515
+32064 545
+32096 551
+32128 543
+32160 532
+32192 522
+32224 524
+32256 565
+32288 520
+32320 527
+32352 525
+32384 548
+32416 537
+32448 514
+32480 545
+32512 536
+32544 527
+32576 551
+32608 549
+32640 573
+32672 525
+32704 537
+32736 545
+32768 524
+32832 538
+32896 538
+32960 534
+33024 563
+33088 528
+33152 567
+33216 528
+33280 566
+33344 574
+33408 569
+33472 549
+33536 572
+33600 571
+33664 520
+33728 585
+33792 570
+33856 582
+33920 544
+33984 581
+34048 551
+34112 572
+34176 578
+34240 571
+34304 590
+34368 581
+34432 585
+34496 582
+34560 568
+34624 584
+34688 587
+34752 591
+34816 591
+34880 584
+34944 581
+35008 586
+35072 562
+35136 573
+35200 587
+35264 593
+35328 594
+35392 600
+35456 568
+35520 589
+35584 586
+35648 591
+35712 591
+35776 595
+35840 589
+35904 600
+35968 608
+36032 600
+36096 612
+36160 599
+36224 612
+36288 602
+36352 611
+36416 607
+36480 602
+36544 606
+36608 605
+36672 603
+36736 591
+36800 608
+36864 612
+36928 610
+36992 604
+37056 615
+37120 613
+37184 619
+37248 613
+37312 607
+37376 611
+37440 615
+37504 611
+37568 626
+37632 618
+37696 619
+37760 623
+37824 618
+37888 630
+37952 615
+38016 622
+38080 624
+38144 622
+38208 616
+38272 629
+38336 623
+38400 616
+38464 625
+38528 614
+38592 626
+38656 635
+38720 624
+38784 624
+38848 623
+38912 615
+38976 622
+39040 629
+39104 635
+39168 623
+39232 639
+39296 634
+39360 629
+39424 642
+39488 637
+39552 637
+39616 637
+39680 648
+39744 640
+39808 647
+39872 636
+39936 632
+40000 645
+40064 638
+40128 645
+40192 640
+40256 644
+40320 635
+40384 629
+40448 641
+40512 647
+40576 648
+40640 646
+40704 640
+40768 643
+40832 657
+40896 638
+40960 647
+41024 648
+41088 649
+41152 644
+41216 642
+41280 644
+41344 648
+41408 648
+41472 663
+41536 646
+41600 666
+41664 651
+41728 656
+41792 650
+41856 647
+41920 653
+41984 667
+42048 664
+42112 672
+42176 670
+42240 660
+42304 667
+42368 673
+42432 659
+42496 674
+42560 675
+42624 670
+42688 673
+42752 662
+42816 666
+42880 670
+42944 664
+43008 673
+43072 675
+43136 680
+43200 680
+43264 672
+43328 671
+43392 678
+43456 680
+43520 689
+43584 683
+43648 697
+43712 699
+43776 685
+43840 675
+43904 680
+43968 685
+44032 681
+44096 683
+44160 688
+44224 681
+44288 702
+44352 705
+44416 685
+44480 689
+44544 694
+44608 692
+44672 688
+44736 688
+44800 694
+44864 708
+44928 702
+44992 700
+45056 707
+45120 704
+45184 707
+45248 707
+45312 702
+45376 707
+45440 709
+45504 710
+45568 710
+45632 710
+45696 714
+45760 710
+45824 701
+45888 709
+45952 712
+46016 706
+46080 714
+46144 712
+46208 711
+46272 716
+46336 715
+46400 724
+46464 726
+46528 720
+46592 713
+46656 713
+46720 710
+46784 719
+46848 716
+46912 715
+46976 725
+47040 725
+47104 715
+47168 725
+47232 718
+47296 719
+47360 725
+47424 728
+47488 715
+47552 721
+47616 718
+47680 712
+47744 735
+47808 727
+47872 737
+47936 742
+48000 736
+48064 738
+48128 740
+48192 728
+48256 732
+48320 729
+48384 743
+48448 736
+48512 733
+48576 739
+48640 741
+48704 742
+48768 741
+48832 742
+48896 735
+48960 735
+49024 740
+49088 738
+49152 737
+49216 747
+49280 739
+49344 740
+49408 744
+49472 749
+49536 756
+49600 744
+49664 733
+49728 748
+49792 744
+49856 743
+49920 752
+49984 748
+50048 750
+50112 741
+50176 752
+50240 745
+50304 751
+50368 741
+50432 748
+50496 742
+50560 751
+50624 751
+50688 747
+50752 764
+50816 749
+50880 759
+50944 752
+51008 757
+51072 760
+51136 759
+51200 755
+51264 759
+51328 748
+51392 758
+51456 760
+51520 747
+51584 755
+51648 761
+51712 764
+51776 763
+51840 761
+51904 782
+51968 766
+52032 764
+52096 761
+52160 759
+52224 772
+52288 773
+52352 764
+52416 768
+52480 779
+52544 770
+52608 757
+52672 779
+52736 773
+52800 769
+52864 778
+52928 773
+52992 786
+53056 778
+53120 772
+53184 771
+53248 771
+53312 771
+53376 772
+53440 776
+53504 800
+53568 792
+53632 791
+53696 783
+53760 801
+53824 798
+53888 795
+53952 786
+54016 796
+54080 783
+54144 792
+54208 788
+54272 802
+54336 787
+54400 782
+54464 779
+54528 794
+54592 794
+54656 785
+54720 789
+54784 791
+54848 808
+54912 798
+54976 799
+55040 805
+55104 791
+55168 803
+55232 812
+55296 805
+55360 812
+55424 814
+55488 802
+55552 810
+55616 798
+55680 806
+55744 807
+55808 803
+55872 811
+55936 814
+56000 807
+56064 799
+56128 804
+56192 816
+56256 805
+56320 805
+56384 820
+56448 821
+56512 823
+56576 808
+56640 810
+56704 809
+56768 826
+56832 831
+56896 812
+56960 823
+57024 825
+57088 820
+57152 812
+57216 822
+57280 809
+57344 832
+57408 811
+57472 824
+57536 810
+57600 821
+57664 821
+57728 817
+57792 819
+57856 835
+57920 833
+57984 838
+58048 823
+58112 826
+58176 830
+58240 844
+58304 828
+58368 828
+58432 821
+58496 825
+58560 839
+58624 850
+58688 829
+58752 838
+58816 826
+58880 838
+58944 835
+59008 828
+59072 830
+59136 838
+59200 847
+59264 829
+59328 851
+59392 847
+59456 837
+59520 838
+59584 835
+59648 842
+59712 846
+59776 849
+59840 854
+59904 848
+59968 856
+60032 859
+60096 838
+60160 848
+60224 849
+60288 858
+60352 846
+60416 849
+60480 848
+60544 855
+60608 847
+60672 870
+60736 857
+60800 858
+60864 882
+60928 862
+60992 853
+61056 857
+61120 851
+61184 866
+61248 848
+61312 872
+61376 873
+61440 881
+61504 864
+61568 878
+61632 880
+61696 871
+61760 877
+61824 863
+61888 879
+61952 861
+62016 867
+62080 877
+62144 876
+62208 884
+62272 866
+62336 860
+62400 882
+62464 874
+62528 865
+62592 867
+62656 886
+62720 875
+62784 877
+62848 872
+62912 861
+62976 899
+63040 870
+63104 885
+63168 889
+63232 863
+63296 876
+63360 868
+63424 866
+63488 879
+63552 885
+63616 869
+63680 878
+63744 885
+63808 884
+63872 878
+63936 882
+64000 889
+64064 878
+64128 895
+64192 875
+64256 889
+64320 882
+64384 880
+64448 889
+64512 883
+64576 886
+64640 879
+64704 892
+64768 880
+64832 890
+64896 908
+64960 919
+65024 882
+65088 896
+65152 895
+65216 894
+65280 891
+65344 889
+65408 891
+65472 1164
+65536 1148
+65664 1172
+65792 1171
+65920 1164
+66048 1162
+66176 1176
+66304 1169
+66432 1184
+66560 1171
+66688 1198
+66816 1176
+66944 1169
+67072 1185
+67200 1180
+67328 1186
+67456 1170
+67584 1191
+67712 1171
+67840 1170
+67968 1194
+68096 1186
+68224 1175
+68352 1188
+68480 1190
+68608 1181
+68736 1195
+68864 1192
+68992 1198
+69120 1195
+69248 1198
+69376 1189
+69504 1196
+69632 1199
+69760 1201
+69888 1209
+70016 1208
+70144 1217
+70272 1213
+70400 1197
+70528 1209
+70656 1215
+70784 1221
+70912 1215
+71040 1218
+71168 1223
+71296 1213
+71424 1257
+71552 1225
+71680 1228
+71808 1207
+71936 1225
+72064 1239
+72192 1213
+72320 1230
+72448 1229
+72576 1229
+72704 1232
+72832 1260
+72960 1218
+73088 1225
+73216 1227
+73344 1231
+73472 1253
+73600 1238
+73728 1242
+73856 1240
+73984 1236
+74112 1245
+74240 1249
+74368 1242
+74496 1226
+74624 1264
+74752 1237
+74880 1257
+75008 1253
+75136 1257
+75264 1258
+75392 1260
+75520 1272
+75648 1263
+75776 1267
+75904 1258
+76032 1275
+76160 1269
+76288 1281
+76416 1271
+76544 1267
+76672 1277
+76800 1264
+76928 1275
+77056 1267
+77184 1272
+77312 1284
+77440 1275
+77568 1305
+77696 1308
+77824 1303
+77952 1284
+78080 1284
+78208 1280
+78336 1314
+78464 1286
+78592 1291
+78720 1278
+78848 1300
+78976 1280
+79104 1272
+79232 1270
+79360 1300
+79488 1323
+79616 1289
+79744 1310
+79872 1298
+80000 1345
+80128 1333
+80256 1302
+80384 1306
+80512 1334
+80640 1318
+80768 1304
+80896 1303
+81024 1347
+81152 1326
+81280 1303
+81408 1323
+81536 1316
+81664 1315
+81792 1335
+81920 1347
+82048 1316
+82176 1328
+82304 1315
+82432 1342
+82560 1338
+82688 1322
+82816 1320
+82944 1329
+83072 1366
+83200 1323
+83328 1356
+83456 1367
+83584 1338
+83712 1369
+83840 1369
+83968 1341
+84096 1343
+84224 1364
+84352 1345
+84480 1349
+84608 1348
+84736 1335
+84864 1337
+84992 1365
+85120 1355
+85248 1361
+85376 1348
+85504 1345
+85632 1329
+85760 1343
+85888 1365
+86016 1367
+86144 1333
+86272 1357
+86400 1349
+86528 1360
+86656 1393
+86784 1364
+86912 1385
+87040 1401
+87168 1368
+87296 1364
+87424 1378
+87552 1354
+87680 1400
+87808 1368
+87936 1372
+88064 1383
+88192 1399
+88320 1376
+88448 1418
+88576 1388
+88704 1382
+88832 1386
+88960 1408
+89088 1377
+89216 1383
+89344 1376
+89472 1389
+89600 1376
+89728 1417
+89856 1380
+89984 1402
+90112 1394
+90240 1389
+90368 1419
+90496 1393
+90624 1386
+90752 1388
+90880 1402
+91008 1382
+91136 1403
+91264 1379
+91392 1431
+91520 1432
+91648 1435
+91776 1404
+91904 1402
+92032 1434
+92160 1431
+92288 1402
+92416 1401
+92544 1412
+92672 1418
+92800 1423
+92928 1389
+93056 1442
+93184 1425
+93312 1428
+93440 1403
+93568 1430
+93696 1452
+93824 1401
+93952 1414
+94080 1415
+94208 1414
+94336 1421
+94464 1444
+94592 1421
+94720 1462
+94848 1457
+94976 1422
+95104 1423
+95232 1432
+95360 1416
+95488 1447
+95616 1442
+95744 1446
+95872 1444
+96000 1443
+96128 1426
+96256 1437
+96384 1442
+96512 1423
+96640 1457
+96768 1464
+96896 1454
+97024 1439
+97152 1464
+97280 1447
+97408 1437
+97536 1417
+97664 1430
+97792 1475
+97920 1446
+98048 1450
+98176 1445
+98304 1421
+98432 1445
+98560 1443
+98688 1441
+98816 1482
+98944 1447
+99072 1466
+99200 1449
+99328 1455
+99456 1467
+99584 1489
+99712 1461
+99840 1452
+99968 1466
+100096 1465
+100224 1458
+100352 1451
+100480 1510
+100608 1448
+100736 1468
+100864 1489
+100992 1480
+101120 1445
+101248 1487
+101376 1476
+101504 1475
+101632 1466
+101760 1455
+101888 1505
+102016 1465
+102144 1462
+102272 1488
+102400 1483
+102528 1514
+102656 1489
+102784 1491
+102912 1478
+103040 1474
+103168 1498
+103296 1497
+103424 1526
+103552 1521
+103680 1461
+103808 1532
+103936 1493
+104064 1469
+104192 1481
+104320 1482
+104448 1522
+104576 1515
+104704 1537
+104832 1504
+104960 1537
+105088 1500
+105216 1478
+105344 1514
+105472 1472
+105600 1483
+105728 1555
+105856 1481
+105984 1504
+106112 1537
+106240 1502
+106368 1530
+106496 1518
+106624 1506
+106752 1517
+106880 1543
+107008 1550
+107136 1506
+107264 1525
+107392 1548
+107520 1564
+107648 1549
+107776 1514
+107904 1526
+108032 1522
+108160 1557
+108288 1532
+108416 1531
+108544 1538
+108672 1544
+108800 1568
+108928 1550
+109056 1540
+109184 1527
+109312 1541
+109440 1519
+109568 1579
+109696 1532
+109824 1598
+109952 1547
+110080 1573
+110208 1545
+110336 1566
+110464 1553
+110592 1547
+110720 1566
+110848 1582
+110976 1568
+111104 1557
+111232 1559
+111360 1590
+111488 1561
+111616 1547
+111744 1574
+111872 1572
+112000 1542
+112128 1611
+112256 1554
+112384 1579
+112512 1581
+112640 1563
+112768 1592
+112896 1593
+113024 1553
+113152 1592
+113280 1590
+113408 1569
+113536 1596
+113664 1606
+113792 1594
+113920 1642
+114048 1570
+114176 1642
+114304 1648
+114432 1570
+114560 1630
+114688 1649
+114816 1581
+114944 1628
+115072 1573
+115200 1628
+115328 1631
+115456 1576
+115584 1635
+115712 1624
+115840 1592
+115968 1634
+116096 1614
+116224 1661
+116352 1609
+116480 1662
+116608 1577
+116736 1662
+116864 1647
+116992 1617
+117120 1627
+117248 1657
+117376 1631
+117504 1598
+117632 1681
+117760 1643
+117888 1634
+118016 1618
+118144 1639
+118272 1651
+118400 1605
+118528 1591
+118656 1655
+118784 1631
+118912 1622
+119040 1624
+119168 1629
+119296 1598
+119424 1665
+119552 1676
+119680 1620
+119808 1616
+119936 1624
+120064 1669
+120192 1673
+120320 1638
+120448 1627
+120576 1611
+120704 1700
+120832 1653
+120960 1715
+121088 1661
+121216 1659
+121344 1640
+121472 1666
+121600 1662
+121728 1680
+121856 1679
+121984 1707
+122112 1640
+122240 1626
+122368 1684
+122496 1666
+122624 1652
+122752 1633
+122880 1674
+123008 1676
+123136 1665
+123264 1687
+123392 1664
+123520 1659
+123648 1643
+123776 1672
+123904 1694
+124032 1641
+124160 1752
+124288 1648
+124416 1658
+124544 1720
+124672 1711
+124800 1723
+124928 1662
+125056 1647
+125184 1772
+125312 1671
+125440 1647
+125568 1719
+125696 1636
+125824 1694
+125952 1648
+126080 1750
+126208 1713
+126336 1771
+126464 1748
+126592 1655
+126720 1720
+126848 1720
+126976 1675
+127104 1662
+127232 1722
+127360 1675
+127488 1667
+127616 1671
+127744 1668
+127872 1659
+128000 1701
+128128 1667
+128256 1731
+128384 1671
+128512 1670
+128640 1675
+128768 1688
+128896 1690
+129024 1714
+129152 1761
+129280 1761
+129408 1684
+129536 1685
+129664 1774
+129792 1751
+129920 1679
+130048 1678
+130176 1712
+130304 1688
+130432 1810
+130560 1756
+130688 1684
+130816 1686
+130944 1688
+131072 1680
+131328 1750
+131584 1683
+131840 1697
+132096 1687
+132352 1694
+132608 1683
+132864 1683
+133120 1760
+133376 1718
+133632 1687
+133888 1707
+134144 1754
+134400 1761
+134656 1705
+134912 1695
+135168 1758
+135424 1697
+135680 1761
+135936 1754
+136192 1730
+136448 1725
+136704 1838
+136960 1743
+137216 1741
+137472 1739
+137728 1798
+137984 1737
+138240 1846
+138496 1744
+138752 1761
+139008 1755
+139264 1837
+139520 1776
+139776 1749
+140032 1832
+140288 1777
+140544 1792
+140800 1839
+141056 1777
+141312 1830
+141568 1787
+141824 1793
+142080 1798
+142336 1779
+142592 1806
+142848 1856
+143104 1804
+143360 1793
+143616 1798
+143872 1810
+144128 1805
+144384 1820
+144640 1808
+144896 1823
+145152 1812
+145408 1810
+145664 1840
+145920 1829
+146176 1826
+146432 1931
+146688 1889
+146944 1892
+147200 1816
+147456 1832
+147712 1873
+147968 1831
+148224 1836
+148480 1856
+148736 1846
+148992 1851
+149248 1902
+149504 1842
+149760 1846
+150016 1849
+150272 1867
+150528 1909
+150784 1846
+151040 1852
+151296 1859
+151552 1891
+151808 1845
+152064 1895
+152320 1857
+152576 1846
+152832 1929
+153088 1850
+153344 1859
+153600 1923
+153856 1868
+154112 1930
+154368 1867
+154624 1873
+154880 1921
+155136 1881
+155392 1879
+155648 1932
+155904 1874
+156160 1867
+156416 1984
+156672 1882
+156928 1872
+157184 1876
+157440 1948
+157696 1893
+157952 1886
+158208 1892
+158464 1890
+158720 1955
+158976 1893
+159232 1901
+159488 1881
+159744 1971
+160000 1891
+160256 1972
+160512 1904
+160768 1982
+161024 1934
+161280 1924
+161536 1925
+161792 1978
+162048 1915
+162304 1944
+162560 1937
+162816 1933
+163072 1929
+163328 2001
+163584 1934
+163840 1947
+164096 1949
+164352 1947
+164608 2008
+164864 1944
+165120 1964
+165376 1960
+165632 1947
+165888 1953
+166144 1971
+166400 2006
+166656 1964
+166912 1970
+167168 1968
+167424 1963
+167680 2001
+167936 1972
+168192 1989
+168448 1980
+168704 1980
+168960 2002
+169216 2061
+169472 1998
+169728 1991
+169984 2017
+170240 2036
+170496 2083
+170752 2016
+171008 2007
+171264 2009
+171520 2023
+171776 2027
+172032 2024
+172288 2022
+172544 2052
+172800 2031
+173056 2039
+173312 2042
+173568 2101
+173824 2042
+174080 2039
+174336 2045
+174592 2048
+174848 2049
+175104 2065
+175360 2056
+175616 2068
+175872 2073
+176128 2062
+176384 2073
+176640 2072
+176896 2061
+177152 2059
+177408 2093
+177664 2085
+177920 2085
+178176 2149
+178432 2084
+178688 2068
+178944 2124
+179200 2074
+179456 2088
+179712 2140
+179968 2088
+180224 2138
+180480 2088
+180736 2094
+180992 2069
+181248 2065
+181504 2084
+181760 2080
+182016 2058
+182272 2078
+182528 2069
+182784 2067
+183040 2084
+183296 2082
+183552 2079
+183808 2075
+184064 2081
+184320 2076
+184576 2092
+184832 2085
+185088 2163
+185344 2083
+185600 2092
+185856 2094
+186112 2091
+186368 2105
+186624 2080
+186880 2115
+187136 2093
+187392 2084
+187648 2170
+187904 2106
+188160 2096
+188416 2116
+188672 2117
+188928 2105
+189184 2109
+189440 2122
+189696 2121
+189952 2103
+190208 2107
+190464 2123
+190720 2123
+190976 2115
+191232 2137
+191488 2129
+191744 2136
+192000 2125
+192256 2135
+192512 2130
+192768 2134
+193024 2141
+193280 2135
+193536 2156
+193792 2142
+194048 2148
+194304 2163
+194560 2154
+194816 2156
+195072 2171
+195328 2233
+195584 2186
+195840 2179
+196096 2171
+196352 2190
+196608 2201
+196864 2216
+197120 2219
+197376 2203
+197632 2211
+197888 2198
+198144 2219
+198400 2222
+198656 2239
+198912 2235
+199168 2224
+199424 2234
+199680 2229
+199936 2218
+200192 2236
+200448 2268
+200704 2284
+200960 2240
+201216 2282
+201472 2252
+201728 2269
+201984 2277
+202240 2264
+202496 2277
+202752 2278
+203008 2279
+203264 2262
+203520 2286
+203776 2299
+204032 2283
+204288 2294
+204544 2283
+204800 2278
+205056 2299
+205312 2298
+205568 2317
+205824 2298
+206080 2311
+206336 2286
+206592 2300
+206848 2306
+207104 2301
+207360 2367
+207616 2308
+207872 2312
+208128 2305
+208384 2327
+208640 2307
+208896 2324
+209152 2312
+209408 2315
+209664 2331
+209920 2317
+210176 2409
+210432 2321
+210688 2322
+210944 2319
+211200 2322
+211456 2319
+211712 2336
+211968 2331
+212224 2323
+212480 2322
+212736 2345
+212992 2334
+213248 2335
+213504 2339
+213760 2344
+214016 2324
+214272 2328
+214528 2343
+214784 2326
+215040 2343
+215296 2345
+215552 2333
+215808 2341
+216064 2353
+216320 2341
+216576 2340
+216832 2346
+217088 2354
+217344 2344
+217600 2351
+217856 2344
+218112 2353
+218368 2350
+218624 2347
+218880 2359
+219136 2360
+219392 2361
+219648 2365
+219904 2359
+220160 2366
+220416 2372
+220672 2369
+220928 2359
+221184 2386
+221440 2389
+221696 2379
+221952 2384
+222208 2382
+222464 2396
+222720 2394
+222976 2402
+223232 2403
+223488 2407
+223744 2400
+224000 2409
+224256 2421
+224512 2427
+224768 2430
+225024 2405
+225280 2420
+225536 2435
+225792 2487
+226048 2449
+226304 2457
+226560 2544
+226816 2462
+227072 2440
+227328 2469
+227584 2456
+227840 2456
+228096 2472
+228352 2483
+228608 2478
+228864 2476
+229120 2473
+229376 2484
+229632 2483
+229888 2495
+230144 2496
+230400 2499
+230656 2505
+230912 2513
+231168 2505
+231424 2510
+231680 2516
+231936 2521
+232192 2509
+232448 2522
+232704 2531
+232960 2509
+233216 2525
+233472 2524
+233728 2525
+233984 2528
+234240 2520
+234496 2547
+234752 2534
+235008 2544
+235264 2532
+235520 2545
+235776 2549
+236032 2537
+236288 2554
+236544 2537
+236800 2539
+237056 2546
+237312 2550
+237568 2559
+237824 2560
+238080 2553
+238336 2549
+238592 2557
+238848 2557
+239104 2556
+239360 2569
+239616 2563
+239872 2557
+240128 2565
+240384 2567
+240640 2557
+240896 2562
+241152 2563
+241408 2584
+241664 2563
+241920 2582
+242176 2568
+242432 2554
+242688 2571
+242944 2586
+243200 2553
+243456 2574
+243712 2589
+243968 2581
+244224 2586
+244480 2581
+244736 2585
+244992 2583
+245248 2595
+245504 2575
+245760 2601
+246016 2606
+246272 2569
+246528 2564
+246784 2565
+247040 2567
+247296 2577
+247552 2584
+247808 2585
+248064 2649
+248320 2590
+248576 2574
+248832 2578
+249088 2592
+249344 2600
+249600 2598
+249856 2612
+250112 2599
+250368 2603
+250624 2602
+250880 2601
+251136 2614
+251392 2620
+251648 2619
+251904 2618
+252160 2636
+252416 2624
+252672 2633
+252928 2619
+253184 2631
+253440 2633
+253696 2647
+253952 2662
+254208 2662
+254464 2668
+254720 2668
+254976 2659
+255232 2681
+255488 2678
+255744 2684
+256000 2691
+256256 2712
+256512 2702
+256768 2693
+257024 2693
+257280 2712
+257536 2709
+257792 2712
+258048 2709
+258304 2723
+258560 2720
+258816 2717
+259072 2734
+259328 2728
+259584 2728
+259840 2739
+260096 2742
+260352 2739
+260608 2747
+260864 2751
+261120 2746
+261376 2742
+261632 2740
+261888 2757
+262144 2754
+262656 2768
+263168 2764
+263680 2773
+264192 2765
+264704 2773
+265216 2779
+265728 2788
+266240 2778
+266752 2788
+267264 2796
+267776 2791
+268288 2800
+268800 2814
+269312 2805
+269824 2808
+270336 2821
+270848 2805
+271360 2813
+271872 2812
+272384 2808
+272896 2816
+273408 2819
+273920 2832
+274432 2842
+274944 2829
+275456 2844
+275968 2850
+276480 2858
+276992 2857
+277504 2862
+278016 2871
+278528 2873
+279040 2883
+279552 2892
+280064 2891
+280576 2890
+281088 2914
+281600 2965
+282112 2929
+282624 2910
+283136 2912
+283648 2924
+284160 2927
+284672 2935
+285184 2945
+285696 2957
+286208 2965
+286720 2966
+287232 2983
+287744 2989
+288256 2979
+288768 2982
+289280 2976
+289792 2991
+290304 3011
+290816 3017
+291328 3018
+291840 3029
+292352 3027
+292864 3014
+293376 3018
+293888 3033
+294400 3025
+294912 3022
+295424 3028
+295936 3064
+296448 3033
+296960 3035
+297472 3037
+297984 3039
+298496 3058
+299008 3037
+299520 3064
+300032 3094
+300544 3065
+301056 3070
+301568 3076
+302080 3060
+302592 3076
+303104 3077
+303616 3076
+304128 3091
+304640 3085
+305152 3092
+305664 3100
+306176 3090
+306688 3113
+307200 3119
+307712 3110
+308224 3133
+308736 3118
+309248 3121
+309760 3152
+310272 3140
+310784 3135
+311296 3140
+311808 3143
+312320 3150
+312832 3149
+313344 3136
+313856 3154
+314368 3166
+314880 3177
+315392 3180
+315904 3192
+316416 3190
+316928 3205
+317440 3212
+317952 3219
+318464 3221
+318976 3217
+319488 3229
+320000 3235
+320512 3239
+321024 3251
+321536 3236
+322048 3239
+322560 3360
+323072 3269
+323584 3252
+324096 3257
+324608 3337
+325120 3280
+325632 3277
+326144 3274
+326656 3310
+327168 3289
+327680 3294
+328192 3299
+328704 3293
+329216 3396
+329728 3299
+330240 3317
+330752 3360
+331264 3320
+331776 3333
+332288 3335
+332800 3327
+333312 3328
+333824 3352
+334336 3353
+334848 3388
+335360 3361
+335872 3354
+336384 3357
+336896 3373
+337408 3423
+337920 3391
+338432 3407
+338944 3409
+339456 3413
+339968 3407
+340480 3402
+340992 3515
+341504 3404
+342016 3425
+342528 3444
+343040 3437
+343552 3435
+344064 3463
+344576 3446
+345088 3481
+345600 3560
+346112 3488
+346624 3484
+347136 3468
+347648 3502
+348160 3485
+348672 3475
+349184 3503
+349696 3498
+350208 3557
+350720 3493
+351232 3511
+351744 3549
+352256 3519
+352768 3499
+353280 3527
+353792 3523
+354304 3568
+354816 3526
+355328 3574
+355840 3648
+356352 3556
+356864 3571
+357376 3614
+357888 3582
+358400 3574
+358912 3543
+359424 3562
+359936 3603
+360448 3595
+360960 3577
+361472 3565
+361984 3600
+362496 3570
+363008 3601
+363520 3590
+364032 3589
+364544 3613
+365056 3668
+365568 3611
+366080 3619
+366592 3626
+367104 3641
+367616 3620
+368128 3654
+368640 3672
+369152 3652
+369664 3675
+370176 3691
+370688 3719
+371200 3671
+371712 3747
+372224 3697
+372736 3679
+373248 3692
+373760 3735
+374272 3750
+374784 3714
+375296 3787
+375808 3711
+376320 3714
+376832 3735
+377344 3746
+377856 3739
+378368 3719
+378880 3741
+379392 3779
+379904 3809
+380416 3768
+380928 3811
+381440 3777
+381952 3763
+382464 3835
+382976 3780
+383488 3780
+384000 3873
+384512 3785
+385024 3785
+385536 3823
+386048 3784
+386560 3796
+387072 3823
+387584 3827
+388096 3824
+388608 3900
+389120 3822
+389632 3886
+390144 3880
+390656 3830
+391168 3928
+391680 3857
+392192 3854
+392704 3943
+393216 3897
+393728 3867
+394240 3850
+394752 3912
+395264 3969
+395776 3880
+396288 3877
+396800 3866
+397312 3889
+397824 3903
+398336 3922
+398848 3935
+399360 3917
+399872 3919
+400384 3941
+400896 3938
+401408 3935
+401920 3936
+402432 3991
+402944 3929
+403456 4009
+403968 4012
+404480 3963
+404992 4051
+405504 3991
+406016 4029
+406528 3987
+407040 4075
+407552 4063
+408064 4041
+408576 4026
+409088 4079
+409600 4005
+410112 4002
+410624 4025
+411136 4006
+411648 4062
+412160 4019
+412672 4037
+413184 4008
+413696 4042
+414208 4047
+414720 4051
+415232 4110
+415744 4088
+416256 4094
+416768 4112
+417280 4155
+417792 4156
+418304 4077
+418816 4140
+419328 4063
+419840 4093
+420352 4114
+420864 4140
+421376 4148
+421888 4116
+422400 4094
+422912 4117
+423424 4087
+423936 4115
+424448 4141
+424960 4122
+425472 4143
+425984 4161
+426496 4141
+427008 4250
+427520 4203
+428032 4191
+428544 4153
+429056 4179
+429568 4264
+430080 4168
+430592 4189
+431104 4217
+431616 4217
+432128 4258
+432640 4193
+433152 4228
+433664 4224
+434176 4210
+434688 4296
+435200 4226
+435712 4293
+436224 4235
+436736 4390
+437248 4369
+437760 4275
+438272 4279
+438784 4281
+439296 4308
+439808 4285
+440320 4272
+440832 4353
+441344 4329
+441856 4307
+442368 4276
+442880 4308
+443392 4289
+443904 4293
+444416 4303
+444928 4300
+445440 4366
+445952 4312
+446464 4399
+446976 4304
+447488 4405
+448000 4355
+448512 4330
+449024 4332
+449536 4408
+450048 4334
+450560 4415
+451072 4360
+451584 4363
+452096 4401
+452608 4342
+453120 4359
+453632 4506
+454144 4385
+454656 4446
+455168 4374
+455680 4451
+456192 4468
+456704 4416
+457216 4400
+457728 4403
+458240 4403
+458752 4402
+459264 4411
+459776 4409
+460288 4428
+460800 4416
+461312 4492
+461824 4432
+462336 4461
+462848 4459
+463360 4451
+463872 4480
+464384 4481
+464896 4559
+465408 4569
+465920 4469
+466432 4498
+466944 4485
+467456 4502
+467968 4481
+468480 4564
+468992 4498
+469504 4530
+470016 4531
+470528 4511
+471040 4582
+471552 4508
+472064 4563
+472576 4537
+473088 4533
+473600 4611
+474112 4530
+474624 4578
+475136 4581
+475648 4554
+476160 4548
+476672 4547
+477184 4643
+477696 4598
+478208 4571
+478720 4626
+479232 4668
+479744 4572
+480256 4610
+480768 4598
+481280 4612
+481792 4676
+482304 4614
+482816 4693
+483328 4697
+483840 4626
+484352 4620
+484864 4645
+485376 4699
+485888 4663
+486400 4653
+486912 4640
+487424 4795
+487936 4687
+488448 4703
+488960 4710
+489472 4698
+489984 4790
+490496 4708
+491008 4748
+491520 4683
+492032 4771
+492544 4782
+493056 4799
+493568 4753
+494080 4741
+494592 4709
+495104 4726
+495616 4713
+496128 4735
+496640 4781
+497152 4788
+497664 4770
+498176 4763
+498688 4799
+499200 4764
+499712 4814
+500224 4824
+500736 4765
+501248 4835
+501760 4787
+502272 4862
+502784 4894
+503296 4855
+503808 4813
+504320 4826
+504832 4817
+505344 4810
+505856 4800
+506368 4888
+506880 4806
+507392 4814
+507904 4875
+508416 4842
+508928 4895
+509440 4876
+509952 4828
+510464 4911
+510976 4908
+511488 4908
+512000 4888
+512512 4881
+513024 4862
+513536 4889
+514048 4925
+514560 4880
+515072 4927
+515584 4874
+516096 4891
+516608 4950
+517120 4975
+517632 4906
+518144 4968
+518656 4944
+519168 4946
+519680 4925
+520192 4917
+520704 4964
+521216 5071
+521728 5075
+522240 5015
+522752 5026
+523264 5012
+523776 4997
+524288 4981
+525312 5057
+526336 4977
+527360 4990
+528384 5117
+529408 5119
+530432 5079
+531456 5086
+532480 5128
+533504 5029
+534528 5157
+535552 5060
+536576 5054
+537600 5049
+538624 5079
+539648 5093
+540672 5132
+541696 5146
+542720 5117
+543744 5128
+544768 5169
+545792 5181
+546816 5171
+547840 5296
+548864 5163
+549888 5211
+550912 5240
+551936 5208
+552960 5407
+553984 5274
+555008 5300
+556032 5382
+557056 5325
+558080 5242
+559104 5310
+560128 5295
+561152 5369
+562176 5294
+563200 5313
+564224 5315
+565248 5310
+566272 5326
+567296 5377
+568320 5376
+569344 5452
+570368 5340
+571392 5413
+572416 5478
+573440 5441
+574464 5477
+575488 5435
+576512 5469
+577536 5476
+578560 5496
+579584 5498
+580608 5531
+581632 5451
+582656 5485
+583680 5559
+584704 5487
+585728 5536
+586752 5572
+587776 5557
+588800 5512
+589824 5559
+590848 5581
+591872 5534
+592896 5714
+593920 5768
+594944 6079
+595968 5834
+596992 5649
+598016 5585
+599040 5638
+600064 5668
+601088 5621
+602112 5645
+603136 5698
+604160 5646
+605184 5676
+606208 5697
+607232 5683
+608256 5774
+609280 5773
+610304 5828
+611328 5792
+612352 5868
+613376 5794
+614400 5781
+615424 5808
+616448 5811
+617472 5814
+618496 5799
+619520 5818
+620544 5876
+621568 5862
+622592 5788
+623616 5935
+624640 5899
+625664 5921
+626688 5895
+627712 5841
+628736 5864
+629760 6007
+630784 5937
+631808 5892
+632832 5983
+633856 5906
+634880 6000
+635904 6005
+636928 5995
+637952 6018
+638976 6042
+640000 5948
+641024 6030
+642048 6051
+643072 6053
+644096 5970
+645120 5991
+646144 6129
+647168 6057
+648192 6173
+649216 6088
+650240 6092
+651264 6037
+652288 6026
+653312 6208
+654336 6090
+655360 6174
+656384 6140
+657408 6124
+658432 6106
+659456 6114
+660480 6114
+661504 6183
+662528 6204
+663552 6257
+664576 6276
+665600 6139
+666624 6243
+667648 6217
+668672 6315
+669696 6280
+670720 6201
+671744 6294
+672768 6294
+673792 6382
+674816 6267
+675840 6303
+676864 6245
+677888 6285
+678912 6279
+679936 6318
+680960 6370
+681984 6371
+683008 6305
+684032 6325
+685056 6300
+686080 6379
+687104 6402
+688128 6456
+689152 6421
+690176 6408
+691200 6367
+692224 6454
+693248 6386
+694272 6385
+695296 6512
+696320 6477
+697344 6444
+698368 6524
+699392 6545
+700416 6665
+701440 6561
+702464 6567
+703488 6595
+704512 6569
+705536 6568
+706560 6595
+707584 6516
+708608 6614
+709632 6599
+710656 6627
+711680 6660
+712704 6642
+713728 6581
+714752 6688
+715776 6675
+716800 6677
+717824 6733
+718848 6614
+719872 6796
+720896 6697
+721920 6747
+722944 6775
+723968 6838
+724992 6770
+726016 6775
+727040 6720
+728064 6789
+729088 6869
+730112 6782
+731136 6785
+732160 6826
+733184 6775
+734208 6846
+735232 6829
+736256 6852
+737280 6949
+738304 6820
+739328 6786
+740352 6881
+741376 6906
+742400 6802
+743424 6864
+744448 6816
+745472 6859
+746496 6902
+747520 6839
+748544 6924
+749568 6969
+750592 6960
+751616 6970
+752640 6953
+753664 6898
+754688 6902
+755712 6930
+756736 6926
+757760 6981
+758784 7012
+759808 7089
+760832 7108
+761856 7017
+762880 7071
+763904 7065
+764928 7063
+765952 7143
+766976 7113
+768000 7131
+769024 7114
+770048 7053
+771072 7097
+772096 7143
+773120 7092
+774144 7088
+775168 7117
+776192 7140
+777216 7117
+778240 7222
+779264 7209
+780288 7221
+781312 7172
+782336 7336
+783360 7239
+784384 7265
+785408 7261
+786432 7332
+787456 7277
+788480 7211
+789504 7350
+790528 7319
+791552 7237
+792576 7289
+793600 7266
+794624 7342
+795648 7337
+796672 7348
+797696 7447
+798720 7367
+799744 7319
+800768 7321
+801792 7342
+802816 7339
+803840 7417
+804864 7346
+805888 7434
+806912 7385
+807936 7500
+808960 7389
+809984 7477
+811008 7484
+812032 7503
+813056 7499
+814080 7433
+815104 7577
+816128 7538
+817152 7549
+818176 7579
+819200 7535
+820224 7580
+821248 7500
+822272 7557
+823296 7610
+824320 7569
+825344 7538
+826368 7549
+827392 7558
+828416 7546
+829440 7674
+830464 7653
+831488 7633
+832512 7665
+833536 7651
+834560 7641
+835584 7695
+836608 7675
+837632 7622
+838656 7692
+839680 7721
+840704 7734
+841728 7702
+842752 7650
+843776 7683
+844800 7724
+845824 7853
+846848 7689
+847872 7718
+848896 7773
+849920 7781
+850944 7791
+851968 7822
+852992 7868
+854016 7833
+855040 7753
+856064 7791
+857088 7875
+858112 7811
+859136 7776
+860160 7855
+861184 7798
+862208 7918
+863232 7846
+864256 7928
+865280 8029
+866304 7870
+867328 7996
+868352 7878
+869376 7874
+870400 7981
+871424 7975
+872448 7918
+873472 7997
+874496 7942
+875520 7953
+876544 8077
+877568 7981
+878592 8030
+879616 8048
+880640 8078
+881664 8105
+882688 8133
+883712 8025
+884736 8176
+885760 8036
+886784 8111
+887808 8136
+888832 8104
+889856 8210
+890880 8178
+891904 8107
+892928 8249
+893952 8192
+894976 8209
+896000 8115
+897024 8127
+898048 8143
+899072 8229
+900096 8259
+901120 8246
+902144 8222
+903168 8329
+904192 8276
+905216 8183
+906240 8307
+907264 8208
+908288 8279
+909312 8220
+910336 8335
+911360 8281
+912384 8250
+913408 8250
+914432 8275
+915456 8267
+916480 8423
+917504 8285
+918528 8282
+919552 8325
+920576 8340
+921600 8411
+922624 8467
+923648 8423
+924672 8379
+925696 8403
+926720 8454
+927744 8369
+928768 8379
+929792 8543
+930816 8396
+931840 8455
+932864 8409
+933888 8503
+934912 8435
+935936 8543
+936960 8455
+937984 8480
+939008 8469
+940032 8594
+941056 8493
+942080 8689
+943104 8512
+944128 8509
+945152 8524
+946176 8553
+947200 8541
+948224 8542
+949248 8554
+950272 8561
+951296 8584
+952320 8583
+953344 8593
+954368 8600
+955392 8622
+956416 8616
+957440 8721
+958464 8649
+959488 8637
+960512 8654
+961536 8669
+962560 8688
+963584 8690
+964608 8715
+965632 8813
+966656 8763
+967680 8829
+968704 8801
+969728 8754
+970752 8778
+971776 8802
+972800 8769
+973824 8792
+974848 8802
+975872 8808
+976896 8909
+977920 8848
+978944 8841
+979968 8953
+980992 8902
+982016 8865
+983040 8878
+984064 8885
+985088 8888
+986112 8897
+987136 8914
+988160 8960
+989184 8922
+990208 8937
+991232 8943
+992256 8986
+993280 8982
+994304 8984
+995328 8976
+996352 8976
+997376 8995
+998400 9005
+999424 9006
+1000448 9021
+1001472 9019
+1002496 9055
+1003520 9059
+1004544 9062
+1005568 9069
+1006592 9127
+1007616 9073
+1008640 9146
+1009664 9084
+1010688 9097
+1011712 9098
+1012736 9101
+1013760 9124
+1014784 9123
+1015808 9129
+1016832 9135
+1017856 9238
+1018880 9204
+1019904 9173
+1020928 9219
+1021952 9192
+1022976 9204
+1024000 9262
+1025024 9220
+1026048 9257
+1027072 9271
+1028096 9332
+1029120 9270
+1030144 9269
+1031168 9380
+1032192 9341
+1033216 9294
+1034240 9334
+1035264 9385
+1036288 9343
+1037312 9363
+1038336 9411
+1039360 9336
+1040384 9363
+1041408 9413
+1042432 9377
+1043456 9356
+1044480 9417
+1045504 9414
+1046528 9392
+1047552 9444
+1048576 9497
+1050624 9501
+1052672 9456
+1054720 9487
+1056768 9553
+1058816 9524
+1060864 9609
+1062912 9643
+1064960 9658
+1067008 9673
+1069056 9597
+1071104 9651
+1073152 9649
+1075200 9663
+1077248 9750
+1079296 9728
+1081344 9819
+1083392 9813
+1085440 9830
+1087488 9823
+1089536 9792
+1091584 9881
+1093632 9793
+1095680 9875
+1097728 9830
+1099776 9927
+1101824 9920
+1103872 9975
+1105920 9888
+1107968 10016
+1110016 9945
+1112064 10008
+1114112 10061
+1116160 9981
+1118208 9999
+1120256 10028
+1122304 10055
+1124352 10140
+1126400 10070
+1128448 10092
+1130496 10116
+1132544 10129
+1134592 10139
+1136640 10168
+1138688 10275
+1140736 10201
+1142784 10311
+1144832 10249
+1146880 10268
+1148928 10295
+1150976 10381
+1153024 10326
+1155072 10332
+1157120 10360
+1159168 10447
+1161216 10375
+1163264 10403
+1165312 10424
+1167360 10434
+1169408 10450
+1171456 10460
+1173504 10574
+1175552 10490
+1177600 10500
+1179648 10529
+1181696 10547
+1183744 10553
+1185792 10580
+1187840 10586
+1189888 10597
+1191936 10625
+1193984 10632
+1196032 10649
+1198080 10679
+1200128 10697
+1202176 10715
+1204224 10735
+1206272 10754
+1208320 10758
+1210368 10769
+1212416 10803
+1214464 10819
+1216512 10828
+1218560 10836
+1220608 10878
+1222656 10879
+1224704 10907
+1226752 10934
+1228800 10964
+1230848 10980
+1232896 10996
+1234944 11025
+1236992 11036
+1239040 11055
+1241088 11072
+1243136 11081
+1245184 11101
+1247232 11131
+1249280 11143
+1251328 11172
+1253376 11183
+1255424 11189
+1257472 11210
+1259520 11217
+1261568 11233
+1263616 11241
+1265664 11292
+1267712 11280
+1269760 11301
+1271808 11311
+1273856 11322
+1275904 11338
+1277952 11385
+1280000 11387
+1282048 11402
+1284096 11419
+1286144 11418
+1288192 11462
+1290240 11477
+1292288 11509
+1294336 11528
+1296384 11550
+1298432 11669
+1300480 11565
+1302528 11574
+1304576 11586
+1306624 11613
+1308672 11646
+1310720 11652
+1312768 11676
+1314816 11700
+1316864 11786
+1318912 11739
+1320960 11742
+1323008 11771
+1325056 11782
+1327104 11805
+1329152 11825
+1331200 11829
+1333248 11876
+1335296 11876
+1337344 11884
+1339392 11938
+1341440 11934
+1343488 11938
+1345536 11950
+1347584 11981
+1349632 12002
+1351680 12012
+1353728 12026
+1355776 12047
+1357824 12068
+1359872 12069
+1361920 12118
+1363968 12116
+1366016 12161
+1368064 12142
+1370112 12159
+1372160 12174
+1374208 12316
+1376256 12230
+1378304 12312
+1380352 12329
+1382400 12262
+1384448 12307
+1386496 12339
+1388544 12315
+1390592 12373
+1392640 12442
+1394688 12346
+1396736 12440
+1398784 12459
+1400832 12451
+1402880 12531
+1404928 12461
+1406976 12465
+1409024 12560
+1411072 12530
+1413120 12542
+1415168 12550
+1417216 12672
+1419264 12634
+1421312 12655
+1423360 12715
+1425408 12736
+1427456 12758
+1429504 12673
+1431552 12773
+1433600 12760
+1435648 12732
+1437696 12825
+1439744 12785
+1441792 12770
+1443840 12791
+1445888 12843
+1447936 12823
+1449984 12892
+1452032 12889
+1454080 12953
+1456128 12936
+1458176 13531
+1460224 12912
+1462272 13011
+1464320 13012
+1466368 13054
+1468416 12992
+1470464 13056
+1472512 13066
+1474560 13048
+1476608 13143
+1478656 13058
+1480704 13082
+1482752 13101
+1484800 13159
+1486848 13138
+1488896 13221
+1490944 13176
+1492992 13208
+1495040 13225
+1497088 13252
+1499136 13360
+1501184 13284
+1503232 13307
+1505280 13385
+1507328 13451
+1509376 13352
+1511424 13388
+1513472 13385
+1515520 13415
+1517568 13540
+1519616 13448
+1521664 13447
+1523712 13468
+1525760 13490
+1527808 13606
+1529856 13556
+1531904 13535
+1533952 13558
+1536000 13558
+1538048 13571
+1540096 13613
+1542144 13605
+1544192 13637
+1546240 13646
+1548288 13654
+1550336 13684
+1552384 13701
+1554432 13724
+1556480 13745
+1558528 13760
+1560576 13773
+1562624 13801
+1564672 13810
+1566720 13815
+1568768 13842
+1570816 13885
+1572864 13901
+1574912 13895
+1576960 13993
+1579008 13931
+1581056 13970
+1583104 13990
+1585152 14002
+1587200 14023
+1589248 14035
+1591296 14150
+1593344 14110
+1595392 14132
+1597440 14193
+1599488 14220
+1601536 14155
+1603584 14199
+1605632 14175
+1607680 14229
+1609728 14211
+1611776 14222
+1613824 14240
+1615872 14263
+1617920 14284
+1619968 14294
+1622016 14293
+1624064 14306
+1626112 14352
+1628160 14337
+1630208 14362
+1632256 14382
+1634304 14384
+1636352 14425
+1638400 14420
+1640448 14460
+1642496 14470
+1644544 14552
+1646592 14498
+1648640 14522
+1650688 14532
+1652736 14572
+1654784 14577
+1656832 14589
+1658880 14649
+1660928 14632
+1662976 14757
+1665024 14763
+1667072 14737
+1669120 14715
+1671168 14849
+1673216 14759
+1675264 14791
+1677312 14812
+1679360 14803
+1681408 14885
+1683456 14837
+1685504 14980
+1687552 14958
+1689600 14905
+1691648 14958
+1693696 14962
+1695744 14953
+1697792 14961
+1699840 14968
+1701888 14990
+1703936 15125
+1705984 15062
+1708032 15060
+1710080 15039
+1712128 15120
+1714176 15193
+1716224 15234
+1718272 15166
+1720320 15179
+1722368 15274
+1724416 15216
+1726464 15241
+1728512 15303
+1730560 15287
+1732608 15372
+1734656 15310
+1736704 15284
+1738752 15364
+1740800 15357
+1742848 15337
+1744896 15420
+1746944 15460
+1748992 15521
+1751040 15518
+1753088 15560
+1755136 15452
+1757184 15456
+1759232 15567
+1761280 15497
+1763328 15607
+1765376 15619
+1767424 15680
+1769472 15642
+1771520 15590
+1773568 15675
+1775616 15716
+1777664 15761
+1779712 15777
+1781760 15795
+1783808 15825
+1785856 15819
+1787904 15798
+1789952 15855
+1792000 15803
+1794048 15862
+1796096 15776
+1798144 15909
+1800192 15871
+1802240 15857
+1804288 15840
+1806336 15848
+1808384 15951
+1810432 15904
+1812480 15920
+1814528 16019
+1816576 15958
+1818624 16075
+1820672 15989
+1822720 16010
+1824768 16032
+1826816 16031
+1828864 16062
+1830912 16063
+1832960 16242
+1835008 16175
+1837056 16134
+1839104 16313
+1841152 16150
+1843200 16191
+1845248 16368
+1847296 16221
+1849344 16359
+1851392 16273
+1853440 16285
+1855488 16299
+1857536 16322
+1859584 16334
+1861632 16360
+1863680 16376
+1865728 16391
+1867776 16398
+1869824 16433
+1871872 16458
+1873920 16466
+1875968 16482
+1878016 16498
+1880064 16498
+1882112 16517
+1884160 16536
+1886208 16535
+1888256 16575
+1890304 16594
+1892352 16592
+1894400 16618
+1896448 16633
+1898496 16662
+1900544 16674
+1902592 16676
+1904640 16703
+1906688 16708
+1908736 16738
+1910784 16750
+1912832 16768
+1914880 16787
+1916928 16813
+1918976 16805
+1921024 16843
+1923072 16855
+1925120 16876
+1927168 16890
+1929216 16903
+1931264 16932
+1933312 16949
+1935360 16960
+1937408 16996
+1939456 17016
+1941504 17042
+1943552 17061
+1945600 17085
+1947648 17102
+1949696 17112
+1951744 17134
+1953792 17138
+1955840 17155
+1957888 17174
+1959936 17192
+1961984 17209
+1964032 17220
+1966080 17245
+1968128 17266
+1970176 17292
+1972224 17297
+1974272 17310
+1976320 17315
+1978368 17323
+1980416 17347
+1982464 17362
+1984512 17400
+1986560 17412
+1988608 17427
+1990656 17423
+1992704 17451
+1994752 17476
+1996800 17527
+1998848 17549
+2000896 17522
+2002944 17537
+2004992 17571
+2007040 17590
+2009088 17596
+2011136 17685
+2013184 17652
+2015232 17652
+2017280 17660
+2019328 17709
+2021376 17750
+2023424 17726
+2025472 17758
+2027520 17792
+2029568 17792
+2031616 17862
+2033664 17881
+2035712 17843
+2037760 17863
+2039808 17909
+2041856 17922
+2043904 17963
+2045952 17982
+2048000 17964
+2050048 17954
+2052096 17982
+2054144 17996
+2056192 18006
+2058240 18085
+2060288 18087
+2062336 18141
+2064384 18061
+2066432 18081
+2068480 18079
+2070528 18220
+2072576 18193
+2074624 18205
+2076672 18184
+2078720 18283
+2080768 18288
+2082816 18224
+2084864 18316
+2086912 18319
+2088960 18280
+2091008 18310
+2093056 18307
+2095104 18429
+2097152 18422
+2101248 18392
+2105344 18478
+2109440 18458
+2113536 18517
+2117632 18554
+2121728 18587
+2125824 18691
+2129920 18648
+2134016 18840
+2138112 18724
+2142208 18819
+2146304 18804
+2150400 18896
+2154496 18904
+2158592 18879
+2162688 18922
+2166784 18939
+2170880 18979
+2174976 19076
+2179072 19136
+2183168 19066
+2187264 19153
+2191360 19264
+2195456 19223
+2199552 19247
+2203648 19274
+2207744 19314
+2211840 19344
+2215936 19378
+2220032 19425
+2224128 19491
+2228224 19469
+2232320 19507
+2236416 19551
+2240512 19577
+2244608 19633
+2248704 19634
+2252800 19685
+2256896 19723
+2260992 19759
+2265088 19774
+2269184 19847
+2273280 19861
+2277376 19957
+2281472 19930
+2285568 20058
+2289664 20033
+2293760 20039
+2297856 20148
+2301952 20202
+2306048 20179
+2310144 20190
+2314240 20211
+2318336 20245
+2322432 20273
+2326528 20376
+2330624 20433
+2334720 20451
+2338816 20401
+2342912 20474
+2347008 20475
+2351104 20582
+2355200 20537
+2359296 20587
+2363392 20661
+2367488 20730
+2371584 20765
+2375680 20863
+2379776 20782
+2383872 20882
+2387968 20994
+2392064 20901
+2396160 20945
+2400256 20947
+2404352 21040
+2408448 21035
+2412544 21101
+2416640 21159
+2420736 21201
+2424832 21165
+2428928 21219
+2433024 21231
+2437120 21346
+2441216 21331
+2445312 21327
+2449408 21368
+2453504 21583
+2457600 21468
+2461696 21622
+2465792 21549
+2469888 21604
+2473984 21664
+2478080 21648
+2482176 21640
+2486272 21707
+2490368 21722
+2494464 21878
+2498560 21841
+2502656 21820
+2506752 21871
+2510848 21908
+2514944 21966
+2519040 21952
+2523136 22027
+2527232 22014
+2531328 22132
+2535424 22083
+2539520 22126
+2543616 22172
+2547712 22224
+2551808 22259
+2555904 22339
+2560000 22404
+2564096 22338
+2568192 22379
+2572288 22466
+2576384 22437
+2580480 22495
+2584576 22515
+2588672 22551
+2592768 22579
+2596864 22599
+2600960 22672
+2605056 22683
+2609152 22728
+2613248 22812
+2617344 22772
+2621440 22804
+2625536 22873
+2629632 22876
+2633728 22931
+2637824 22966
+2641920 22992
+2646016 23031
+2650112 23143
+2654208 23112
+2658304 23156
+2662400 23181
+2666496 23216
+2670592 23310
+2674688 23399
+2678784 23419
+2682880 23432
+2686976 23466
+2691072 23389
+2695168 23469
+2699264 23486
+2703360 23528
+2707456 23561
+2711552 23590
+2715648 23613
+2719744 23650
+2723840 23724
+2727936 23818
+2732032 23785
+2736128 23805
+2740224 23972
+2744320 23883
+2748416 23951
+2752512 23987
+2756608 24052
+2760704 24046
+2764800 24047
+2768896 24153
+2772992 24137
+2777088 24151
+2781184 24275
+2785280 24208
+2789376 24352
+2793472 24297
+2797568 24389
+2801664 24358
+2805760 24408
+2809856 24556
+2813952 24535
+2818048 24554
+2822144 24611
+2826240 24580
+2830336 24644
+2834432 24676
+2838528 24769
+2842624 24787
+2846720 24805
+2850816 24778
+2854912 24832
+2859008 24929
+2863104 24928
+2867200 25037
+2871296 24939
+2875392 25035
+2879488 25115
+2883584 25048
+2887680 25115
+2891776 25177
+2895872 25156
+2899968 25209
+2904064 25303
+2908160 25335
+2912256 25330
+2916352 26120
+2920448 25459
+2924544 25501
+2928640 25514
+2932736 25508
+2936832 25549
+2940928 25557
+2945024 25649
+2949120 25629
+2953216 25699
+2957312 25788
+2961408 25751
+2965504 25778
+2969600 25866
+2973696 25964
+2977792 25853
+2981888 25972
+2985984 25972
+2990080 25980
+2994176 26013
+2998272 26099
+3002368 26099
+3006464 26186
+3010560 26221
+3014656 26279
+3018752 26300
+3022848 26393
+3026944 26365
+3031040 26451
+3035136 26419
+3039232 26484
+3043328 26384
+3047424 26490
+3051520 26576
+3055616 26600
+3059712 26669
+3063808 26633
+3067904 26710
+3072000 26765
+3076096 26766
+3080192 26820
+3084288 26807
+3088384 26846
+3092480 26976
+3096576 26999
+3100672 27065
+3104768 26957
+3108864 27018
+3112960 27099
+3117056 27131
+3121152 27169
+3125248 27101
+3129344 27227
+3133440 27165
+3137536 27273
+3141632 27329
+3145728 27462
+3149824 27395
+3153920 27337
+3158016 27482
+3162112 27401
+3166208 27571
+3170304 27483
+3174400 27526
+3178496 27567
+3182592 27596
+3186688 27635
+3190784 27657
+3194880 27714
+3198976 27744
+3203072 27770
+3207168 27916
+3211264 27832
+3215360 27969
+3219456 27906
+3223552 27921
+3227648 27972
+3231744 28150
+3235840 28032
+3239936 28208
+3244032 28098
+3248128 28147
+3252224 28185
+3256320 28316
+3260416 28263
+3264512 28357
+3268608 28449
+3272704 28361
+3276800 28413
+3280896 28491
+3284992 28494
+3289088 28508
+3293184 28542
+3297280 28579
+3301376 28682
+3305472 28689
+3309568 28765
+3313664 28697
+3317760 28734
+3321856 28764
+3325952 28910
+3330048 28843
+3334144 28895
+3338240 28970
+3342336 28952
+3346432 29095
+3350528 29037
+3354624 29198
+3358720 29146
+3362816 29262
+3366912 29229
+3371008 29210
+3375104 29242
+3379200 29359
+3383296 29338
+3387392 29422
+3391488 29375
+3395584 29482
+3399680 29576
+3403776 29506
+3407872 29556
+3411968 29626
+3416064 29678
+3420160 29837
+3424256 29745
+3428352 29721
+3432448 29813
+3436544 29847
+3440640 29835
+3444736 29929
+3448832 29955
+3452928 29892
+3457024 30063
+3461120 30043
+3465216 30116
+3469312 30032
+3473408 30062
+3477504 30102
+3481600 30326
+3485696 30148
+3489792 30304
+3493888 30230
+3497984 30408
+3502080 30383
+3506176 30338
+3510272 30496
+3514368 30413
+3518464 30453
+3522560 30486
+3526656 30516
+3530752 30564
+3534848 30642
+3538944 30774
+3543040 30658
+3547136 30696
+3551232 30751
+3555328 30835
+3559424 30786
+3563520 30826
+3567616 30851
+3571712 30897
+3575808 30932
+3579904 30957
+3584000 31000
+3588096 31038
+3592192 31062
+3596288 31100
+3600384 31138
+3604480 31168
+3608576 31206
+3612672 31251
+3616768 31287
+3620864 31332
+3624960 31354
+3629056 31400
+3633152 31613
+3637248 31463
+3641344 31511
+3645440 31530
+3649536 31585
+3653632 31754
+3657728 31627
+3661824 31693
+3665920 31767
+3670016 31727
+3674112 31775
+3678208 31807
+3682304 31836
+3686400 31877
+3690496 31906
+3694592 31983
+3698688 32019
+3702784 32051
+3706880 32118
+3710976 32099
+3715072 32150
+3719168 32153
+3723264 32246
+3727360 32242
+3731456 32272
+3735552 32336
+3739648 32340
+3743744 32378
+3747840 32441
+3751936 32473
+3756032 32476
+3760128 32576
+3764224 32524
+3768320 32566
+3772416 32706
+3776512 32695
+3780608 32672
+3784704 32772
+3788800 32752
+3792896 32786
+3796992 32919
+3801088 32863
+3805184 32961
+3809280 33032
+3813376 32962
+3817472 33026
+3821568 33123
+3825664 33074
+3829760 33216
+3833856 33127
+3837952 33151
+3842048 33208
+3846144 33322
+3850240 33269
+3854336 33301
+3858432 33333
+3862528 33366
+3866624 33401
+3870720 33436
+3874816 33471
+3878912 33515
+3883008 33544
+3887104 33581
+3891200 33619
+3895296 33668
+3899392 33695
+3903488 33733
+3907584 33759
+3911680 33790
+3915776 33855
+3919872 33868
+3923968 33884
+3928064 33920
+3932160 33971
+3936256 33998
+3940352 34038
+3944448 34055
+3948544 34106
+3952640 34145
+3956736 34163
+3960832 34236
+3964928 34269
+3969024 34283
+3973120 34321
+3977216 34350
+3981312 34392
+3985408 34483
+3989504 34469
+3993600 34494
+3997696 34558
+4001792 34564
+4005888 34611
+4009984 34645
+4014080 34681
+4018176 34690
+4022272 34749
+4026368 34759
+4030464 34787
+4034560 34869
+4038656 34913
+4042752 34891
+4046848 34962
+4050944 34996
+4055040 35014
+4059136 35069
+4063232 35179
+4067328 35116
+4071424 35231
+4075520 35264
+4079616 35297
+4083712 35258
+4087808 35371
+4091904 35326
+4096000 35422
+4100096 35463
+4104192 35421
+4108288 35520
+4112384 35550
+4116480 35526
+4120576 35632
+4124672 35634
+4128768 35731
+4132864 35766
+4136960 35717
+4141056 35741
+4145152 35780
+4149248 35834
+4153344 35868
+4157440 35893
+4161536 35932
+4165632 35956
+4169728 36094
+4173824 36030
+4177920 36175
+4182016 36082
+4186112 36226
+4190208 36138
+4194304 36181
+4202496 36269
+4210688 36332
+4218880 36487
+4227072 36555
+4235264 36544
+4243456 36627
+4251648 36708
+4259840 36762
+4268032 36823
+4276224 36908
+4284416 37036
+4292608 37039
+4300800 37088
+4308992 37166
+4317184 37336
+4325376 37330
+4333568 37385
+4341760 37469
+4349952 37537
+4358144 37602
+4366336 37667
+4374528 37763
+4382720 37834
+4390912 37944
+4399104 38028
+4407296 38040
+4415488 38112
+4423680 38167
+4431872 38302
+4440064 38298
+4448256 38376
+4456448 38441
+4464640 38598
+4472832 38576
+4481024 38667
+4489216 38757
+4497408 38786
+4505600 38941
+4513792 39008
+4521984 39005
+4530176 39088
+4538368 39186
+4546560 39317
+4554752 39254
+4562944 39343
+4571136 39397
+4579328 39489
+4587520 39603
+4595712 39647
+4603904 39685
+4612096 39778
+4620288 39966
+4628480 39917
+4636672 40109
+4644864 40114
+4653056 40090
+4661248 40341
+4669440 40316
+4677632 40319
+4685824 40420
+4694016 40456
+4702208 40539
+4710400 40625
+4718592 40646
+4726784 40828
+4734976 40786
+4743168 40940
+4751360 41034
+4759552 41072
+4767744 41126
+4775936 41193
+4784128 41333
+4792320 41324
+4800512 41346
+4808704 41487
+4816896 41525
+4825088 41600
+4833280 41830
+4841472 41748
+4849664 41856
+4857856 41909
+4866048 42064
+4874240 42031
+4882432 42148
+4890624 42171
+4898816 42181
+4907008 42330
+4915200 42434
+4923392 42500
+4931584 42475
+4939776 42627
+4947968 42755
+4956160 42677
+4964352 42826
+4972544 42943
+4980736 42974
+4988928 43017
+4997120 43038
+5005312 43194
+5013504 43282
+5021696 43227
+5029888 43320
+5038080 43376
+5046272 43443
+5054464 43537
+5062656 43606
+5070848 43744
+5079040 43803
+5087232 43855
+5095424 43931
+5103616 44021
+5111808 44198
+5120000 44157
+5128192 44207
+5136384 44307
+5144576 44372
+5152768 44557
+5160960 44414
+5169152 44479
+5177344 44551
+5185536 44790
+5193728 44673
+5201920 44763
+5210112 44844
+5218304 44914
+5226496 44968
+5234688 45244
+5242880 45222
+5251072 45205
+5259264 45299
+5267456 45311
+5275648 45389
+5283840 45463
+5292032 45532
+5300224 45605
+5308416 45751
+5316608 45736
+5324800 45848
+5332992 45878
+5341184 46057
+5349376 46007
+5357568 46092
+5365760 46157
+5373952 46228
+5382144 46309
+5390336 46373
+5398528 46451
+5406720 46507
+5414912 46586
+5423104 46662
+5431296 46781
+5439488 46809
+5447680 46975
+5455872 47039
+5464064 46988
+5472256 47098
+5480448 47214
+5488640 47193
+5496832 47272
+5505024 47447
+5513216 47495
+5521408 47534
+5529600 47550
+5537792 47719
+5545984 47685
+5554176 47764
+5562368 47824
+5570560 47899
+5578752 47958
+5586944 48036
+5595136 48115
+5603328 48171
+5611520 48323
+5619712 48306
+5627904 48381
+5636096 48512
+5644288 48534
+5652480 48588
+5660672 48681
+5668864 48740
+5677056 48800
+5685248 48893
+5693440 48971
+5701632 49021
+5709824 49080
+5718016 49226
+5726208 49220
+5734400 49298
+5742592 49370
+5750784 49435
+5758976 49503
+5767168 49619
+5775360 49646
+5783552 49836
+5791744 49871
+5799936 49869
+5808128 49915
+5816320 50040
+5824512 50099
+5832704 50154
+5840896 50229
+5849088 50275
+5857280 50374
+5865472 50494
+5873664 50581
+5881856 50609
+5890048 50671
+5898240 50747
+5906432 50956
+5914624 50933
+5922816 50957
+5931008 51067
+5939200 51193
+5947392 51219
+5955584 51261
+5963776 51268
+5971968 51311
+5980160 51587
+5988352 51564
+5996544 51673
+6004736 51599
+6012928 51769
+6021120 51733
+6029312 51803
+6037504 51888
+6045696 51937
+6053888 52008
+6062080 52093
+6070272 52143
+6078464 52238
+6086656 52306
+6094848 52355
+6103040 52446
+6111232 52529
+6119424 52558
+6127616 52665
+6135808 52698
+6144000 52791
+6152192 52901
+6160384 53014
+6168576 53078
+6176768 53043
+6184960 53127
+6193152 53192
+6201344 53271
+6209536 53388
+6217728 53402
+6225920 53464
+6234112 53649
+6242304 53607
+6250496 53671
+6258688 53738
+6266880 53821
+6275072 54005
+6283264 53971
+6291456 54020
+6299648 54232
+6307840 54161
+6316032 54252
+6324224 54299
+6332416 54372
+6340608 54441
+6348800 54509
+6356992 54595
+6365184 54652
+6373376 54731
+6381568 54795
+6389760 54857
+6397952 54960
+6406144 55015
+6414336 55067
+6422528 55170
+6430720 55203
+6438912 55270
+6447104 55427
+6455296 55439
+6463488 55573
+6471680 55578
+6479872 55636
+6488064 55692
+6496256 55757
+6504448 55877
+6512640 55900
+6520832 56069
+6529024 56044
+6537216 56112
+6545408 56177
+6553600 56265
+6561792 56319
+6569984 56390
+6578176 56455
+6586368 56533
+6594560 56596
+6602752 56668
+6610944 56736
+6619136 56806
+6627328 56885
+6635520 56948
+6643712 57027
+6651904 57092
+6660096 57175
+6668288 57237
+6676480 57315
+6684672 57374
+6692864 57429
+6701056 57596
+6709248 57589
+6717440 57687
+6725632 57720
+6733824 57835
+6742016 58421
+6750208 57959
+6758400 58019
+6766592 58061
+6774784 58167
+6782976 58200
+6791168 58279
+6799360 58451
+6807552 58539
+6815744 58489
+6823936 58548
+6832128 58673
+6840320 58737
+6848512 58788
+6856704 58829
+6864896 58894
+6873088 58989
+6881280 59034
+6889472 59179
+6897664 59197
+6905856 59278
+6914048 59382
+6922240 59427
+6930432 59459
+6938624 59528
+6946816 59577
+6955008 59659
+6963200 59872
+6971392 59846
+6979584 59880
+6987776 60074
+6995968 60140
+7004160 60144
+7012352 60197
+7020544 60250
+7028736 60291
+7036928 60361
+7045120 60466
+7053312 60580
+7061504 60585
+7069696 60671
+7077888 60756
+7086080 60820
+7094272 60847
+7102464 61022
+7110656 61083
+7118848 61077
+7127040 61168
+7135232 61199
+7143424 61286
+7151616 61511
+7159808 61394
+7168000 61571
+7176192 61543
+7184384 61625
+7192576 61701
+7200768 61750
+7208960 61823
+7217152 61928
+7225344 61967
+7233536 62064
+7241728 62128
+7249920 62169
+7258112 62245
+7266304 62309
+7274496 62430
+7282688 62476
+7290880 62516
+7299072 62597
+7307264 62684
+7315456 62763
+7323648 62836
+7331840 62876
+7340032 62967
+7348224 63038
+7356416 63084
+7364608 63181
+7372800 63334
+7380992 63344
+7389184 63410
+7397376 63483
+7405568 63611
+7413760 63586
+7421952 63683
+7430144 63767
+7438336 63904
+7446528 63912
+7454720 64098
+7462912 64003
+7471104 64179
+7479296 64316
+7487488 64268
+7495680 64271
+7503872 64369
+7512064 64491
+7520256 64510
+7528448 64535
+7536640 64610
+7544832 64776
+7553024 64832
+7561216 64854
+7569408 64921
+7577600 64949
+7585792 65096
+7593984 65189
+7602176 65220
+7610368 65257
+7618560 65348
+7626752 65439
+7634944 65547
+7643136 65533
+7651328 65663
+7659520 65758
+7667712 65902
+7675904 66435
+7684096 65998
+7692288 65999
+7700480 66194
+7708672 66211
+7716864 66230
+7725056 66221
+7733248 66303
+7741440 66387
+7749632 66529
+7757824 66514
+7766016 66621
+7774208 66643
+7782400 66687
+7790592 66861
+7798784 66862
+7806976 67003
+7815168 67037
+7823360 67020
+7831552 67118
+7839744 67195
+7847936 67350
+7856128 67324
+7864320 67390
+7872512 67560
+7880704 67523
+7888896 67586
+7897088 67654
+7905280 67749
+7913472 67822
+7921664 67880
+7929856 67938
+7938048 68013
+7946240 68085
+7954432 68153
+7962624 68225
+7970816 68304
+7979008 68361
+7987200 68429
+7995392 68512
+8003584 68591
+8011776 68641
+8019968 68722
+8028160 68788
+8036352 68887
+8044544 69110
+8052736 69085
+8060928 69196
+8069120 69131
+8077312 69237
+8085504 69357
+8093696 69368
+8101888 69643
+8110080 69597
+8118272 69609
+8126464 69648
+8134656 69748
+8142848 69919
+8151040 69898
+8159232 69981
+8167424 70067
+8175616 70028
+8183808 70218
+8192000 70272
+8200192 70357
+8208384 70410
+8216576 70514
+8224768 70503
+8232960 70623
+8241152 70720
+8249344 70659
+8257536 70779
+8265728 70792
+8273920 70978
+8282112 71039
+8290304 71013
+8298496 71213
+8306688 71203
+8314880 71231
+8323072 71298
+8331264 71347
+8339456 71517
+8347648 71609
+8355840 71575
+8364032 71642
+8372224 71709
+8380416 71824
+8388608 71855
#!/usr/bin/env python
#---------------------------------------------------------------------------------------------------
+# Example invokation:
+# % ./regress.py griffon_skampi_pt2pt.ski.dat 65536 120832
+#
+#
# Given two vectors of same length n: message size S(.. s_i ..), and communication time T( .. t_i .. )
# where t_i is the time associated to a mesage size s_i, computes the segmentation of the vectors
# in 3 segments such that linear regressions on the 3 segments maximize correlation.
if len(sys.argv) != 2 and len(sys.argv) != 4:
print("Usage : {} datafile".format(sys.argv[0]))
- print("or : {} datafile p1 p2".format(sys.argv[0]))
+ print("or : {0} datafile p1 p2".format(sys.argv[0]))
print("where : p1 < p2 belongs to sizes in datafiles")
sys.exit(-1)
Z.append( a * X[i] + b )
# compare real values and computed values
e = mean_logerr( Y[start:stop+1] , Z )
- #print(" range [%d,%d] err=%f‰ weight=%f" % (X[start],X[stop],e,(stop-start+1)/len(X)))
correl.append( (e, stop-start+1) ); # store correl. coef + number of values (segment length)
interv.append( (a,b, X[start],X[stop],e) );
for k in range(top_n_sol):
(err,interval) = result[k]
- print("\n RANK {}\n-------".format(k))
+ print(k)
+ print("\n RANK {0}\n-------".format(k))
print("** overall metric = {0}".format(err))
for (a,b,i,j,e) in interval:
print("** OPT: [{0} .. {1}] segment_metric={2} slope: {3} x + {4}".format(i,j,e,a,b))
--- /dev/null
+#!/usr/bin/python
+# This script takes the following command line parameters
+# 1) an input file containing 2 columns: message size and 1-way trip time
+# 2) the maximum relative error for a line segment
+# 3) the minimum number of points needed to justify adding a line segment
+# 4) the number of links
+# 5) the latency
+# 6) the bandwidth
+
+import sys
+
+def compute_regression(points):
+ N = len(points)
+
+ if N < 1:
+ return None
+
+ if N < 2:
+ return (0, points[0][1])
+
+ Sx = Sy = Sxx = Syy = Sxy = 0.0
+
+ for x, y in points:
+ Sx += x
+ Sy += y
+ Sxx += x*x
+ Syy += y*y
+ Sxy += x*y
+ denom = Sxx * N - Sx * Sx
+ # don't return 0 or negative values as a matter of principle...
+ m = max(sys.float_info.min, (Sxy * N - Sy * Sx) / denom)
+ b = max(sys.float_info.min, (Sxx * Sy - Sx * Sxy) / denom)
+ return (m, b)
+
+def compute_error(m, b, x, y):
+ yp = m*x+b
+ return abs(yp - y) / max(min(yp, y), sys.float_info.min)
+
+def compute_max_error(m, b, points):
+ max_error = 0.0
+ for x, y in points:
+ max_error = max(max_error, compute_error(m, b, x, y))
+ return max_error
+
+def get_max_error_point(m, b, points):
+ max_error_index = -1
+ max_error = 0.0
+
+ i = 0
+ while i < len(points):
+ x, y = points[i]
+ error = compute_error(m, b, x, y)
+ if error > max_error:
+ max_error_index = i
+ max_error = error
+ i += 1
+
+ return (max_error_index, max_error)
+
+infile_name = sys.argv[1]
+error_bound = float(sys.argv[2])
+min_seg_points = int(sys.argv[3])
+links = int(sys.argv[4])
+latency = float(sys.argv[5])
+bandwidth = float(sys.argv[6])
+
+infile = open(infile_name, 'r')
+
+# read datafile
+points = []
+for line in infile:
+ fields = line.split()
+ points.append((int(fields[0]), int(fields[1])))
+infile.close()
+
+# should sort points by x values
+points.sort()
+
+# break points up into segments
+pointsets = []
+lbi = 0
+while lbi < len(points):
+ min_ubi = lbi
+ max_ubi = len(points) - 1
+ while max_ubi - min_ubi > 1:
+ ubi = (min_ubi + max_ubi) / 2
+ m, b = compute_regression(points[lbi:ubi+1])
+ max_error = compute_max_error(m, b, points[lbi:ubi+1])
+ if max_error > error_bound:
+ max_ubi = ubi - 1
+ else:
+ min_ubi = ubi
+ ubi = max_ubi
+ if min_ubi < max_ubi:
+ m, b = compute_regression(points[lbi:max_ubi+1])
+ max_error = compute_max_error(m, b, points[lbi:max_ubi+1])
+ if max_error > error_bound:
+ ubi = min_ubi
+ pointsets.append(points[lbi:ubi+1])
+ lbi = ubi+1
+
+# try to merge larger segments if possible and compute piecewise regression
+i = 0
+segments = []
+notoutliers = 0
+while i < len(pointsets):
+ currpointset = []
+ j = i
+ while j < len(pointsets):
+ newpointset = currpointset + pointsets[j]
+ # if joining a small segment, we can delete bad points
+ if len(pointsets[j]) < min_seg_points:
+ k = 0
+ while k < len(pointsets[j]):
+ m, b = compute_regression(newpointset)
+ max_error_index, max_error = get_max_error_point(m, b, newpointset)
+ if max_error <= error_bound:
+ break
+ del newpointset[max_error_index]
+ k += 1
+ # only add new pointset if we had to delete fewer than its length
+ # points
+ if k < len(pointsets[j]):
+ i = j
+ currpointset = newpointset
+ # otherwise, we just see if it works...
+ else:
+ m, b = compute_regression(newpointset)
+ max_error = compute_max_error(m, b, newpointset)
+ if max_error > error_bound:
+ break
+ i = j
+ currpointset = newpointset
+ j += 1
+ i += 1
+ # outliers are ignored when constructing the piecewise funciton
+ if len(currpointset) < min_seg_points:
+ continue
+ notoutliers += len(currpointset)
+ m, b = compute_regression(currpointset)
+ lb = min(x for x, y in currpointset)
+ lat_factor = b / (1.0e6 * links * latency)
+ bw_factor = 1.0e6 / (m * bandwidth)
+ segments.append((lb, m, b, lat_factor, bw_factor))
+
+outliers = len(points) - notoutliers
+segments.sort()
+segments.reverse()
+
+print "/**--------- <copy/paste C code snippet in surf/network.c> -------------"
+print " * produced by:"
+print " *", " ".join(sys.argv)
+print " * outliers:", outliers
+print " * gnuplot: "
+print " plot \"%s\" using 1:2 with lines title \"data\", \\" % (infile_name)
+for lb, m, b, lat_factor, bw_factor in segments:
+ print " (x >= %d) ? %g*x+%g : \\" % (lb, m, b)
+print " 1.0 with lines title \"piecewise function\""
+print " *-------------------------------------------------------------------*/"
+print
+print "static double smpi_bandwidth_factor(double size)\n{\n"
+for lb, m, b, lat_factor, bw_factor in segments:
+ print " if (size >= %d) return %g;" % (lb, bw_factor)
+print " return 1.0;\n}\n"
+print "static double smpi_latency_factor(double size)\n{\n"
+for lb, m, b, lat_factor, bw_factor in segments:
+ print " if (size >= %d) return %g;" % (lb, lat_factor)
+print " return 1.0;\n}\n"
+print "/**--------- <copy/paste C code snippet in surf/network.c> -----------*/"
--- /dev/null
+/**--------- <copy/paste C code snippet in surf/network.c> -------------
+ * produced by:
+ * ./regression2.py ./pingpong-in.dat 0.15 30 2 2.4e-5 1.25e8
+ * outliers: 66
+ * gnuplot:
+ plot "./pingpong-in.dat" using 1:2 with lines title "data", \
+ (x >= 65472) ? 0.00850436*x+558.894 : \
+ (x >= 15424) ? 0.0114635*x+167.446 : \
+ (x >= 9376) ? 0.0136219*x+124.464 : \
+ (x >= 5776) ? 0.00735707*x+105.022 : \
+ (x >= 3484) ? 0.0103235*x+90.2886 : \
+ (x >= 1426) ? 0.0131384*x+77.3159 : \
+ (x >= 732) ? 0.0233927*x+93.6146 : \
+ (x >= 257) ? 0.0236608*x+93.7637 : \
+ (x >= 127) ? 0.0246645*x+94.0447 : \
+ (x >= 64) ? 0.037963*x+93.0877 : \
+ (x >= 0) ? 2.22507e-308*x+98.0633 : \
+ 1.0 with lines title "piecewise function"
+ *-------------------------------------------------------------------*/
+
+static double smpi_bandwidth_factor(double size)
+{
+
+ if (size >= 65472) return 0.940694;
+ if (size >= 15424) return 0.697866;
+ if (size >= 9376) return 0.58729;
+ if (size >= 5776) return 1.08739;
+ if (size >= 3484) return 0.77493;
+ if (size >= 1426) return 0.608902;
+ if (size >= 732) return 0.341987;
+ if (size >= 257) return 0.338112;
+ if (size >= 127) return 0.324353;
+ if (size >= 64) return 0.210731;
+ if (size >= 0) return 3.59539e+305;
+ return 1.0;
+}
+
+static double smpi_latency_factor(double size)
+{
+
+ if (size >= 65472) return 11.6436;
+ if (size >= 15424) return 3.48845;
+ if (size >= 9376) return 2.59299;
+ if (size >= 5776) return 2.18796;
+ if (size >= 3484) return 1.88101;
+ if (size >= 1426) return 1.61075;
+ if (size >= 732) return 1.9503;
+ if (size >= 257) return 1.95341;
+ if (size >= 127) return 1.95926;
+ if (size >= 64) return 1.93933;
+ if (size >= 0) return 2.04299;
+ return 1.0;
+}
+
+/**--------- <copy/paste C code snippet in surf/network.c> -----------*/
--- /dev/null
+/* A simple example pingpong pogram to test MPI_Send and MPI_Recv */
+
+/* Copyright (c) 2009, 2010. The SimGrid Team.
+ * All rights reserved. */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include <mpi.h>
+
+int main(int argc, char *argv[])
+{
+ int rank;
+ int size;
+ MPI_Status status;
+
+ int n = 0, m = 0, bytes = 0, workusecs = 0;
+ int currusecs;
+
+ char *buf = NULL;
+ int i, j;
+ struct timeval start_time, stop_time;
+ struct timeval start_pause, curr_pause;
+ unsigned long usecs;
+
+ MPI_Init(&argc, &argv); /* Initialize MPI */
+ MPI_Comm_size(MPI_COMM_WORLD, &size); /* Get nr of tasks */
+ MPI_Comm_rank(MPI_COMM_WORLD, &rank); /* Get id of this process */
+
+ if (size != 2) {
+ printf("run this program with exactly 2 processes (-np 2)\n");
+ MPI_Finalize();
+ exit(0);
+ }
+
+ if (0 == rank) {
+ if (argc > 1 && isdigit(argv[1][0])) {
+ n = atoi(argv[1]);
+ }
+ if (argc > 2 && isdigit(argv[2][0])) {
+ m = atoi(argv[2]);
+ }
+ if (argc > 3 && isdigit(argv[3][0])) {
+ bytes = atoi(argv[3]);
+ }
+ if (argc > 4 && isdigit(argv[4][0])) {
+ workusecs = atoi(argv[4]);
+ }
+ buf = malloc(sizeof(char) * bytes);
+ for (i = 0; i < bytes; i++) buf[i] = i % 256;
+ MPI_Send(&n, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
+ MPI_Send(&m, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
+ MPI_Send(&bytes, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
+ MPI_Send(&workusecs, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);
+ MPI_Barrier(MPI_COMM_WORLD);
+ gettimeofday(&start_time, NULL);
+ for (i = 0; i < n; i++) {
+ for (j = 0; j < m; j++) {
+ MPI_Send(buf, bytes, MPI_CHAR, 1, 0, MPI_COMM_WORLD);
+ gettimeofday(&start_pause, NULL);
+ currusecs = 0;
+ while (currusecs < workusecs) {
+ gettimeofday(&curr_pause, NULL);
+ currusecs = (curr_pause.tv_sec - start_pause.tv_sec) * 1e6 + curr_pause.tv_usec - start_pause.tv_usec;
+ }
+ }
+ MPI_Recv(buf, bytes, MPI_CHAR, 1, 0, MPI_COMM_WORLD, &status);
+ }
+ gettimeofday(&stop_time, NULL);
+ usecs = (stop_time.tv_sec - start_time.tv_sec) * 1e6 + stop_time.tv_usec - start_time.tv_usec;
+ printf("n: %d m: %d bytes: %d sleep: %d usecs: %u\n", n, m, bytes, workusecs, usecs);
+ } else {
+ MPI_Recv(&n, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
+ MPI_Recv(&m, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
+ MPI_Recv(&bytes, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
+ MPI_Recv(&workusecs, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &status);
+ buf = malloc(sizeof(char) * bytes);
+ MPI_Barrier(MPI_COMM_WORLD);
+ for (i = 0; i < n; i++) {
+ for (j = 0; j < m; j++) {
+ MPI_Recv(buf, bytes, MPI_CHAR, 0, 0, MPI_COMM_WORLD, &status);
+ }
+ MPI_Send(buf, bytes, MPI_CHAR, 0, 0, MPI_COMM_WORLD);
+ }
+ }
+ free(buf);
+ MPI_Finalize();
+ return 0;
+}
XBT_PUBLIC(void) SIMIX_comm_set_copy_data_callback(void (*callback) (smx_action_t, size_t));
XBT_PUBLIC(void) SIMIX_comm_copy_pointer_callback(smx_action_t comm, size_t buff_size);
XBT_PUBLIC(void) SIMIX_comm_copy_buffer_callback(smx_action_t comm, size_t buff_size);
+XBT_PUBLIC(void) smpi_comm_copy_data_callback(smx_action_t comm, size_t buff_size);
+
XBT_PUBLIC(smx_action_t) SIMIX_comm_get_send_match(smx_rdv_t rdv, int (*match_fun)(void*, void*), void* data);
XBT_PUBLIC(int) SIMIX_comm_has_send_match(smx_rdv_t rdv, int (*match_fun)(void*, void*), void* data);
XBT_PUBLIC(int) SIMIX_comm_has_recv_match(smx_rdv_t rdv, int (*match_fun)(void*, void*), void* data);
#include <xbt/log.h>
#include <xbt/asserts.h>
-#define sleep(x) smpi_sleep(x)
-#define gettimeofday(x, y) smpi_gettimeofday(x, y)
-
#endif
#include <xbt/misc.h>
#include <xbt/function_types.h>
+#define sleep(x) smpi_sleep(x)
+#define gettimeofday(x, y) smpi_gettimeofday(x, y)
+
#define MPI_CALL(type,name,args) \
type name args __attribute__((weak)); \
type P##name args
} MPI_Status;
#define MPI_STATUS_IGNORE NULL
+#define MPI_STATUSES_IGNORE NULL
#define MPI_DATATYPE_NULL NULL
extern MPI_Datatype MPI_CHAR;
#include <smpi/smpi.h>
#include <f2c.h>
+XBT_PUBLIC_DATA(__thread int) smpi_current_rank;
+
XBT_PUBLIC(int) smpi_process_argc(void);
XBT_PUBLIC(int) smpi_process_getarg(integer* index, char* dst, ftnlen len);
XBT_PUBLIC(int) smpi_global_size(void);
if (*task)
XBT_CRITICAL
- ("MSG_task_get() was asked to write in a non empty task struct.");
+ ("MSG_task_irecv() was asked to write in a non empty task struct.");
/* Try to receive it by calling SIMIX network layer */
msg_comm_t comm = xbt_new0(s_msg_comm_t, 1);
XBT_DEBUG("Destroy action %p (refcount: %d), state: %d",
action, action->comm.refcount, action->state);
- xbt_assert(action->comm.refcount > 0,
- "The refcount of comm %p is already 0 before decreasing it. "
- "That's a bug!", action);
-
+ if (action->comm.refcount <= 0) {
+ xbt_backtrace_display_current();
+ xbt_die("the refcount of comm %p is already 0 before decreasing it. "
+ "That's a bug!", action);
+ }
action->comm.refcount--;
if (action->comm.refcount > 0)
return;
}
SIMIX_comm_start(action);
- return action;
+ return (detached ? NULL : action);
}
smx_action_t SIMIX_comm_irecv(smx_process_t dst_proc, smx_rdv_t rdv,
memcpy(comm->comm.dst_buff, comm->comm.src_buff, buff_size);
}
+void smpi_comm_copy_data_callback(smx_action_t comm, size_t buff_size)
+{
+ memcpy(comm->comm.dst_buff, comm->comm.src_buff, buff_size);
+ if (comm->comm.detached) // if this is a detached send, the source buffer was duplicated by SMPI sender to make the original buffer available to the application ASAP
+ free(comm->comm.src_buff);
+}
+
/**
* \brief Copy the communication data from the sender's buffer to the receiver's one
* \param comm The communication
if (comm->comm.dst_buff_size)
*comm->comm.dst_buff_size = buff_size;
+<<<<<<< HEAD
+ if (buff_size > 0)
+ (*SIMIX_comm_copy_data_callback) (comm, buff_size);
+=======
if (buff_size == 0)
return;
SIMIX_comm_copy_data_callback(comm, buff_size);
+>>>>>>> master
/* Set the copied flag so we copy data only once */
/* (this function might be called from both communication ends) */
xbt_assert(ref, "Cannot match recv against null reference");
xbt_assert(req, "Cannot match recv against null request");
- return req->comm == ref->comm
- && (ref->src == MPI_ANY_SOURCE || req->src == ref->src)
+ return (ref->src == MPI_ANY_SOURCE || req->src == ref->src)
&& (ref->tag == MPI_ANY_TAG || req->tag == ref->tag);
}
xbt_assert(ref, "Cannot match send against null reference");
xbt_assert(req, "Cannot match send against null request");
- return req->comm == ref->comm
- && (req->src == MPI_ANY_SOURCE || req->src == ref->src)
+ return (req->src == MPI_ANY_SOURCE || req->src == ref->src)
&& (req->tag == MPI_ANY_TAG || req->tag == ref->tag);
}
request = xbt_new(s_smpi_mpi_request_t, 1);
request->buf = buf;
+ // FIXME: this will have to be changed to support non-contiguous datatypes
request->size = smpi_datatype_size(datatype) * count;
request->src = src;
request->dst = dst;
void smpi_mpi_start(MPI_Request request)
{
smx_rdv_t mailbox;
+ int detached = 0;
xbt_assert(!request->action,
"Cannot (re)start a non-finished communication");
if(request->flags & RECV) {
print_request("New recv", request);
mailbox = smpi_process_mailbox();
+ // FIXME: SIMIX does not yet support non-contiguous datatypes
request->action = SIMIX_req_comm_irecv(mailbox, request->buf, &request->size, &match_recv, request);
} else {
print_request("New send", request);
- mailbox = smpi_process_remote_mailbox(request->dst);
- request->action = SIMIX_req_comm_isend(mailbox, request->size, -1.0,
- request->buf, request->size, &match_send, request, 0);
+ mailbox = smpi_process_remote_mailbox(
+ smpi_group_index(smpi_comm_group(request->comm), request->dst));
+ // FIXME: SIMIX does not yet support non-contiguous datatypes
+
+ if (request->size < 64*1024 ) { // eager mode => detached send (FIXME: this limit should be configurable)
+ void *oldbuf = request->buf;
+ detached = 1;
+ request->buf = malloc(request->size);
+ memcpy(request->buf,oldbuf,request->size);
+ XBT_DEBUG("Send request %p is detached; buf %p copied into %p",request,oldbuf,request->buf);
+ } else {
+ XBT_DEBUG("Send request %p is not detached (buf: %p)",request,request->buf);
+ }
+ request->action =
+ SIMIX_req_comm_isend(mailbox, request->size, -1.0,
+ request->buf, request->size, &match_send, request,
+ // detach if msg size < eager/rdv switch limit
+ detached);
+
#ifdef HAVE_TRACING
SIMIX_req_set_category (request->action, TRACE_internal_smpi_get_category());
#endif
void smpi_mpi_startall(int count, MPI_Request * requests)
{
- int i;
+ int i;
for(i = 0; i < count; i++) {
smpi_mpi_start(requests[i]);
status->MPI_SOURCE = req->src;
status->MPI_TAG = req->tag;
status->MPI_ERROR = MPI_SUCCESS;
+ // FIXME: really this should just contain the count of receive-type blocks,
+ // right?
status->count = req->size;
}
print_request("Finishing", req);
}
}
-int smpi_mpi_test(MPI_Request * request, MPI_Status * status)
-{
- int flag = SIMIX_req_comm_test((*request)->action);
+int smpi_mpi_test(MPI_Request * request, MPI_Status * status) {
+int flag;
+ if ((*request)->action == NULL)
+ flag = 1;
+ else
+ flag = SIMIX_req_comm_test((*request)->action);
if(flag) {
- smpi_mpi_wait(request, status);
- }
- return flag;
+ smpi_mpi_wait(request, status);
+ }
+ return flag;
}
int smpi_mpi_testany(int count, MPI_Request requests[], int *index,
}
}
if(size > 0) {
- *index = SIMIX_req_comm_testany(comms);
- *index = map[*index];
- if(*index != MPI_UNDEFINED) {
+ i = SIMIX_req_comm_testany(comms);
+ // FIXME: MPI_UNDEFINED or does SIMIX have a return code?
+ if(i != MPI_UNDEFINED) {
+ *index = map[i];
smpi_mpi_wait(&requests[*index], status);
flag = 1;
}
void smpi_mpi_wait(MPI_Request * request, MPI_Status * status)
{
print_request("Waiting", *request);
- SIMIX_req_comm_wait((*request)->action, -1.0);
+ if ((*request)->action != NULL )
+ SIMIX_req_comm_wait((*request)->action, -1.0);
finish_wait(request, status);
}
size = 0;
XBT_DEBUG("Wait for one of");
for(i = 0; i < count; i++) {
- if(requests[i] != MPI_REQUEST_NULL) {
+ if((requests[i] != MPI_REQUEST_NULL) && (requests[i]->action != NULL)) {
print_request(" ", requests[i]);
xbt_dynar_push(comms, &requests[i]->action);
map[size] = i;
}
}
if(size > 0) {
- index = SIMIX_req_comm_waitany(comms);
- index = map[index];
- finish_wait(&requests[index], status);
+ i = SIMIX_req_comm_waitany(comms);
+ // FIXME: MPI_UNDEFINED or does SIMIX have a return code?
+ if (i != MPI_UNDEFINED) {
+ index = map[i];
+ finish_wait(&requests[index], status);
+ }
}
xbt_free(map);
xbt_dynar_free(&comms);
int root, MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, src, index, sendsize, recvsize;
+ int rank, size, src, index;
+ MPI_Aint lb = 0, recvext = 0;
MPI_Request *requests;
rank = smpi_comm_rank(comm);
// Send buffer to root
smpi_mpi_send(sendbuf, sendcount, sendtype, root, system_tag, comm);
} else {
- sendsize = smpi_datatype_size(sendtype);
- recvsize = smpi_datatype_size(recvtype);
+ // FIXME: check for errors
+ smpi_datatype_extent(recvtype, &lb, &recvext);
// Local copy from root
- memcpy(&((char *) recvbuf)[root * recvcount * recvsize], sendbuf,
- sendcount * sendsize * sizeof(char));
+ smpi_datatype_copy(sendbuf, sendcount, sendtype,
+ (char *)recvbuf + root * recvcount * recvext, recvcount, recvtype);
// Receive buffers from senders
requests = xbt_new(MPI_Request, size - 1);
index = 0;
for(src = 0; src < size; src++) {
if(src != root) {
- requests[index] = smpi_irecv_init(&((char *) recvbuf)
- [src * recvcount * recvsize],
- recvcount, recvtype, src,
- system_tag, comm);
+ requests[index] = smpi_irecv_init((char *)recvbuf + src * recvcount * recvext,
+ recvcount, recvtype,
+ src, system_tag, comm);
index++;
}
}
MPI_Datatype recvtype, int root, MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, src, index, sendsize;
+ int rank, size, src, index;
+ MPI_Aint lb = 0, recvext = 0;
MPI_Request *requests;
rank = smpi_comm_rank(comm);
// Send buffer to root
smpi_mpi_send(sendbuf, sendcount, sendtype, root, system_tag, comm);
} else {
- sendsize = smpi_datatype_size(sendtype);
+ // FIXME: check for errors
+ smpi_datatype_extent(recvtype, &lb, &recvext);
// Local copy from root
- memcpy(&((char *) recvbuf)[displs[root]], sendbuf,
- sendcount * sendsize * sizeof(char));
+ smpi_datatype_copy(sendbuf, sendcount, sendtype,
+ (char *)recvbuf + displs[root] * recvext,
+ recvcounts[root], recvtype);
// Receive buffers from senders
requests = xbt_new(MPI_Request, size - 1);
index = 0;
for(src = 0; src < size; src++) {
if(src != root) {
requests[index] =
- smpi_irecv_init(&((char *) recvbuf)[displs[src]],
- recvcounts[src], recvtype, src, system_tag,
- comm);
+ smpi_irecv_init((char *)recvbuf + displs[src] * recvext,
+ recvcounts[src], recvtype, src, system_tag, comm);
index++;
}
}
MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, other, index, sendsize, recvsize;
+ int rank, size, other, index;
+ MPI_Aint lb = 0, recvext = 0;
MPI_Request *requests;
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
- sendsize = smpi_datatype_size(sendtype);
- recvsize = smpi_datatype_size(recvtype);
+ // FIXME: check for errors
+ smpi_datatype_extent(recvtype, &lb, &recvext);
// Local copy from self
- memcpy(&((char *) recvbuf)[rank * recvcount * recvsize], sendbuf,
- sendcount * sendsize * sizeof(char));
+ smpi_datatype_copy(sendbuf, sendcount, sendtype,
+ (char *)recvbuf + rank * recvcount * recvext, recvcount,
+ recvtype);
// Send/Recv buffers to/from others;
requests = xbt_new(MPI_Request, 2 * (size - 1));
index = 0;
smpi_isend_init(sendbuf, sendcount, sendtype, other, system_tag,
comm);
index++;
- requests[index] = smpi_irecv_init(&((char *) recvbuf)
- [other * recvcount * recvsize],
- recvcount, recvtype, other,
+ requests[index] = smpi_irecv_init((char *)recvbuf + other * recvcount * recvext,
+ recvcount, recvtype, other,
system_tag, comm);
index++;
}
MPI_Datatype recvtype, MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, other, index, sendsize;
+ int rank, size, other, index;
+ MPI_Aint lb = 0, recvext = 0;
MPI_Request *requests;
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
- sendsize = smpi_datatype_size(sendtype);
+ // FIXME: check for errors
+ smpi_datatype_extent(recvtype, &lb, &recvext);
// Local copy from self
- memcpy(&((char *) recvbuf)[displs[rank]], sendbuf,
- sendcount * sendsize * sizeof(char));
+ smpi_datatype_copy(sendbuf, sendcount, sendtype,
+ (char *)recvbuf + displs[rank] * recvext,
+ recvcounts[rank], recvtype);
// Send buffers to others;
requests = xbt_new(MPI_Request, 2 * (size - 1));
index = 0;
comm);
index++;
requests[index] =
- smpi_irecv_init(&((char *) recvbuf)[displs[other]],
- recvcounts[other], recvtype, other, system_tag,
- comm);
+ smpi_irecv_init((char *)recvbuf + displs[other] * recvext, recvcounts[other],
+ recvtype, other, system_tag, comm);
index++;
}
}
int root, MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, dst, index, sendsize, recvsize;
+ int rank, size, dst, index;
+ MPI_Aint lb = 0, sendext = 0;
MPI_Request *requests;
rank = smpi_comm_rank(comm);
smpi_mpi_recv(recvbuf, recvcount, recvtype, root, system_tag, comm,
MPI_STATUS_IGNORE);
} else {
- sendsize = smpi_datatype_size(sendtype);
- recvsize = smpi_datatype_size(recvtype);
+ // FIXME: check for errors
+ smpi_datatype_extent(sendtype, &lb, &sendext);
// Local copy from root
- memcpy(recvbuf, &((char *) sendbuf)[root * sendcount * sendsize],
- recvcount * recvsize * sizeof(char));
+ smpi_datatype_copy((char *)sendbuf + root * sendcount * sendext,
+ sendcount, sendtype, recvbuf, recvcount, recvtype);
// Send buffers to receivers
requests = xbt_new(MPI_Request, size - 1);
index = 0;
for(dst = 0; dst < size; dst++) {
if(dst != root) {
- requests[index] = smpi_isend_init(&((char *) sendbuf)
- [dst * sendcount * sendsize],
+ requests[index] = smpi_isend_init((char *)sendbuf + dst * sendcount * sendext,
sendcount, sendtype, dst,
system_tag, comm);
index++;
MPI_Datatype recvtype, int root, MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, dst, index, recvsize;
+ int rank, size, dst, index;
+ MPI_Aint lb = 0, sendext = 0;
MPI_Request *requests;
rank = smpi_comm_rank(comm);
smpi_mpi_recv(recvbuf, recvcount, recvtype, root, system_tag, comm,
MPI_STATUS_IGNORE);
} else {
- recvsize = smpi_datatype_size(recvtype);
+ // FIXME: check for errors
+ smpi_datatype_extent(sendtype, &lb, &sendext);
// Local copy from root
- memcpy(recvbuf, &((char *) sendbuf)[displs[root]],
- recvcount * recvsize * sizeof(char));
+ smpi_datatype_copy((char *)sendbuf + displs[root] * sendext, sendcounts[root],
+ sendtype, recvbuf, recvcount, recvtype);
// Send buffers to receivers
requests = xbt_new(MPI_Request, size - 1);
index = 0;
for(dst = 0; dst < size; dst++) {
if(dst != root) {
requests[index] =
- smpi_isend_init(&((char *) sendbuf)[displs[dst]],
- sendcounts[dst], sendtype, dst, system_tag,
- comm);
+ smpi_isend_init((char *)sendbuf + displs[dst] * sendext, sendcounts[dst],
+ sendtype, dst, system_tag, comm);
index++;
}
}
MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, src, index, datasize;
+ int rank, size, src, index;
+ MPI_Aint lb = 0, dataext = 0;
MPI_Request *requests;
void **tmpbufs;
// Send buffer to root
smpi_mpi_send(sendbuf, count, datatype, root, system_tag, comm);
} else {
- datasize = smpi_datatype_size(datatype);
+ // FIXME: check for errors
+ smpi_datatype_extent(datatype, &lb, &dataext);
// Local copy from root
- memcpy(recvbuf, sendbuf, count * datasize * sizeof(char));
+ smpi_datatype_copy(sendbuf, count, datatype, recvbuf, count, datatype);
// Receive buffers from senders
//TODO: make a MPI_barrier here ?
requests = xbt_new(MPI_Request, size - 1);
index = 0;
for(src = 0; src < size; src++) {
if(src != root) {
- tmpbufs[index] = xbt_malloc(count * datasize);
+ // FIXME: possibly overkill we we have contiguous/noncontiguous data
+ // mapping...
+ tmpbufs[index] = xbt_malloc(count * dataext);
requests[index] =
smpi_irecv_init(tmpbufs[index], count, datatype, src,
system_tag, comm);
{
smpi_mpi_reduce(sendbuf, recvbuf, count, datatype, op, 0, comm);
smpi_mpi_bcast(recvbuf, count, datatype, 0, comm);
-
-/*
-FIXME: buggy implementation
-
- int system_tag = 666;
- int rank, size, other, index, datasize;
- MPI_Request* requests;
- void** tmpbufs;
-
- rank = smpi_comm_rank(comm);
- size = smpi_comm_size(comm);
- datasize = smpi_datatype_size(datatype);
- // Local copy from self
- memcpy(recvbuf, sendbuf, count * datasize * sizeof(char));
- // Send/Recv buffers to/from others;
- //TODO: make a MPI_barrier here ?
- requests = xbt_new(MPI_Request, 2 * (size - 1));
- tmpbufs = xbt_new(void*, size - 1);
- index = 0;
- for(other = 0; other < size; other++) {
- if(other != rank) {
- tmpbufs[index / 2] = xbt_malloc(count * datasize);
- requests[index] = smpi_mpi_isend(sendbuf, count, datatype, other, system_tag, comm);
- requests[index + 1] = smpi_mpi_irecv(tmpbufs[index / 2], count, datatype, other, system_tag, comm);
- index += 2;
- }
- }
- // Wait for completion of all comms.
- for(other = 0; other < 2 * (size - 1); other++) {
- index = smpi_mpi_waitany(size - 1, requests, MPI_STATUS_IGNORE);
- if(index == MPI_UNDEFINED) {
- break;
- }
- if((index & 1) == 1) {
- // Request is odd: it's a irecv
- smpi_op_apply(op, tmpbufs[index / 2], recvbuf, &count, &datatype);
- }
- }
- for(index = 0; index < size - 1; index++) {
- xbt_free(tmpbufs[index]);
- }
- xbt_free(tmpbufs);
- xbt_free(requests);
-*/
}
void smpi_mpi_scan(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op, MPI_Comm comm)
{
int system_tag = 666;
- int rank, size, other, index, datasize;
- int total;
+ int rank, size, other, index;
+ MPI_Aint lb = 0, dataext = 0;
MPI_Request *requests;
void **tmpbufs;
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
- datasize = smpi_datatype_size(datatype);
+
+ // FIXME: check for errors
+ smpi_datatype_extent(datatype, &lb, &dataext);
+
// Local copy from self
- memcpy(recvbuf, sendbuf, count * datasize * sizeof(char));
+ smpi_datatype_copy(sendbuf, count, datatype, recvbuf, count, datatype);
+
// Send/Recv buffers to/from others;
- total = rank + (size - (rank + 1));
- requests = xbt_new(MPI_Request, total);
+ requests = xbt_new(MPI_Request, size - 1);
tmpbufs = xbt_new(void *, rank);
index = 0;
for(other = 0; other < rank; other++) {
- tmpbufs[index] = xbt_malloc(count * datasize);
+ // FIXME: possibly overkill we we have contiguous/noncontiguous data
+ // mapping...
+ tmpbufs[index] = xbt_malloc(count * dataext);
requests[index] =
smpi_irecv_init(tmpbufs[index], count, datatype, other, system_tag,
comm);
}
// Wait for completion of all comms.
smpi_mpi_startall(size - 1, requests);
- for(other = 0; other < total; other++) {
+ for(other = 0; other < size - 1; other++) {
index = smpi_mpi_waitany(size - 1, requests, MPI_STATUS_IGNORE);
if(index == MPI_UNDEFINED) {
break;
smpi_op_apply(op, tmpbufs[index], recvbuf, &count, &datatype);
}
}
- for(index = 0; index < size - 1; index++) {
+ for(index = 0; index < rank; index++) {
xbt_free(tmpbufs[index]);
}
xbt_free(tmpbufs);
#include "xbt/ex.h"
#include "surf/surf.h"
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+#include <stdio.h>
+
XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_bench, smpi,
"Logging specific to SMPI (benchmarking)");
-xbt_dict_t allocs = NULL; /* Allocated on first use */
-xbt_dict_t samples = NULL; /* Allocated on first use */
-xbt_dict_t calls = NULL; /* Allocated on first use */
+/* Shared allocations are handled through shared memory segments.
+ * Associated data and metadata are used as follows:
+ *
+ * mmap #1
+ * `allocs' dict ---- -.
+ * ---------- shared_data_t shared_metadata_t / | | |
+ * .->| <name> | ---> -------------------- <--. ----------------- | | | |
+ * | ---------- | fd of <name> | | | size of mmap | --| | | |
+ * | | count (2) | |-- | data | \ | | |
+ * `----------------- | <name> | | ----------------- ---- |
+ * -------------------- | ^ |
+ * | | |
+ * | | `allocs_metadata' dict |
+ * | | ---------------------- |
+ * | `-- | <addr of mmap #1> |<-'
+ * | .-- | <addr of mmap #2> |<-.
+ * | | ---------------------- |
+ * | | |
+ * | | |
+ * | | |
+ * | | mmap #2 |
+ * | v ---- -'
+ * | shared_metadata_t / | |
+ * | ----------------- | | |
+ * | | size of mmap | --| | |
+ * `-- | data | | | |
+ * ----------------- | | |
+ * \ | |
+ * ----
+ */
+
+#define PTR_STRLEN (2 + 2 * sizeof(void*) + 1)
+
+xbt_dict_t allocs = NULL; /* Allocated on first use */
+xbt_dict_t allocs_metadata = NULL; /* Allocated on first use */
+xbt_dict_t samples = NULL; /* Allocated on first use */
+xbt_dict_t calls = NULL; /* Allocated on first use */
+__thread int smpi_current_rank = 0; /* Updated after each MPI call */
typedef struct {
+ int fd;
int count;
- char data[];
+ char* loc;
} shared_data_t;
+typedef struct {
+ size_t size;
+ shared_data_t* data;
+} shared_metadata_t;
+
+static size_t shm_size(int fd) {
+ struct stat st;
+
+ if(fstat(fd, &st) < 0) {
+ xbt_die("Could not stat fd %d: %s", fd, strerror(errno));
+ }
+ return (size_t)st.st_size;
+}
+
+static void* shm_map(int fd, size_t size, shared_data_t* data) {
+ void* mem;
+ char loc[PTR_STRLEN];
+ shared_metadata_t* meta;
+
+ if(size > shm_size(fd)) {
+ if(ftruncate(fd, (off_t)size) < 0) {
+ xbt_die("Could not truncate fd %d to %zu: %s", fd, size, strerror(errno));
+ }
+ }
+ mem = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
+ if(mem == MAP_FAILED) {
+ xbt_die("Could not map fd %d: %s", fd, strerror(errno));
+ }
+ if(!allocs_metadata) {
+ allocs_metadata = xbt_dict_new();
+ }
+ snprintf(loc, PTR_STRLEN, "%p", mem);
+ meta = xbt_new(shared_metadata_t, 1);
+ meta->size = size;
+ meta->data = data;
+ xbt_dict_set(allocs_metadata, loc, meta, &free);
+ XBT_DEBUG("MMAP %zu to %p", size, mem);
+ return mem;
+}
+
typedef struct {
int count;
double sum;
void smpi_bench_begin(void)
{
xbt_os_timer_start(smpi_process_timer());
+ smpi_current_rank = smpi_process_index();
}
void smpi_bench_end(void)
unsigned int smpi_sleep(unsigned int secs)
{
+ smpi_bench_end();
smpi_execute((double) secs);
+ smpi_bench_begin();
return secs;
}
int smpi_gettimeofday(struct timeval *tv, struct timezone *tz)
{
- double now = SIMIX_get_clock();
-
+ double now;
+ smpi_bench_end();
+ now = SIMIX_get_clock();
if (tv) {
- tv->tv_sec = (time_t) now;
- tv->tv_usec = (suseconds_t) (now * 1e6);
+ tv->tv_sec = (time_t)now;
+ tv->tv_usec = (suseconds_t)((now - tv->tv_sec) * 1e6);
}
+ smpi_bench_begin();
return 0;
}
void *smpi_shared_malloc(size_t size, const char *file, int line)
{
- char *loc = bprintf("%s:%d:%zu", file, line, size);
+ char *loc = bprintf("%zu_%s_%d", (size_t)getpid(), file, line);
+ size_t len = strlen(loc);
+ size_t i;
+ int fd;
+ void* mem;
shared_data_t *data;
+ for(i = 0; i < len; i++) {
+ /* Make the 'loc' ID be a flat filename */
+ if(loc[i] == '/') {
+ loc[i] = '_';
+ }
+ }
if (!allocs) {
allocs = xbt_dict_new_homogeneous(free);
}
data = xbt_dict_get_or_null(allocs, loc);
- if (!data) {
- data = (shared_data_t *) xbt_malloc0(sizeof(int) + size);
+ if(!data) {
+ fd = shm_open(loc, O_RDWR | O_CREAT | O_EXCL, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
+ if(fd < 0) {
+ switch(errno) {
+ case EEXIST:
+ xbt_die("Please cleanup /dev/shm/%s", loc);
+ default:
+ xbt_die("An unhandled error occured while opening %s: %s", loc, strerror(errno));
+ }
+ }
+ data = xbt_new(shared_data_t, 1);
+ data->fd = fd;
data->count = 1;
+ data->loc = loc;
+ mem = shm_map(fd, size, data);
+ if(shm_unlink(loc) < 0) {
+ XBT_WARN("Could not early unlink %s: %s", loc, strerror(errno));
+ }
xbt_dict_set(allocs, loc, data, NULL);
+ XBT_DEBUG("Mapping %s at %p through %d", loc, mem, fd);
} else {
+ mem = shm_map(data->fd, size, data);
data->count++;
}
- free(loc);
- return data->data;
+ XBT_DEBUG("Malloc %zu in %p (metadata at %p)", size, mem, data);
+ return mem;
}
void smpi_shared_free(void *ptr)
{
- shared_data_t *data = (shared_data_t *) ((int *) ptr - 1);
- char *loc;
+ char loc[PTR_STRLEN];
+ shared_metadata_t* meta;
+ shared_data_t* data;
if (!allocs) {
XBT_WARN("Cannot free: nothing was allocated");
return;
}
- loc = xbt_dict_get_key(allocs, data);
- if (!loc) {
+ if(!allocs_metadata) {
+ XBT_WARN("Cannot free: no metadata was allocated");
+ }
+ snprintf(loc, PTR_STRLEN, "%p", ptr);
+ meta = (shared_metadata_t*)xbt_dict_get_or_null(allocs_metadata, loc);
+ if (!meta) {
XBT_WARN("Cannot free: %p was not shared-allocated by SMPI", ptr);
return;
}
+ data = meta->data;
+ if(!data) {
+ XBT_WARN("Cannot free: something is broken in the metadata link");
+ return;
+ }
+ if(munmap(ptr, meta->size) < 0) {
+ XBT_WARN("Unmapping of fd %d failed: %s", data->fd, strerror(errno));
+ }
data->count--;
if (data->count <= 0) {
- xbt_dict_remove(allocs, loc);
+ close(data->fd);
+ xbt_dict_remove(allocs, data->loc);
+ free(data->loc);
}
}
/**
* Build the tree depending on a process rank (index) and the group size (extent)
- * @param index the rank of the calling process
- * @param extent the total number of processes
+ * @param root the rank of the tree root
+ * @param rank the rank of the calling process
+ * @param size the total number of processes
**/
-static void build_tree(int index, int extent, proc_tree_t * tree)
+static void build_tree(int root, int rank, int size, proc_tree_t * tree)
{
- int places = (*tree)->PROCTREE_A * index;
- int i, ch, pr;
+ int index = (rank - root + size) % size;
+ int firstChildIdx = index * (*tree)->PROCTREE_A + 1;
+ int i;
- (*tree)->me = index;
- (*tree)->root = 0;
- for (i = 1; i <= (*tree)->PROCTREE_A; i++) {
- ++places;
- ch = (*tree)->PROCTREE_A * index + i + (*tree)->root;
- ch %= extent;
- if (places < extent) {
- (*tree)->child[i - 1] = ch;
- (*tree)->numChildren++;
- }
+ (*tree)->me = rank;
+ (*tree)->root = root;
+
+ for (i = 0; i < (*tree)->PROCTREE_A && firstChildIdx + i < size; i++) {
+ (*tree)->child[i] = (firstChildIdx + i + root) % size;
+ (*tree)->numChildren++;
}
- if (index == (*tree)->root) {
+ if (rank == root) {
(*tree)->isRoot = 1;
} else {
(*tree)->isRoot = 0;
- pr = (index - 1) / (*tree)->PROCTREE_A;
- (*tree)->parent = pr;
+ (*tree)->parent = (((index - 1) / (*tree)->PROCTREE_A) + root) % size;
}
}
* bcast
**/
static void tree_bcast(void *buf, int count, MPI_Datatype datatype,
- int root, MPI_Comm comm, proc_tree_t tree)
+ MPI_Comm comm, proc_tree_t tree)
{
int system_tag = 999; // used negative int but smpi_create_request() declares this illegal (to be checked)
int rank, i;
* anti-bcast
**/
static void tree_antibcast(void *buf, int count, MPI_Datatype datatype,
- int root, MPI_Comm comm, proc_tree_t tree)
+ MPI_Comm comm, proc_tree_t tree)
{
int system_tag = 999; // used negative int but smpi_create_request() declares this illegal (to be checked)
int rank, i;
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
- build_tree(rank, size, &tree);
- tree_bcast(buf, count, datatype, root, comm, tree);
+ build_tree(root, rank, size, &tree);
+ tree_bcast(buf, count, datatype, comm, tree);
free_tree(tree);
}
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
- build_tree(rank, size, &tree);
- tree_antibcast(&dummy, 1, MPI_CHAR, 0, comm, tree);
- tree_bcast(&dummy, 1, MPI_CHAR, 0, comm, tree);
+ build_tree(0, rank, size, &tree);
+ tree_antibcast(&dummy, 1, MPI_CHAR, comm, tree);
+ tree_bcast(&dummy, 1, MPI_CHAR, comm, tree);
free_tree(tree);
}
* Alltoall Bruck
*
* Openmpi calls this routine when the message size sent to each rank < 2000 bytes and size < 12
+ * FIXME: uh, check smpi_pmpi again, but this routine is called for > 12, not
+ * less...
**/
int smpi_coll_tuned_alltoall_bruck(void *sendbuf, int sendcount,
MPI_Datatype sendtype, void *recvbuf,
int system_tag = 777;
int i, rank, size, err, count;
MPI_Aint lb;
- MPI_Aint sendextent = 0;
- MPI_Aint recvextent = 0;
+ MPI_Aint sendext = 0;
+ MPI_Aint recvext = 0;
MPI_Request *requests;
// FIXME: check implementation
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
XBT_DEBUG("<%d> algorithm alltoall_bruck() called.", rank);
- err = smpi_datatype_extent(sendtype, &lb, &sendextent);
- err = smpi_datatype_extent(recvtype, &lb, &recvextent);
+ err = smpi_datatype_extent(sendtype, &lb, &sendext);
+ err = smpi_datatype_extent(recvtype, &lb, &recvext);
/* Local copy from self */
err =
- smpi_datatype_copy(&((char *) sendbuf)[rank * sendextent], sendcount,
- sendtype, &((char *) recvbuf)[rank * recvextent],
+ smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
+ sendcount, sendtype,
+ (char *)recvbuf + rank * recvcount * recvext,
recvcount, recvtype);
if (err == MPI_SUCCESS && size > 1) {
/* Initiate all send/recv to/from others. */
continue;
}
requests[count] =
- smpi_irecv_init(&((char *) recvbuf)[i * recvextent], recvcount,
+ smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
recvtype, i, system_tag, comm);
count++;
}
continue;
}
requests[count] =
- smpi_isend_init(&((char *) sendbuf)[i * sendextent], sendcount,
+ smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
sendtype, i, system_tag, comm);
count++;
}
{
int system_tag = 888;
int i, rank, size, err, count;
- MPI_Aint lb;
- MPI_Aint sendinc = 0;
- MPI_Aint recvinc = 0;
+ MPI_Aint lb = 0, sendext = 0, recvext = 0;
MPI_Request *requests;
/* Initialize. */
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
XBT_DEBUG("<%d> algorithm alltoall_basic_linear() called.", rank);
- err = smpi_datatype_extent(sendtype, &lb, &sendinc);
- err = smpi_datatype_extent(recvtype, &lb, &recvinc);
- sendinc *= sendcount;
- recvinc *= recvcount;
+ err = smpi_datatype_extent(sendtype, &lb, &sendext);
+ err = smpi_datatype_extent(recvtype, &lb, &recvext);
/* simple optimization */
- err =
- smpi_datatype_copy(&((char *) sendbuf)[rank * sendinc], sendcount,
- sendtype, &((char *) recvbuf)[rank * recvinc],
- recvcount, recvtype);
+ err = smpi_datatype_copy((char *)sendbuf + rank * sendcount * sendext,
+ sendcount, sendtype,
+ (char *)recvbuf + rank * recvcount * recvext,
+ recvcount, recvtype);
if (err == MPI_SUCCESS && size > 1) {
/* Initiate all send/recv to/from others. */
requests = xbt_new(MPI_Request, 2 * (size - 1));
count = 0;
for (i = (rank + 1) % size; i != rank; i = (i + 1) % size) {
requests[count] =
- smpi_irecv_init(&((char *) recvbuf)[i * recvinc], recvcount,
+ smpi_irecv_init((char *)recvbuf + i * recvcount * recvext, recvcount,
recvtype, i, system_tag, comm);
count++;
}
* when messages actually arrive in the order in which they were posted.
* TODO: check the previous assertion
*/
- for (i = (rank + size - 1) % size; i != rank;
- i = (i + size - 1) % size) {
+ for (i = (rank + size - 1) % size; i != rank; i = (i + size - 1) % size) {
requests[count] =
- smpi_isend_init(&((char *) sendbuf)[i * sendinc], sendcount,
+ smpi_isend_init((char *)sendbuf + i * sendcount * sendext, sendcount,
sendtype, i, system_tag, comm);
count++;
}
{
int system_tag = 889;
int i, rank, size, err, count;
- MPI_Aint lb;
- MPI_Aint sendextent = 0;
- MPI_Aint recvextent = 0;
+ MPI_Aint lb = 0, sendext = 0, recvext = 0;
MPI_Request *requests;
/* Initialize. */
rank = smpi_comm_rank(comm);
size = smpi_comm_size(comm);
XBT_DEBUG("<%d> algorithm basic_alltoallv() called.", rank);
- err = smpi_datatype_extent(sendtype, &lb, &sendextent);
- err = smpi_datatype_extent(recvtype, &lb, &recvextent);
+ err = smpi_datatype_extent(sendtype, &lb, &sendext);
+ err = smpi_datatype_extent(recvtype, &lb, &recvext);
/* Local copy from self */
err =
- smpi_datatype_copy(&((char *) sendbuf)[senddisps[rank] * sendextent],
+ smpi_datatype_copy((char *)sendbuf + senddisps[rank] * sendext,
sendcounts[rank], sendtype,
- &((char *) recvbuf)[recvdisps[rank] * recvextent],
+ (char *)recvbuf + recvdisps[rank] * recvext,
recvcounts[rank], recvtype);
if (err == MPI_SUCCESS && size > 1) {
/* Initiate all send/recv to/from others. */
continue;
}
requests[count] =
- smpi_irecv_init(&((char *) recvbuf)[recvdisps[i] * recvextent],
+ smpi_irecv_init((char *)recvbuf + recvdisps[i] * recvext,
recvcounts[i], recvtype, i, system_tag, comm);
count++;
}
continue;
}
requests[count] =
- smpi_isend_init(&((char *) sendbuf)[senddisps[i] * sendextent],
+ smpi_isend_init((char *)sendbuf + senddisps[i] * sendext,
sendcounts[i], sendtype, i, system_tag, comm);
count++;
}
static MPI_Comm get_comm(int comm) {
if(comm == -2) {
return MPI_COMM_SELF;
- } else if(comm >= 0) {
+ } else if(comm_lookup && comm >= 0 && comm < (int)xbt_dynar_length(comm_lookup)) {
return *(MPI_Comm*)xbt_dynar_get_ptr(comm_lookup, comm);
}
return MPI_COMM_NULL;
void mpi_finalize__(int* ierr) {
*ierr = MPI_Finalize();
xbt_dynar_free(&op_lookup);
+ op_lookup = NULL;
xbt_dynar_free(&datatype_lookup);
+ datatype_lookup = NULL;
xbt_dict_free(&request_lookup);
+ request_lookup = NULL;
xbt_dynar_free(&comm_lookup);
+ comm_lookup = NULL;
}
void mpi_abort__(int* comm, int* errorcode, int* ierr) {
* under the terms of the license (GNU LGPL) which comes with this package. */
#include <stdint.h>
+#include <stdio.h>
#include <stdlib.h>
#include "private.h"
char* value = getenv("SMPI_GLOBAL_SIZE");
if(!value) {
+ fprintf(stderr, "Please set env var SMPI_GLOBAL_SIZE to expected number of processes.\n");
abort();
}
return atoi(value);
MPI_Group group;
char name[MAILBOX_NAME_MAXLEN];
- SIMIX_comm_set_copy_data_callback
- (&SIMIX_comm_copy_buffer_callback);
+ SIMIX_comm_set_copy_data_callback(&smpi_comm_copy_data_callback);
process_count = SIMIX_process_count();
process_data = xbt_new(smpi_process_data_t, process_count);
for (i = 0; i < process_count; i++) {
if(/^} (.*?);/) {
$_ = "}* __attribute__((weak)) $1 = NULL;\n";
} elsif(/^#define\s*(\S*)\s*\(?([^.]*)(\..*?)?\)?$/) {
- $_ = "#define $1 $2\[smpi_process_index()\]";
+ $_ = "#define $1 $2\[smpi_current_rank\]";
if(defined $3) {
$_ .= $3;
}
return rate;
}
-
/**********************/
/* SMPI callbacks */
/**********************/
return 1.0056;
}
- /* 2 KiB <= size <= 32 KiB */
- if (size <= 32768.0) {
- return 1.8805;
- }
+static double smpi_bandwidth_factor(double size)
+{
- /* 64 KiB <= size <= 4 MiB */
- return 22.7111;
+ if (size >= 65472) return 0.940694;
+ if (size >= 15424) return 0.697866;
+ if (size >= 9376) return 0.58729;
+ if (size >= 5776) return 1.08739;
+ if (size >= 3484) return 0.77493;
+ if (size >= 1426) return 0.608902;
+ if (size >= 732) return 0.341987;
+ if (size >= 257) return 0.338112;
+ if (size >= 0) return 0.812084;
+ return 1.0;
}
-static double smpi_bandwidth_factor(double size)
+static double smpi_latency_factor(double size)
{
- /* 1 B <= size <= 1 KiB */
- if (size <= 1024.0) {
- return 0.2758;
- }
-
- /* 2 KiB <= size <= 32 KiB */
- if (size <= 32768.0) {
- return 0.5477;
- }
- /* 64 KiB <= size <= 4 MiB */
- return 0.9359;
+ if (size >= 65472) return 11.6436;
+ if (size >= 15424) return 3.48845;
+ if (size >= 9376) return 2.59299;
+ if (size >= 5776) return 2.18796;
+ if (size >= 3484) return 1.88101;
+ if (size >= 1426) return 1.61075;
+ if (size >= 732) return 1.9503;
+ if (size >= 257) return 1.95341;
+ if (size >= 0) return 2.01467;
+ return 1.0;
}
+/**--------- <copy/paste C code snippet in surf/network.c> -----------*/
static double smpi_bandwidth_constraint(double rate, double bound,
double size)
