def GCD(a, b):
prevx, x = 1, 0
prevy, y = 0, 1
while b:
q = a/b
x, prevx = prevx - q*x, x
y, prevy = prevy - q*y, y
a, b = b, a%b
return a, prevx, prevy
def modinv(x, m):
(gcd, c, d)= GCD(x,m)
if c<0:
c += m
return c
q = 2**256 - 432420386565659656852420866394968145599
r = 0x6a93787fbfef76b95d2f4d7632b841459d440afaaa0873608436efcd3fbe3e54
s1 = 0xe939c2360b5dcdb64c2bc8d5ffad06a7cdfde79f29ec967a5d5d07cdec142815
s2 = 0x0df72a51154081325f81c87eb220387833aac888dcc4800b78d8423f59b1a711
m1 = 0x1a374484e71c12135cda76c1261801e9f8fc27108e3f5e439679ef13eb300eae
m2 = 0xe366e7bc7d5c12808b88e1b89c27436ac9cb3ae482dd044faeb7fab4654cbeac
print "%x" % (m1-m2) # -c92fa3379640006d2eae6af7760f4180d0cf13d3f49da60c183e0ba07a1caffe
print "%x" % (s1-s2) # db4297e4f61d4c83ecaa00574d8cce2f9a531f164d28166ee484c58e92628104
mi = modinv(s1-s2, q)
print "%x" % mi # 7369938cee97daa2c7e2b9aab4c07d7ba1189e177499caf6a2de68a71427428f
k = ((m1-m2)*mi) % q
print "k = %x" % k # 6e3469cb1dec3ce994dfc5c88bb53971fe513749727bdfa4a44a38f294008136
rinv = modinv(r, q)
xx = (s1*k-m1) % q
print "xx=%x" % xx # 8321bc4f5e0a2973e5bdc9ba8194cc62c5be375216832cb5c04c28cab035dd42
x = (xx * rinv) % q
print "x=%x" % x # 1930a0cb6fe514b9ab03c652a61ac53b2c7ee6db417543de782503e690fab966
CmRlZiBHQ0QoYSwgYik6CiAgICBwcmV2eCwgeCA9IDEsIDAKICAgIHByZXZ5LCB5ID0gMCwgMQogICAgd2hpbGUgYjoKICAgICAgICBxID0gYS9iCiAgICAgICAgeCwgcHJldnggPSBwcmV2eCAtIHEqeCwgeAogICAgICAgIHksIHByZXZ5ID0gcHJldnkgLSBxKnksIHkKICAgICAgICBhLCBiID0gYiwgYSViCiAgICByZXR1cm4gYSwgcHJldngsIHByZXZ5CgoKZGVmIG1vZGludih4LCBtKToKICAgIChnY2QsIGMsIGQpPSBHQ0QoeCxtKQogICAgaWYgYzwwOgogICAgICAgIGMgKz0gbQogICAgcmV0dXJuIGMKCnEgPSAyKioyNTYgLSA0MzI0MjAzODY1NjU2NTk2NTY4NTI0MjA4NjYzOTQ5NjgxNDU1OTkKCnIgPSAweDZhOTM3ODdmYmZlZjc2Yjk1ZDJmNGQ3NjMyYjg0MTQ1OWQ0NDBhZmFhYTA4NzM2MDg0MzZlZmNkM2ZiZTNlNTQKczEgPSAweGU5MzljMjM2MGI1ZGNkYjY0YzJiYzhkNWZmYWQwNmE3Y2RmZGU3OWYyOWVjOTY3YTVkNWQwN2NkZWMxNDI4MTUKczIgPSAweDBkZjcyYTUxMTU0MDgxMzI1ZjgxYzg3ZWIyMjAzODc4MzNhYWM4ODhkY2M0ODAwYjc4ZDg0MjNmNTliMWE3MTEKbTEgPSAweDFhMzc0NDg0ZTcxYzEyMTM1Y2RhNzZjMTI2MTgwMWU5ZjhmYzI3MTA4ZTNmNWU0Mzk2NzllZjEzZWIzMDBlYWUKbTIgPSAweGUzNjZlN2JjN2Q1YzEyODA4Yjg4ZTFiODljMjc0MzZhYzljYjNhZTQ4MmRkMDQ0ZmFlYjdmYWI0NjU0Y2JlYWMKCnByaW50ICIleCIgJSAobTEtbTIpICMgLWM5MmZhMzM3OTY0MDAwNmQyZWFlNmFmNzc2MGY0MTgwZDBjZjEzZDNmNDlkYTYwYzE4M2UwYmEwN2ExY2FmZmUKcHJpbnQgIiV4IiAlIChzMS1zMikgIyBkYjQyOTdlNGY2MWQ0YzgzZWNhYTAwNTc0ZDhjY2UyZjlhNTMxZjE2NGQyODE2NmVlNDg0YzU4ZTkyNjI4MTA0CgptaSA9IG1vZGludihzMS1zMiwgcSkKcHJpbnQgIiV4IiAlIG1pICAjIDczNjk5MzhjZWU5N2RhYTJjN2UyYjlhYWI0YzA3ZDdiYTExODllMTc3NDk5Y2FmNmEyZGU2OGE3MTQyNzQyOGYKCmsgPSAoKG0xLW0yKSptaSkgJSBxIApwcmludCAiayA9ICV4IiAlIGsgIyA2ZTM0NjljYjFkZWMzY2U5OTRkZmM1Yzg4YmI1Mzk3MWZlNTEzNzQ5NzI3YmRmYTRhNDRhMzhmMjk0MDA4MTM2CgpyaW52ID0gbW9kaW52KHIsIHEpCnh4ID0gKHMxKmstbTEpICUgcQpwcmludCAieHg9JXgiICUgeHggIyA4MzIxYmM0ZjVlMGEyOTczZTViZGM5YmE4MTk0Y2M2MmM1YmUzNzUyMTY4MzJjYjVjMDRjMjhjYWIwMzVkZDQyCnggPSAoeHggKiByaW52KSAlIHEKcHJpbnQgIng9JXgiICUgeCAjIDE5MzBhMGNiNmZlNTE0YjlhYjAzYzY1MmE2MWFjNTNiMmM3ZWU2ZGI0MTc1NDNkZTc4MjUwM2U2OTBmYWI5NjYK