Project P165
Shard planner
Order ids allocated 8 apart, placed on buckets and nodes: id % 16 uses 2 of 16 buckets, a ring moves only the keys a new node takes, and one customer's key makes one node serve more than five times the even share.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-19
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
1,024 order ids placed on buckets and on nodes: what comes out even, and what does not.
main.eml- the menu, the keys and their traffic, buckets by id % n and by a mixing hash, a 13th node, the load on each node, and a bucket count of your ownshards.eml- the ids and their request rates, a multiplicative mixing hash, a ring with 16 points a node, and finding a key's owner on it
How each part works:
- The allocator hands out ids in blocks of 8: 1000, 1008, ... 9184. Every key gets 20 requests a second except customer 5000's, which gets 9,200, 31.0% of all 29,660.
- As in the corpus case
the-hash-was-uniform-and-the-buckets-were-not, id % n reaches only n / gcd(n, 8) buckets: 2 of 16, 4 of 32, 8 of 64, and all 17 of 17. The ids are not skewed; they share a factor with a power-of-two bucket count. The top bits of a mixing hash use all 16, 32 and 64. - As in
the-hash-was-stable-and-the-ring-was-not, adding a 13th node moves 946 of the 1,024 keys when they are placed by id % nodes, and 59 on the ring, every one of them to the new node. For the 120 seconds both node lists are in use, the half of the clients still on the old one send the moved keys' 1,180 requests a second to the old owners: 70,800 requests to the wrong node, from the same stable hash. - As in
the-shard-key-was-uniform-and-the-traffic-was-not, keys per node run from 58 to 133, while the node holding customer 5000 serves 11,800 requests a second, 5.2 times the even share: no placement of keys can split one key.
What is checked: menu choices 1 to 6; a bucket count from 2 to 1024. An empty answer cancels.
Sessions: sessions/basic.in gives: - the keys, the buckets, the 13th node and the load per node; - bucket counts of 24, 128 and 17.
sessions/bad-input.in gives: - menu choices 0 and x; - bucket counts: a cancel, 1, 1025 and x; - bucket counts of 2 and 1024.
Built on the verified corpus cases the-hash-was-uniform-and-the-buckets-were-not (ids allocated 8 apart in a power-of-two table), the-hash-was-stable-and-the-ring-was-not (a node added to a consistent hashing ring while clients hold different member lists) and the-shard-key-was-uniform-and-the-traffic-was-not (keys even across 64 shards, and one key with 31 percent of the requests).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Shard planner ==
1,024 order ids placed on buckets and on nodes: what is even, and what is not.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 0
Pick a number from 1 to 6.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> x
Pick a number from 1 to 6.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)>
Cancelled.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 1
Type a whole number from 2 to 1024.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 1025
Type a whole number from 2 to 1024.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> x
Type a whole number from 2 to 1024.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 2
id % 2: 1 of 2 buckets used, the busiest with 1024 ids; gcd(2, 8) is 2, and 2 / 2 is 1.
The top bit of the mixed hash: 2 of 2 used, the busiest with 513.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 1024
id % 1024: 128 of 1024 buckets used, the busiest with 8 ids; gcd(1024, 8) is 8, and 1024 / 8 is 128.
The top 10 bits of the mixed hash: 450 of 1024 used, the busiest with 4.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 6
Bye.
What was typed (15 lines)
0
x
5
5
1
5
1025
5
x
5
2
5
1024
6
basic
interpreter: byte-equal== Shard planner ==
1,024 order ids placed on buckets and on nodes: what is even, and what is not.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 1
1,024 order ids from the allocator, which hands them out in blocks of 8: 1000, 1008, 1016, ... 9184.
Every key gets 20 requests a second, except customer 5000's, which gets 9,200: 31.0% of all 29,660.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 2
Where id % n puts the 1,024 ids, and where the top bits of a mixing hash put them:
buckets id % n: used busiest mixed: used busiest
16 2 512 16 68
17 17 61 - -
32 4 256 32 35
64 8 128 64 20
The ids are 8 apart, so id % n reaches only n / gcd(n, 8) of the buckets: a power of two shares the factor 8, and 17 shares none. The ids are not skewed; the bucket count and the allocator share a divisor.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 3
12 nodes, then a 13th:
placed by id % nodes: 946 of the 1,024 keys change node.
placed on a ring, 16 points a node: 59 keys change node, every one of them to the new node.
Clients read the node list from a registry every 60 seconds, with jitter: for 120 seconds both rings are in use, half the clients on each on average.
The 59 moved keys get 1,180 requests a second, and the half still on the old ring send theirs to the old owners: 70,800 requests to the wrong node, from the same stable hash.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 4
Keys and requests on each node of the 13-node ring:
node keys requests a second
n0 84 1,680
n1 72 1,440
n2 73 1,460
n3 88 1,760
n4 131 11,800
n5 133 2,660
n6 89 1,780
n7 60 1,200
n8 59 1,180
n9 59 1,180
n10 58 1,160
n11 59 1,180
n12 59 1,180
Keys per node: 58 to 133. Requests: n4, which holds customer 5000, serves 11,800 a second, 5.2 times the even share of 2,282.
Spreading keys does not spread requests: one key is 31.0% of the traffic, and no placement of keys can split it.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 24
id % 24: 3 of 24 buckets used, the busiest with 342 ids; gcd(24, 8) is 8, and 24 / 8 is 3.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 128
id % 128: 16 of 128 buckets used, the busiest with 64 ids; gcd(128, 8) is 8, and 128 / 8 is 16.
The top 7 bits of the mixed hash: 128 of 128 used, the busiest with 12.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 5
buckets (2 to 1024)> 17
id % 17: 17 of 17 buckets used, the busiest with 61 ids; gcd(17, 8) is 1, and 17 / 1 is 17.
1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit
choice> 6
Bye.
What was typed (11 lines)
1
2
3
4
5
24
5
128
5
17
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P165 shard planner: 1,024 order ids on buckets and nodes - the keys and
# their traffic, buckets by id % n and by a mixing hash, a 13th node added,
# the load on each node, and a bucket count of your own.
import shards
def plain(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def pad(s, n):
s => out
while len(out) < n:
out + " " => out
return out
def lpad(s, n):
s => out
while len(out) < n:
" " + out => out
return out
def digits(t):
for c in t:
if c < "0" or c > "9":
return False
return len(t) > 0
def commas(n):
str(n) => s
"" => out
0 => k
len(s) => i
while i > 0:
if k == 3:
"," + out => out
0 => k
s[i - 1] + out => out
k + 1 => k
i - 1 => i
return out
def tenths(num, den):
# num / den as a percent to one place, rounded half-up
num * 2000 + den => y
int((y - y % (2 * den)) / (2 * den)) => t
return str(int((t - t % 10) / 10)) + "." + str(t % 10) + "%"
def total_rate():
0 => t
for x in shards.ids():
t + shards.rate(x) => t
return t
def spread(counts):
# [buckets used, the busiest]
0 => used
0 => most
for c in counts:
if c > 0:
used + 1 => used
if c > most:
c => most
return [used, most]
def by_mod(n):
[0] * n => c
for x in shards.ids():
c[x % n] + 1 => c[x % n]
return spread(c)
def by_top(b, n):
[0] * n => c
for x in shards.ids():
shards.top(x, b) => k
c[k] + 1 => c[k]
return spread(c)
def log2(n):
# b with 2^b == n, or -1 if n is not a power of two
0 => b
1 => p
while p < n:
p * 2 => p
b + 1 => b
if p == n:
return b
return 0 - 1
def show_keys():
"1,024 order ids from the allocator, which hands them out in blocks of 8: 1000, 1008, 1016, ... 9184." ^0
("Every key gets 20 requests a second, except customer " + str(shards.hot_id()) + "'s, which gets " + commas(shards.rate(shards.hot_id())) + ": " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of all " + commas(total_rate()) + ".") ^0
def show_buckets():
"Where id % n puts the 1,024 ids, and where the top bits of a mixing hash put them:" ^0
(" " + pad("buckets", 9) + lpad("id % n: used", 13) + lpad("busiest", 9) + lpad("mixed: used", 14) + lpad("busiest", 9)) ^0
for n in [16, 17, 32, 64]:
by_mod(n) => a
" " + pad(str(n), 9) + lpad(str(a[0]), 13) + lpad(str(a[1]), 9) => line
if log2(n) > 0:
by_top(log2(n), n) => m
line + lpad(str(m[0]), 14) + lpad(str(m[1]), 9) => line
else:
line + lpad("-", 14) + lpad("-", 9) => line
line ^0
"The ids are 8 apart, so id % n reaches only n / gcd(n, 8) of the buckets: a power of two shares the factor 8, and 17 shares none. The ids are not skewed; the bucket count and the allocator share a divisor." ^0
def show_join():
shards.ring(12) => r12
shards.ring(13) => r13
0 => by_mod
0 => by_ring
0 => moved_rate
for x in shards.ids():
if x % 12 != x % 13:
by_mod + 1 => by_mod
if shards.owner(r12, x) != shards.owner(r13, x):
by_ring + 1 => by_ring
moved_rate + shards.rate(x) => moved_rate
"12 nodes, then a 13th:" ^0
(" placed by id % nodes: " + str(by_mod) + " of the 1,024 keys change node.") ^0
(" placed on a ring, 16 points a node: " + str(by_ring) + " keys change node, every one of them to the new node.") ^0
"Clients read the node list from a registry every 60 seconds, with jitter: for 120 seconds both rings are in use, half the clients on each on average." ^0
("The " + str(by_ring) + " moved keys get " + commas(moved_rate) + " requests a second, and the half still on the old ring send theirs to the old owners: " + commas(moved_rate * 60) + " requests to the wrong node, from the same stable hash.") ^0
def show_load():
shards.ring(13) => r
[0] * 13 => keys
[0] * 13 => reqs
for x in shards.ids():
shards.owner(r, x) => n
keys[n] + 1 => keys[n]
reqs[n] + shards.rate(x) => reqs[n]
"Keys and requests on each node of the 13-node ring:" ^0
(" " + pad("node", 6) + lpad("keys", 5) + lpad("requests a second", 19)) ^0
0 => k
while k < 13:
(" " + pad("n" + str(k), 6) + lpad(str(keys[k]), 5) + lpad(commas(reqs[k]), 19)) ^0
k + 1 => k
spread(keys) => s
1024 => least
0 => hot
0 => k
while k < 13:
if keys[k] < least:
keys[k] => least
if reqs[k] > reqs[hot]:
k => hot
k + 1 => k
total_rate() * 2 + 13 => y
int((y - y % 26) / 26) => even
reqs[hot] * 130 * 2 + total_rate() => z
int((z - z % (2 * total_rate())) / (2 * total_rate())) => times
("Keys per node: " + str(least) + " to " + str(s[1]) + ". Requests: n" + str(hot) + ", which holds customer " + str(shards.hot_id()) + ", serves " + commas(reqs[hot]) + " a second, " + str(int((times - times % 10) / 10)) + "." + str(times % 10) + " times the even share of " + commas(even) + ".") ^0
("Spreading keys does not spread requests: one key is " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of the traffic, and no placement of keys can split it.") ^0
def own():
plain(input("buckets (2 to 1024)> ")) => t
if t == "":
"Cancelled." ^0
return
if len(t) > 4 or not digits(t) or int(t) < 2 or int(t) > 1024:
"Type a whole number from 2 to 1024." ^0
return
int(t) => n
by_mod(n) => a
("id % " + str(n) + ": " + str(a[0]) + " of " + str(n) + " buckets used, the busiest with " + str(a[1]) + " ids; gcd(" + str(n) + ", 8) is " + str(shards.gcd(n, 8)) + ", and " + str(n) + " / " + str(shards.gcd(n, 8)) + " is " + str(int(n / shards.gcd(n, 8))) + ".") ^0
if log2(n) > 0:
by_top(log2(n), n) => m
"The top " + str(log2(n)) + " bits" => unit
if log2(n) == 1:
"The top bit" => unit
(unit + " of the mixed hash: " + str(m[0]) + " of " + str(n) + " used, the busiest with " + str(m[1]) + ".") ^0
"== Shard planner ==" ^0
"1,024 order ids placed on buckets and on nodes: what is even, and what is not." ^0
True => running
while running:
"" ^0
"1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show_keys()
elif choice == "2":
show_buckets()
elif choice == "3":
show_join()
elif choice == "4":
show_load()
elif choice == "5":
own()
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import shards
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def pad(s, n):
out = s
while len(out) < n:
out = out + " "
return out
def lpad(s, n):
out = s
while len(out) < n:
out = " " + out
return out
def digits(t):
for c in t:
if c < "0" or c > "9":
return False
return len(t) > 0
def commas(n):
s = str(n)
out = ""
k = 0
i = len(s)
while i > 0:
if k == 3:
out = "," + out
k = 0
out = s[i - 1] + out
k = k + 1
i = i - 1
return out
def tenths(num, den):
y = num * 2000 + den
t = int((y - y % (2 * den)) / (2 * den))
return str(int((t - t % 10) / 10)) + "." + str(t % 10) + "%"
def total_rate():
t = 0
for x in shards.ids():
t = t + shards.rate(x)
return t
def spread(counts):
used = 0
most = 0
for c in counts:
if c > 0:
used = used + 1
if c > most:
most = c
return [used, most]
def by_mod(n):
c = [0] * n
for x in shards.ids():
c[x % n] = c[x % n] + 1
return spread(c)
def by_top(b, n):
c = [0] * n
for x in shards.ids():
k = shards.top(x, b)
c[k] = c[k] + 1
return spread(c)
def log2(n):
b = 0
p = 1
while p < n:
p = p * 2
b = b + 1
if p == n:
return b
return 0 - 1
def show_keys():
print("1,024 order ids from the allocator, which hands them out in blocks of 8: 1000, 1008, 1016, ... 9184.")
print("Every key gets 20 requests a second, except customer " + str(shards.hot_id()) + "'s, which gets " + commas(shards.rate(shards.hot_id())) + ": " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of all " + commas(total_rate()) + ".")
def show_buckets():
print("Where id % n puts the 1,024 ids, and where the top bits of a mixing hash put them:")
print(" " + pad("buckets", 9) + lpad("id % n: used", 13) + lpad("busiest", 9) + lpad("mixed: used", 14) + lpad("busiest", 9))
for n in [16, 17, 32, 64]:
a = by_mod(n)
line = " " + pad(str(n), 9) + lpad(str(a[0]), 13) + lpad(str(a[1]), 9)
if log2(n) > 0:
m = by_top(log2(n), n)
line = line + lpad(str(m[0]), 14) + lpad(str(m[1]), 9)
else:
line = line + lpad("-", 14) + lpad("-", 9)
print(line)
print("The ids are 8 apart, so id % n reaches only n / gcd(n, 8) of the buckets: a power of two shares the factor 8, and 17 shares none. The ids are not skewed; the bucket count and the allocator share a divisor.")
def show_join():
r12 = shards.ring(12)
r13 = shards.ring(13)
by_mod = 0
by_ring = 0
moved_rate = 0
for x in shards.ids():
if x % 12 != x % 13:
by_mod = by_mod + 1
if shards.owner(r12, x) != shards.owner(r13, x):
by_ring = by_ring + 1
moved_rate = moved_rate + shards.rate(x)
print("12 nodes, then a 13th:")
print(" placed by id % nodes: " + str(by_mod) + " of the 1,024 keys change node.")
print(" placed on a ring, 16 points a node: " + str(by_ring) + " keys change node, every one of them to the new node.")
print("Clients read the node list from a registry every 60 seconds, with jitter: for 120 seconds both rings are in use, half the clients on each on average.")
print("The " + str(by_ring) + " moved keys get " + commas(moved_rate) + " requests a second, and the half still on the old ring send theirs to the old owners: " + commas(moved_rate * 60) + " requests to the wrong node, from the same stable hash.")
def show_load():
r = shards.ring(13)
keys = [0] * 13
reqs = [0] * 13
for x in shards.ids():
n = shards.owner(r, x)
keys[n] = keys[n] + 1
reqs[n] = reqs[n] + shards.rate(x)
print("Keys and requests on each node of the 13-node ring:")
print(" " + pad("node", 6) + lpad("keys", 5) + lpad("requests a second", 19))
k = 0
while k < 13:
print(" " + pad("n" + str(k), 6) + lpad(str(keys[k]), 5) + lpad(commas(reqs[k]), 19))
k = k + 1
s = spread(keys)
least = 1024
hot = 0
k = 0
while k < 13:
if keys[k] < least:
least = keys[k]
if reqs[k] > reqs[hot]:
hot = k
k = k + 1
y = total_rate() * 2 + 13
even = int((y - y % 26) / 26)
z = reqs[hot] * 130 * 2 + total_rate()
times = int((z - z % (2 * total_rate())) / (2 * total_rate()))
print("Keys per node: " + str(least) + " to " + str(s[1]) + ". Requests: n" + str(hot) + ", which holds customer " + str(shards.hot_id()) + ", serves " + commas(reqs[hot]) + " a second, " + str(int((times - times % 10) / 10)) + "." + str(times % 10) + " times the even share of " + commas(even) + ".")
print("Spreading keys does not spread requests: one key is " + tenths(shards.rate(shards.hot_id()), total_rate()) + " of the traffic, and no placement of keys can split it.")
def own():
t = plain(input("buckets (2 to 1024)> "))
if t == "":
print("Cancelled.")
return
if len(t) > 4 or not digits(t) or int(t) < 2 or int(t) > 1024:
print("Type a whole number from 2 to 1024.")
return
n = int(t)
a = by_mod(n)
print("id % " + str(n) + ": " + str(a[0]) + " of " + str(n) + " buckets used, the busiest with " + str(a[1]) + " ids; gcd(" + str(n) + ", 8) is " + str(shards.gcd(n, 8)) + ", and " + str(n) + " / " + str(shards.gcd(n, 8)) + " is " + str(int(n / shards.gcd(n, 8))) + ".")
if log2(n) > 0:
m = by_top(log2(n), n)
unit = "The top " + str(log2(n)) + " bits"
if log2(n) == 1:
unit = "The top bit"
print(unit + " of the mixed hash: " + str(m[0]) + " of " + str(n) + " used, the busiest with " + str(m[1]) + ".")
print("== Shard planner ==")
print("1,024 order ids placed on buckets and on nodes: what is even, and what is not.")
running = True
while running:
print("")
print("1) the keys 2) buckets 3) a 13th node 4) load per node 5) a bucket count of your own 6) quit")
choice = plain(input("choice> "))
if choice == "1":
show_keys()
elif choice == "2":
show_buckets()
elif choice == "3":
show_join()
elif choice == "4":
show_load()
elif choice == "5":
own()
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
shards.eml
eml# P165 shard planner - 1,024 order ids placed on buckets and nodes. As in
# the corpus case the-hash-was-uniform-and-the-buckets-were-not, the ids
# come from an allocator that hands them out 8 apart, and id % n reaches
# only the buckets that 8 can: a power of two shares its factor. As in
# the-hash-was-stable-and-the-ring-was-not, a ring moves only the keys the
# new node takes, and while clients hold two node lists, the same stable
# hash names two owners. And as in
# the-shard-key-was-uniform-and-the-traffic-was-not, keys spread evenly and
# requests do not.
def ids():
# 1000, 1008, 1016, ... - 1,024 of them
[0] * 1024 => out
0 => k
while k < 1024:
1000 + 8 * k => out[k]
k + 1 => k
return out
def hot_id():
return 5000
def rate(x):
# requests a second for key x
if x == hot_id():
return 9200
return 20
def mix(x):
# a multiplicative hash onto 0 .. 2^32 - 1 (x below 3,000,000)
return (x * 2654435761) % 4294967296
def top(x, b):
# bucket of x among 2^b: the top b bits of its mixed hash
1 => d
0 => k
while k < 32 - b:
d * 2 => d
k + 1 => k
mix(x) => h
return int((h - h % d) / d)
def ring(nodes):
# [position, node] for 16 points a node, sorted by position
[] => pts
0 => n
while n < nodes:
0 => v
while v < 16:
pts + [[mix(100000 + n * 100 + v), n]] => pts
v + 1 => v
n + 1 => n
1 => i
while i < len(pts):
pts[i] => p
i - 1 => j
while j >= 0 and pts[j][0] > p[0]:
pts[j] => pts[j + 1]
j - 1 => j
p => pts[j + 1]
i + 1 => i
return pts
def owner(pts, x):
# the node of the first point at or after x's position, round the ring
mix(x) => h
0 => lo
len(pts) => hi
while lo < hi:
int((lo + hi - (lo + hi) % 2) / 2) => mid
if pts[mid][0] < h:
mid + 1 => lo
else:
mid => hi
if lo == len(pts):
return pts[0][1]
return pts[lo][1]
def gcd(a, b):
while b > 0:
a % b => r
b => a
r => b
return a
Python projection (shards.py)
def ids():
out = [0] * 1024
k = 0
while k < 1024:
out[k] = 1000 + 8 * k
k = k + 1
return out
def hot_id():
return 5000
def rate(x):
if x == hot_id():
return 9200
return 20
def mix(x):
return x * 2654435761 % 4294967296
def top(x, b):
d = 1
k = 0
while k < 32 - b:
d = d * 2
k = k + 1
h = mix(x)
return int((h - h % d) / d)
def ring(nodes):
pts = []
n = 0
while n < nodes:
v = 0
while v < 16:
pts = pts + [[mix(100000 + n * 100 + v), n]]
v = v + 1
n = n + 1
i = 1
while i < len(pts):
p = pts[i]
j = i - 1
while j >= 0 and pts[j][0] > p[0]:
pts[j + 1] = pts[j]
j = j - 1
pts[j + 1] = p
i = i + 1
return pts
def owner(pts, x):
h = mix(x)
lo = 0
hi = len(pts)
while lo < hi:
mid = int((lo + hi - (lo + hi) % 2) / 2)
if pts[mid][0] < h:
lo = mid + 1
else:
hi = mid
if lo == len(pts):
return pts[0][1]
return pts[lo][1]
def gcd(a, b):
while b > 0:
r = a % b
a = b
b = r
return a