Schnorr4.sage.py

# This file was *autogenerated* from the file Schnorr4.sage
from sage.all_cmdline import *   # import sage library

_sage_const_16 = Integer(16)
_sage_const_2 = Integer(2)
_sage_const_0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F = Integer(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
_sage_const_0 = Integer(0)
_sage_const_7 = Integer(7)
_sage_const_0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 = Integer(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
_sage_const_3943403887 = Integer(3943403887)
_sage_const_3 = Integer(3)
_sage_const_5 = Integer(5)
_sage_const_1 = Integer(1)
_sage_const_1024 = Integer(1024)
_sage_const_3952459683 = Integer(3952459683)
_sage_const_140620442 = Integer(140620442)
_sage_const_2017216018 = Integer(2017216018)
_sage_const_2009046716 = Integer(2009046716)
_sage_const_1509335457 = Integer(1509335457)
_sage_const_4077915080 = Integer(4077915080)
_sage_const_1932088938 = Integer(1932088938)
_sage_const_2486682281 = Integer(2486682281)
_sage_const_3314941358 = Integer(3314941358)
_sage_const_499585529 = Integer(499585529)
_sage_const_3362337200 = Integer(3362337200)
_sage_const_2211775199 = Integer(2211775199)
_sage_const_2330471963 = Integer(2330471963)
_sage_const_3606788670 = Integer(3606788670)
_sage_const_4134288763 = Integer(4134288763)
_sage_const_3260445262 = Integer(3260445262)
_sage_const_2586822768 = Integer(2586822768)
_sage_const_1128746907 = Integer(1128746907)
_sage_const_3723722377 = Integer(3723722377)
_sage_const_1544039621 = Integer(1544039621)
_sage_const_1516844343 = Integer(1516844343)
_sage_const_3838049092 = Integer(3838049092)
_sage_const_3234026267 = Integer(3234026267)
_sage_const_1742413807 = Integer(1742413807)
_sage_const_3209196705 = Integer(3209196705)
_sage_const_4042251632 = Integer(4042251632)
_sage_const_3975864098 = Integer(3975864098)
_sage_const_1096753163 = Integer(1096753163)
_sage_const_3633611705 = Integer(3633611705)
_sage_const_767066282 = Integer(767066282)
_sage_const_3768454157 = Integer(3768454157)
_sage_const_539424771 = Integer(539424771)
_sage_const_3606753106 = Integer(3606753106)
_sage_const_18313224 = Integer(18313224)
_sage_const_1075685129 = Integer(1075685129)
_sage_const_737257314 = Integer(737257314)
_sage_const_1301487686 = Integer(1301487686)
_sage_const_364160362 = Integer(364160362)
_sage_const_4217215080 = Integer(4217215080)
_sage_const_1352247727 = Integer(1352247727)
_sage_const_1914230622 = Integer(1914230622)
_sage_const_142035844 = Integer(142035844)
_sage_const_3445740864 = Integer(3445740864)
_sage_const_2469049293 = Integer(2469049293)
_sage_const_1797902554 = Integer(1797902554)
_sage_const_3319456240 = Integer(3319456240)
_sage_const_2229753882 = Integer(2229753882)
_sage_const_2191947181 = Integer(2191947181)
_sage_const_3976251297 = Integer(3976251297)
_sage_const_1619755698 = Integer(1619755698)
_sage_const_2552941005 = Integer(2552941005)
_sage_const_2301914585 = Integer(2301914585)
_sage_const_2503888055 = Integer(2503888055)
_sage_const_1844588746 = Integer(1844588746)
_sage_const_3047825066 = Integer(3047825066)
_sage_const_1928880188 = Integer(1928880188)
_sage_const_4155801463 = Integer(4155801463)
_sage_const_2583818105 = Integer(2583818105)
_sage_const_3106220087 = Integer(3106220087)
_sage_const_3279762563 = Integer(3279762563)
_sage_const_3212767151 = Integer(3212767151)
_sage_const_3807893560 = Integer(3807893560)
_sage_const_2229425900 = Integer(2229425900)
_sage_const_2739136220 = Integer(2739136220)
_sage_const_1632389433 = Integer(1632389433)
_sage_const_2902152512 = Integer(2902152512)
_sage_const_83693948 = Integer(83693948)
_sage_const_2093956158 = Integer(2093956158)
_sage_const_1095902075 = Integer(1095902075)
_sage_const_2868146148 = Integer(2868146148)
_sage_const_766459304 = Integer(766459304)
_sage_const_1914935438 = Integer(1914935438)
_sage_const_3406978115 = Integer(3406978115)
_sage_const_1395422425 = Integer(1395422425)
_sage_const_2520335904 = Integer(2520335904)
_sage_const_1504028136 = Integer(1504028136)
_sage_const_4023735222 = Integer(4023735222)
_sage_const_3046846676 = Integer(3046846676)
_sage_const_1201078568 = Integer(1201078568)
_sage_const_375908758 = Integer(375908758)
_sage_const_119286203 = Integer(119286203)
_sage_const_1853781173 = Integer(1853781173)
_sage_const_2369168331 = Integer(2369168331)
_sage_const_1804912580 = Integer(1804912580)
_sage_const_733969225 = Integer(733969225)
_sage_const_3163390675 = Integer(3163390675)
_sage_const_328558366 = Integer(328558366)
_sage_const_4154804709 = Integer(4154804709)
_sage_const_2922558557 = Integer(2922558557)
_sage_const_1022427754 = Integer(1022427754)
_sage_const_2077866832 = Integer(2077866832)
_sage_const_2841336229 = Integer(2841336229)
_sage_const_4112332032 = Integer(4112332032)
_sage_const_3683257847 = Integer(3683257847)
_sage_const_3115064832 = Integer(3115064832)
_sage_const_1424320860 = Integer(1424320860)
_sage_const_709678450 = Integer(709678450)
_sage_const_1251382373 = Integer(1251382373)
_sage_const_3834362799 = Integer(3834362799)
_sage_const_3311489886 = Integer(3311489886)
_sage_const_1059044347 = Integer(1059044347)
_sage_const_1840764376 = Integer(1840764376)
_sage_const_2720090515 = Integer(2720090515)
_sage_const_3505032467 = Integer(3505032467)
_sage_const_593507574 = Integer(593507574)
_sage_const_661286706 = Integer(661286706)
_sage_const_1143943486 = Integer(1143943486)
_sage_const_496329025 = Integer(496329025)
_sage_const_472939875 = Integer(472939875)
_sage_const_2414880472 = Integer(2414880472)
_sage_const_2030246970 = Integer(2030246970)
_sage_const_324673756 = Integer(324673756)
_sage_const_3697634721 = Integer(3697634721)
_sage_const_449647308 = Integer(449647308)
_sage_const_2787228712 = Integer(2787228712)
_sage_const_4205775805 = Integer(4205775805)
_sage_const_2018848604 = Integer(2018848604)
_sage_const_3934436566 = Integer(3934436566)
_sage_const_3711878379 = Integer(3711878379)
_sage_const_586563327 = Integer(586563327)
_sage_const_1900151571 = Integer(1900151571)
_sage_const_1782602950 = Integer(1782602950)
_sage_const_204982352 = Integer(204982352)
_sage_const_1168800016 = Integer(1168800016)
_sage_const_1760581905 = Integer(1760581905)
_sage_const_3312121479 = Integer(3312121479)
_sage_const_389216358 = Integer(389216358)
_sage_const_2538577611 = Integer(2538577611)
_sage_const_1600728930 = Integer(1600728930)
_sage_const_42948890 = Integer(42948890)
_sage_const_2790096070 = Integer(2790096070)
_sage_const_2592628431 = Integer(2592628431)
_sage_const_603771702 = Integer(603771702)
_sage_const_364764022 = Integer(364764022)
_sage_const_3657953974 = Integer(3657953974)
_sage_const_345932725 = Integer(345932725)
_sage_const_2389681322 = Integer(2389681322)
_sage_const_2511987192 = Integer(2511987192)
_sage_const_2554772220 = Integer(2554772220)
_sage_const_4000714081 = Integer(4000714081)
_sage_const_2512894656 = Integer(2512894656)
_sage_const_1282546849 = Integer(1282546849)
_sage_const_607700325 = Integer(607700325)
_sage_const_3520902869 = Integer(3520902869)
_sage_const_3760734200 = Integer(3760734200)
_sage_const_1167290368 = Integer(1167290368)
_sage_const_366505776 = Integer(366505776)
_sage_const_809138353 = Integer(809138353)
_sage_const_1838612482 = Integer(1838612482)
_sage_const_3525364779 = Integer(3525364779)
_sage_const_1952591117 = Integer(1952591117)
_sage_const_3667128651 = Integer(3667128651)
_sage_const_577679124 = Integer(577679124)
_sage_const_209929118 = Integer(209929118)
_sage_const_952525595 = Integer(952525595)
_sage_const_2805017976 = Integer(2805017976)
_sage_const_1908102323 = Integer(1908102323)
_sage_const_3107524892 = Integer(3107524892)
_sage_const_3998515704 = Integer(3998515704)
_sage_const_2818601629 = Integer(2818601629)
_sage_const_1632644731 = Integer(1632644731)
_sage_const_1673264357 = Integer(1673264357)
_sage_const_2478623148 = Integer(2478623148)
_sage_const_2387096063 = Integer(2387096063)
_sage_const_1271224779 = Integer(1271224779)
_sage_const_3545655642 = Integer(3545655642)
_sage_const_1338634086 = Integer(1338634086)
_sage_const_208565460 = Integer(208565460)
_sage_const_1144254551 = Integer(1144254551)
_sage_const_566749384 = Integer(566749384)
_sage_const_1213444573 = Integer(1213444573)
_sage_const_2270680829 = Integer(2270680829)
_sage_const_2667338802 = Integer(2667338802)
_sage_const_447393599 = Integer(447393599)
_sage_const_2745909947 = Integer(2745909947)
_sage_const_1413657208 = Integer(1413657208)
_sage_const_2818038301 = Integer(2818038301)
_sage_const_2611315625 = Integer(2611315625)
_sage_const_558788 = Integer(558788)
_sage_const_2001781779 = Integer(2001781779)
_sage_const_1145522126 = Integer(1145522126)
_sage_const_3864133576 = Integer(3864133576)
_sage_const_2855615464 = Integer(2855615464)
_sage_const_1175579813 = Integer(1175579813)
_sage_const_445158637 = Integer(445158637)
_sage_const_817566918 = Integer(817566918)
_sage_const_1344934809 = Integer(1344934809)
_sage_const_1890208939 = Integer(1890208939)
_sage_const_595665807 = Integer(595665807)
_sage_const_2083040701 = Integer(2083040701)
_sage_const_2546103415 = Integer(2546103415)
_sage_const_3799539368 = Integer(3799539368)
_sage_const_1653802914 = Integer(1653802914)
_sage_const_3120286505 = Integer(3120286505)
_sage_const_4017684220 = Integer(4017684220)
_sage_const_4108938953 = Integer(4108938953)
_sage_const_385794252 = Integer(385794252)
_sage_const_3054087990 = Integer(3054087990)
_sage_const_2519574417 = Integer(2519574417)
_sage_const_2903452730 = Integer(2903452730)
_sage_const_1291639897 = Integer(1291639897)
_sage_const_826798828 = Integer(826798828)
_sage_const_586206110 = Integer(586206110)
_sage_const_3285585972 = Integer(3285585972)
_sage_const_2920486174 = Integer(2920486174)
_sage_const_3175925084 = Integer(3175925084)
_sage_const_459481797 = Integer(459481797)
_sage_const_466529033 = Integer(466529033)
_sage_const_848706037 = Integer(848706037)
_sage_const_2934537306 = Integer(2934537306)
_sage_const_4289714493 = Integer(4289714493)
_sage_const_1245082734 = Integer(1245082734)
_sage_const_2589996752 = Integer(2589996752)
_sage_const_2389930559 = Integer(2389930559)
_sage_const_4163622221 = Integer(4163622221)
_sage_const_1032226453 = Integer(1032226453)
_sage_const_4047370927 = Integer(4047370927)
_sage_const_3998477336 = Integer(3998477336)
_sage_const_4203406315 = Integer(4203406315)
_sage_const_2577438133 = Integer(2577438133)
_sage_const_4190796340 = Integer(4190796340)
_sage_const_1445431932 = Integer(1445431932)
_sage_const_542197919 = Integer(542197919)
_sage_const_1523076747 = Integer(1523076747)
_sage_const_3156657627 = Integer(3156657627)
_sage_const_1151167272 = Integer(1151167272)
_sage_const_899779775 = Integer(899779775)
_sage_const_3888750110 = Integer(3888750110)
_sage_const_4178055519 = Integer(4178055519)
_sage_const_1059680825 = Integer(1059680825)
_sage_const_134098916 = Integer(134098916)
_sage_const_3241953930 = Integer(3241953930)
_sage_const_1403191210 = Integer(1403191210)
_sage_const_2782617305 = Integer(2782617305)
_sage_const_1596932414 = Integer(1596932414)
_sage_const_3824062207 = Integer(3824062207)
_sage_const_1446860573 = Integer(1446860573)
_sage_const_2646807260 = Integer(2646807260)
_sage_const_3227579532 = Integer(3227579532)
_sage_const_3132938294 = Integer(3132938294)
_sage_const_2768482560 = Integer(2768482560)
_sage_const_461251643 = Integer(461251643)
_sage_const_661133937 = Integer(661133937)
_sage_const_3012269095 = Integer(3012269095)
_sage_const_2269874965 = Integer(2269874965)
_sage_const_3805639755 = Integer(3805639755)
_sage_const_2364681041 = Integer(2364681041)
_sage_const_226700072 = Integer(226700072)
_sage_const_3071628030 = Integer(3071628030)
_sage_const_740031554 = Integer(740031554)
_sage_const_1029331527 = Integer(1029331527)
_sage_const_4133052612 = Integer(4133052612)
_sage_const_206116831 = Integer(206116831)
_sage_const_3546889884 = Integer(3546889884)
_sage_const_4110204268 = Integer(4110204268)
_sage_const_748254024 = Integer(748254024)
_sage_const_2441189548 = Integer(2441189548)
_sage_const_4054227839 = Integer(4054227839)
_sage_const_1907595159 = Integer(1907595159)
_sage_const_4000683750 = Integer(4000683750)
_sage_const_3249068243 = Integer(3249068243)
_sage_const_1504667377 = Integer(1504667377)
_sage_const_3054475378 = Integer(3054475378)
_sage_const_3276497813 = Integer(3276497813)
_sage_const_1509430713 = Integer(1509430713)
_sage_const_2677043124 = Integer(2677043124)
_sage_const_3244208999 = Integer(3244208999)
_sage_const_446714967 = Integer(446714967)
_sage_const_1180268955 = Integer(1180268955)
_sage_const_1106168058 = Integer(1106168058)
_sage_const_1413675763 = Integer(1413675763)
_sage_const_711113383 = Integer(711113383)
_sage_const_377958134 = Integer(377958134)
_sage_const_1247237878 = Integer(1247237878)
_sage_const_1756911021 = Integer(1756911021)
_sage_const_201052169 = Integer(201052169)
_sage_const_1959269810 = Integer(1959269810)
_sage_const_3190208469 = Integer(3190208469)
_sage_const_3099357099 = Integer(3099357099)
_sage_const_3092865037 = Integer(3092865037)
_sage_const_195020592 = Integer(195020592)
_sage_const_3379419715 = Integer(3379419715)
_sage_const_1392797718 = Integer(1392797718)
_sage_const_3609500251 = Integer(3609500251)
_sage_const_3967480620 = Integer(3967480620)
_sage_const_1470003086 = Integer(1470003086)
_sage_const_1611273651 = Integer(1611273651)
_sage_const_2678649306 = Integer(2678649306)
_sage_const_3793943163 = Integer(3793943163)
_sage_const_4263260479 = Integer(4263260479)
_sage_const_2272670323 = Integer(2272670323)
_sage_const_3552013912 = Integer(3552013912)
_sage_const_2327802720 = Integer(2327802720)
_sage_const_964409761 = Integer(964409761)
_sage_const_2589215214 = Integer(2589215214)
_sage_const_2428882680 = Integer(2428882680)
_sage_const_648055316 = Integer(648055316)
_sage_const_4123710212 = Integer(4123710212)
_sage_const_1673774034 = Integer(1673774034)
_sage_const_3887832523 = Integer(3887832523)
_sage_const_1441529431 = Integer(1441529431)
_sage_const_4290921581 = Integer(4290921581)
_sage_const_807526737 = Integer(807526737)
_sage_const_1496000033 = Integer(1496000033)
_sage_const_3361527512 = Integer(3361527512)
_sage_const_2194767334 = Integer(2194767334)
_sage_const_1819445301 = Integer(1819445301)
_sage_const_2517018921 = Integer(2517018921)
_sage_const_3594711790 = Integer(3594711790)
_sage_const_2796122842 = Integer(2796122842)
_sage_const_872001322 = Integer(872001322)
_sage_const_3229855629 = Integer(3229855629)
_sage_const_3114124587 = Integer(3114124587)
_sage_const_4169245642 = Integer(4169245642)
_sage_const_2616053411 = Integer(2616053411)
_sage_const_3909511573 = Integer(3909511573)
_sage_const_994489645 = Integer(994489645)
_sage_const_3587611841 = Integer(3587611841)
_sage_const_2210050416 = Integer(2210050416)
_sage_const_437035565 = Integer(437035565)
_sage_const_554583559 = Integer(554583559)
_sage_const_1559347049 = Integer(1559347049)
_sage_const_1112273838 = Integer(1112273838)
_sage_const_4121356635 = Integer(4121356635)
_sage_const_3785139433 = Integer(3785139433)
_sage_const_4090626494 = Integer(4090626494)
_sage_const_1931371692 = Integer(1931371692)
_sage_const_3548553825 = Integer(3548553825)
_sage_const_4181304425 = Integer(4181304425)
_sage_const_1469510419 = Integer(1469510419)
_sage_const_2206424494 = Integer(2206424494)
_sage_const_3477963051 = Integer(3477963051)
_sage_const_3849342270 = Integer(3849342270)
_sage_const_3703460250 = Integer(3703460250)
_sage_const_1334252130 = Integer(1334252130)
_sage_const_288572380 = Integer(288572380)
_sage_const_971216662 = Integer(971216662)
_sage_const_1815390916 = Integer(1815390916)
_sage_const_3493969241 = Integer(3493969241)
_sage_const_2608286018 = Integer(2608286018)
_sage_const_651275292 = Integer(651275292)
_sage_const_1215400968 = Integer(1215400968)
_sage_const_1898101947 = Integer(1898101947)
_sage_const_3439487858 = Integer(3439487858)
_sage_const_2006176490 = Integer(2006176490)
_sage_const_500620238 = Integer(500620238)
_sage_const_730932289 = Integer(730932289)
_sage_const_2279956838 = Integer(2279956838)
_sage_const_101866724 = Integer(101866724)
_sage_const_3243125721 = Integer(3243125721)
_sage_const_4093792017 = Integer(4093792017)
_sage_const_2824718385 = Integer(2824718385)
_sage_const_296941721 = Integer(296941721)
_sage_const_2486937000 = Integer(2486937000)
_sage_const_3435465698 = Integer(3435465698)
_sage_const_3023964098 = Integer(3023964098)
_sage_const_1248385944 = Integer(1248385944)
_sage_const_3209359661 = Integer(3209359661)
_sage_const_433832325 = Integer(433832325)
_sage_const_2414181781 = Integer(2414181781)
_sage_const_1035892004 = Integer(1035892004)
_sage_const_1267320598 = Integer(1267320598)
_sage_const_781849687 = Integer(781849687)
_sage_const_4175962999 = Integer(4175962999)
_sage_const_3250906632 = Integer(3250906632)
_sage_const_3334829192 = Integer(3334829192)
_sage_const_2799399854 = Integer(2799399854)
_sage_const_1317434321 = Integer(1317434321)
_sage_const_1417465101 = Integer(1417465101)
_sage_const_4117758796 = Integer(4117758796)
_sage_const_4092211979 = Integer(4092211979)
_sage_const_2879341984 = Integer(2879341984)
_sage_const_2160184051 = Integer(2160184051)
_sage_const_412025946 = Integer(412025946)
_sage_const_3913954063 = Integer(3913954063)
_sage_const_2290482390 = Integer(2290482390)
_sage_const_2858885770 = Integer(2858885770)
_sage_const_1497709652 = Integer(1497709652)
_sage_const_2808944091 = Integer(2808944091)
_sage_const_1308877778 = Integer(1308877778)
_sage_const_3190731050 = Integer(3190731050)
_sage_const_1832988858 = Integer(1832988858)
_sage_const_978508767 = Integer(978508767)
_sage_const_1900348650 = Integer(1900348650)
_sage_const_3251776573 = Integer(3251776573)
_sage_const_3896457431 = Integer(3896457431)
_sage_const_4094300135 = Integer(4094300135)
_sage_const_2656886649 = Integer(2656886649)
_sage_const_1616027087 = Integer(1616027087)
_sage_const_1809944247 = Integer(1809944247)
_sage_const_3790895900 = Integer(3790895900)
_sage_const_1974078952 = Integer(1974078952)
_sage_const_2826935185 = Integer(2826935185)
_sage_const_3261996568 = Integer(3261996568)
_sage_const_239419057 = Integer(239419057)
_sage_const_2645414694 = Integer(2645414694)
_sage_const_1914423974 = Integer(1914423974)
_sage_const_4066359836 = Integer(4066359836)
_sage_const_2957408273 = Integer(2957408273)
_sage_const_1580192614 = Integer(1580192614)
_sage_const_3529152483 = Integer(3529152483)
_sage_const_498440598 = Integer(498440598)
_sage_const_2074047399 = Integer(2074047399)
_sage_const_3878220458 = Integer(3878220458)
_sage_const_28566736 = Integer(28566736)
_sage_const_3717809264 = Integer(3717809264)
_sage_const_3717577698 = Integer(3717577698)
_sage_const_2786808071 = Integer(2786808071)
_sage_const_2634436011 = Integer(2634436011)
_sage_const_3528688245 = Integer(3528688245)
_sage_const_57331723 = Integer(57331723)
_sage_const_3941478473 = Integer(3941478473)
_sage_const_532788744 = Integer(532788744)
_sage_const_3085440955 = Integer(3085440955)
_sage_const_631024091 = Integer(631024091)
_sage_const_2092762845 = Integer(2092762845)
_sage_const_2900199454 = Integer(2900199454)
_sage_const_1681880163 = Integer(1681880163)
_sage_const_65030485 = Integer(65030485)
_sage_const_1923886359 = Integer(1923886359)
_sage_const_3186692127 = Integer(3186692127)
_sage_const_2373847057 = Integer(2373847057)
_sage_const_2970320823 = Integer(2970320823)
_sage_const_2179393866 = Integer(2179393866)
_sage_const_4232235063 = Integer(4232235063)
_sage_const_2724142643 = Integer(2724142643)
_sage_const_434961598 = Integer(434961598)
_sage_const_2212549068 = Integer(2212549068)
_sage_const_1852891838 = Integer(1852891838)
_sage_const_2174479740 = Integer(2174479740)
_sage_const_205195157 = Integer(205195157)
_sage_const_137033942 = Integer(137033942)
_sage_const_1131010727 = Integer(1131010727)
_sage_const_907169493 = Integer(907169493)
_sage_const_594560834 = Integer(594560834)
_sage_const_3286951263 = Integer(3286951263)
_sage_const_2279593073 = Integer(2279593073)
_sage_const_2628790437 = Integer(2628790437)
_sage_const_222639794 = Integer(222639794)
_sage_const_1974918295 = Integer(1974918295)
_sage_const_3285634123 = Integer(3285634123)
_sage_const_2045561189 = Integer(2045561189)
_sage_const_1882398249 = Integer(1882398249)
_sage_const_283934601 = Integer(283934601)
_sage_const_1265040621 = Integer(1265040621)
_sage_const_3601155789 = Integer(3601155789)
_sage_const_3231133674 = Integer(3231133674)
_sage_const_1070736492 = Integer(1070736492)
_sage_const_2604041139 = Integer(2604041139)
_sage_const_1286644694 = Integer(1286644694)
_sage_const_3471881410 = Integer(3471881410)
_sage_const_3998008737 = Integer(3998008737)
_sage_const_4166692921 = Integer(4166692921)
_sage_const_1984749305 = Integer(1984749305)
_sage_const_3717312094 = Integer(3717312094)
_sage_const_170493346 = Integer(170493346)
_sage_const_4151638014 = Integer(4151638014)
_sage_const_3100096563 = Integer(3100096563)
_sage_const_1781970618 = Integer(1781970618)
_sage_const_1469465656 = Integer(1469465656)
_sage_const_1129563677 = Integer(1129563677)
_sage_const_3126950261 = Integer(3126950261)
_sage_const_2598959897 = Integer(2598959897)
_sage_const_3930980098 = Integer(3930980098)
_sage_const_3145416236 = Integer(3145416236)
_sage_const_2065799006 = Integer(2065799006)
_sage_const_503245321 = Integer(503245321)
_sage_const_2349936549 = Integer(2349936549)
_sage_const_34718926 = Integer(34718926)
_sage_const_466644579 = Integer(466644579)
_sage_const_4081985580 = Integer(4081985580)
_sage_const_3273641486 = Integer(3273641486)
_sage_const_1620257026 = Integer(1620257026)
_sage_const_2982646358 = Integer(2982646358)
_sage_const_199380680 = Integer(199380680)
_sage_const_87748991 = Integer(87748991)
_sage_const_1537697907 = Integer(1537697907)
_sage_const_1353507210 = Integer(1353507210)
_sage_const_649640394 = Integer(649640394)
_sage_const_923002607 = Integer(923002607)
_sage_const_3954168617 = Integer(3954168617)
_sage_const_3588753946 = Integer(3588753946)
_sage_const_2395140467 = Integer(2395140467)
_sage_const_3528208126 = Integer(3528208126)
_sage_const_942612979 = Integer(942612979)
_sage_const_535721316 = Integer(535721316)
_sage_const_277984505 = Integer(277984505)
_sage_const_2398191553 = Integer(2398191553)
_sage_const_3198280166 = Integer(3198280166)
_sage_const_3103354176 = Integer(3103354176)
_sage_const_1906004320 = Integer(1906004320)
_sage_const_703614489 = Integer(703614489)
_sage_const_2733831898 = Integer(2733831898)
_sage_const_167894300 = Integer(167894300)
_sage_const_3927722210 = Integer(3927722210)
_sage_const_462166401 = Integer(462166401)
_sage_const_1949372081 = Integer(1949372081)
_sage_const_394481983 = Integer(394481983)
_sage_const_142259367 = Integer(142259367)
_sage_const_2142924833 = Integer(2142924833)
_sage_const_3723138218 = Integer(3723138218)
_sage_const_1513897917 = Integer(1513897917)
_sage_const_2229626255 = Integer(2229626255)
_sage_const_2108490120 = Integer(2108490120)
_sage_const_1230492766 = Integer(1230492766)
_sage_const_3008774167 = Integer(3008774167)
_sage_const_3812375492 = Integer(3812375492)
_sage_const_3074455388 = Integer(3074455388)
_sage_const_1848665308 = Integer(1848665308)
_sage_const_3120260622 = Integer(3120260622)
_sage_const_4141159246 = Integer(4141159246)
_sage_const_621593509 = Integer(621593509)
_sage_const_1520284440 = Integer(1520284440)
_sage_const_419672987 = Integer(419672987)
_sage_const_3952319235 = Integer(3952319235)
_sage_const_1972040021 = Integer(1972040021)
_sage_const_2682795333 = Integer(2682795333)
_sage_const_4248958407 = Integer(4248958407)
_sage_const_2430489776 = Integer(2430489776)
_sage_const_1998982847 = Integer(1998982847)
_sage_const_2447726525 = Integer(2447726525)
_sage_const_4186472610 = Integer(4186472610)
_sage_const_4072971075 = Integer(4072971075)
_sage_const_193515222 = Integer(193515222)
_sage_const_1070797965 = Integer(1070797965)
_sage_const_836171487 = Integer(836171487)
_sage_const_1787824246 = Integer(1787824246)
_sage_const_664674363 = Integer(664674363)
_sage_const_734630056 = Integer(734630056)
_sage_const_4028847063 = Integer(4028847063)
_sage_const_1371828711 = Integer(1371828711)
_sage_const_4246510952 = Integer(4246510952)
_sage_const_3343965217 = Integer(3343965217)
_sage_const_2643351565 = Integer(2643351565)
_sage_const_1217664939 = Integer(1217664939)
_sage_const_2940984862 = Integer(2940984862)
_sage_const_3942219648 = Integer(3942219648)
_sage_const_505760561 = Integer(505760561)
_sage_const_540562365 = Integer(540562365)
_sage_const_3221206580 = Integer(3221206580)
_sage_const_3713131495 = Integer(3713131495)
_sage_const_3367407149 = Integer(3367407149)
_sage_const_1345854475 = Integer(1345854475)
_sage_const_2500012197 = Integer(2500012197)
_sage_const_877056782 = Integer(877056782)
_sage_const_2010460269 = Integer(2010460269)
_sage_const_1125841596 = Integer(1125841596)
_sage_const_393541314 = Integer(393541314)
_sage_const_1093377296 = Integer(1093377296)
_sage_const_2207060009 = Integer(2207060009)
_sage_const_2193458018 = Integer(2193458018)
_sage_const_3185777727 = Integer(3185777727)
_sage_const_1734059597 = Integer(1734059597)
_sage_const_2835440292 = Integer(2835440292)
_sage_const_3795486676 = Integer(3795486676)
_sage_const_236382810 = Integer(236382810)
_sage_const_196722783 = Integer(196722783)
_sage_const_273542651 = Integer(273542651)
_sage_const_1939662971 = Integer(1939662971)
_sage_const_3839481177 = Integer(3839481177)
_sage_const_3809197040 = Integer(3809197040)
_sage_const_4127081423 = Integer(4127081423)
_sage_const_2254237506 = Integer(2254237506)
_sage_const_3859992183 = Integer(3859992183)
_sage_const_2935782939 = Integer(2935782939)
_sage_const_1709109184 = Integer(1709109184)
_sage_const_1631021458 = Integer(1631021458)
_sage_const_166788004 = Integer(166788004)
_sage_const_1243239501 = Integer(1243239501)
_sage_const_3911919396 = Integer(3911919396)
_sage_const_127742131 = Integer(127742131)
_sage_const_2799649543 = Integer(2799649543)
_sage_const_2699707072 = Integer(2699707072)
_sage_const_894878619 = Integer(894878619)
_sage_const_2134355819 = Integer(2134355819)
_sage_const_874662292 = Integer(874662292)
_sage_const_4243725233 = Integer(4243725233)
_sage_const_2965176282 = Integer(2965176282)
_sage_const_3631572266 = Integer(3631572266)
_sage_const_246165295 = Integer(246165295)
_sage_const_1326531614 = Integer(1326531614)
_sage_const_434637048 = Integer(434637048)
_sage_const_4093779404 = Integer(4093779404)
_sage_const_4275927089 = Integer(4275927089)
_sage_const_330883731 = Integer(330883731)
_sage_const_2573083971 = Integer(2573083971)
_sage_const_4041603319 = Integer(4041603319)
_sage_const_1078826072 = Integer(1078826072)
_sage_const_1205178391 = Integer(1205178391)
_sage_const_2804818001 = Integer(2804818001)
_sage_const_3648185928 = Integer(3648185928)
_sage_const_2062983627 = Integer(2062983627)
_sage_const_3964754414 = Integer(3964754414)
_sage_const_3825757328 = Integer(3825757328)
_sage_const_2268216703 = Integer(2268216703)
_sage_const_3710959221 = Integer(3710959221)
_sage_const_1198002389 = Integer(1198002389)
_sage_const_4036779168 = Integer(4036779168)
_sage_const_2492232218 = Integer(2492232218)
_sage_const_1928923097 = Integer(1928923097)
_sage_const_2348851751 = Integer(2348851751)
_sage_const_1017299113 = Integer(1017299113)
_sage_const_1270160978 = Integer(1270160978)
_sage_const_4110788366 = Integer(4110788366)
_sage_const_2153685733 = Integer(2153685733)
_sage_const_3728171636 = Integer(3728171636)
_sage_const_1876621909 = Integer(1876621909)
_sage_const_485833390 = Integer(485833390)
_sage_const_1651722917 = Integer(1651722917)
_sage_const_2682417343 = Integer(2682417343)
_sage_const_3230797873 = Integer(3230797873)
_sage_const_2820676544 = Integer(2820676544)
_sage_const_2423016272 = Integer(2423016272)
_sage_const_601987276 = Integer(601987276)
_sage_const_4225572480 = Integer(4225572480)
_sage_const_2647148433 = Integer(2647148433)
_sage_const_651290631 = Integer(651290631)
_sage_const_2147758899 = Integer(2147758899)
_sage_const_188984776 = Integer(188984776)
_sage_const_2082976857 = Integer(2082976857)
_sage_const_3175276849 = Integer(3175276849)
_sage_const_3796197588 = Integer(3796197588)
_sage_const_3554347013 = Integer(3554347013)
_sage_const_3543187949 = Integer(3543187949)
_sage_const_496630012 = Integer(496630012)
_sage_const_2208459623 = Integer(2208459623)
_sage_const_3272907041 = Integer(3272907041)
_sage_const_210407366 = Integer(210407366)
_sage_const_3991869385 = Integer(3991869385)
_sage_const_2357925000 = Integer(2357925000)
_sage_const_2070201873 = Integer(2070201873)
_sage_const_977621473 = Integer(977621473)
_sage_const_1255307098 = Integer(1255307098)
_sage_const_4222709020 = Integer(4222709020)
_sage_const_691479729 = Integer(691479729)
_sage_const_3065895902 = Integer(3065895902)
_sage_const_3055126435 = Integer(3055126435)
_sage_const_3263974894 = Integer(3263974894)
_sage_const_3723648766 = Integer(3723648766)
_sage_const_1604036949 = Integer(1604036949)
_sage_const_1105364752 = Integer(1105364752)
_sage_const_4181140885 = Integer(4181140885)
_sage_const_838845188 = Integer(838845188)
_sage_const_2273312903 = Integer(2273312903)
_sage_const_1766468476 = Integer(1766468476)
_sage_const_3353527955 = Integer(3353527955)
_sage_const_1725600089 = Integer(1725600089)
_sage_const_4137000307 = Integer(4137000307)
_sage_const_2427062551 = Integer(2427062551)
_sage_const_3490521428 = Integer(3490521428)
_sage_const_1415370922 = Integer(1415370922)
_sage_const_2679882528 = Integer(2679882528)
_sage_const_3796729361 = Integer(3796729361)
_sage_const_924907542 = Integer(924907542)
_sage_const_2302164408 = Integer(2302164408)
_sage_const_1407497627 = Integer(1407497627)
_sage_const_3167248507 = Integer(3167248507)
_sage_const_1147976257 = Integer(1147976257)
_sage_const_6118358 = Integer(6118358)
_sage_const_4260044114 = Integer(4260044114)
_sage_const_1848231444 = Integer(1848231444)
_sage_const_2720759468 = Integer(2720759468)
_sage_const_3056979594 = Integer(3056979594)
_sage_const_2970693772 = Integer(2970693772)
_sage_const_1493032544 = Integer(1493032544)
_sage_const_744644094 = Integer(744644094)
_sage_const_164286594 = Integer(164286594)
_sage_const_2711565098 = Integer(2711565098)
_sage_const_2030457173 = Integer(2030457173)
_sage_const_1657508875 = Integer(1657508875)
_sage_const_1184221857 = Integer(1184221857)
_sage_const_1268943103 = Integer(1268943103)
_sage_const_2551904019 = Integer(2551904019)
_sage_const_1925257953 = Integer(1925257953)
_sage_const_3712826754 = Integer(3712826754)
_sage_const_3488346100 = Integer(3488346100)
_sage_const_1981020400 = Integer(1981020400)
_sage_const_2161469554 = Integer(2161469554)
_sage_const_1226220086 = Integer(1226220086)
_sage_const_534564588 = Integer(534564588)
_sage_const_307498003 = Integer(307498003)
_sage_const_310722413 = Integer(310722413)
_sage_const_3173002092 = Integer(3173002092)
_sage_const_41750711 = Integer(41750711)
_sage_const_3187637261 = Integer(3187637261)
_sage_const_2713095315 = Integer(2713095315)
_sage_const_433825015 = Integer(433825015)
_sage_const_3807644237 = Integer(3807644237)
_sage_const_2508300676 = Integer(2508300676)
_sage_const_2968131701 = Integer(2968131701)
_sage_const_2767486568 = Integer(2767486568)
_sage_const_294221686 = Integer(294221686)
_sage_const_1595137624 = Integer(1595137624)
_sage_const_1299592670 = Integer(1299592670)
_sage_const_1522586545 = Integer(1522586545)
_sage_const_2703264289 = Integer(2703264289)
_sage_const_798522702 = Integer(798522702)
_sage_const_855707870 = Integer(855707870)
_sage_const_310120694 = Integer(310120694)
_sage_const_3572230065 = Integer(3572230065)
_sage_const_2333612681 = Integer(2333612681)
_sage_const_2041702558 = Integer(2041702558)
_sage_const_104358760 = Integer(104358760)
_sage_const_3423081585 = Integer(3423081585)
_sage_const_2756612595 = Integer(2756612595)
_sage_const_358222834 = Integer(358222834)
_sage_const_1756994402 = Integer(1756994402)
_sage_const_3854650109 = Integer(3854650109)
_sage_const_391562022 = Integer(391562022)
_sage_const_3945956139 = Integer(3945956139)
_sage_const_2040176921 = Integer(2040176921)
_sage_const_557049729 = Integer(557049729)
_sage_const_3427457227 = Integer(3427457227)
_sage_const_4242258101 = Integer(4242258101)
_sage_const_1633630566 = Integer(1633630566)
_sage_const_448351314 = Integer(448351314)
_sage_const_635648450 = Integer(635648450)
_sage_const_779325024 = Integer(779325024)
_sage_const_907754110 = Integer(907754110)
_sage_const_1853532259 = Integer(1853532259)
_sage_const_267542844 = Integer(267542844)
_sage_const_584127385 = Integer(584127385)
_sage_const_3650779727 = Integer(3650779727)
_sage_const_2777540958 = Integer(2777540958)
_sage_const_2510108176 = Integer(2510108176)
_sage_const_3361672012 = Integer(3361672012)
_sage_const_3942017305 = Integer(3942017305)
_sage_const_3360905211 = Integer(3360905211)
_sage_const_2030277480 = Integer(2030277480)
_sage_const_1409676013 = Integer(1409676013)
_sage_const_2392006602 = Integer(2392006602)
_sage_const_3226960738 = Integer(3226960738)
_sage_const_278983218 = Integer(278983218)
_sage_const_3860359492 = Integer(3860359492)
_sage_const_416534282 = Integer(416534282)
_sage_const_2841754813 = Integer(2841754813)
_sage_const_1278787368 = Integer(1278787368)
_sage_const_2412452225 = Integer(2412452225)
_sage_const_331925259 = Integer(331925259)
_sage_const_2851460015 = Integer(2851460015)
_sage_const_1977865620 = Integer(1977865620)
_sage_const_3364921170 = Integer(3364921170)
_sage_const_2540431163 = Integer(2540431163)
_sage_const_383779840 = Integer(383779840)
_sage_const_1054421842 = Integer(1054421842)
_sage_const_4121059223 = Integer(4121059223)
_sage_const_1972176582 = Integer(1972176582)
_sage_const_3932834336 = Integer(3932834336)
_sage_const_1181121744 = Integer(1181121744)
_sage_const_837376906 = Integer(837376906)
_sage_const_2052847070 = Integer(2052847070)
_sage_const_2711665445 = Integer(2711665445)
_sage_const_544313009 = Integer(544313009)
_sage_const_2639086723 = Integer(2639086723)
_sage_const_953043149 = Integer(953043149)
_sage_const_3861671823 = Integer(3861671823)
_sage_const_3334016664 = Integer(3334016664)
_sage_const_891565430 = Integer(891565430)
_sage_const_2754391506 = Integer(2754391506)
_sage_const_1862912009 = Integer(1862912009)
_sage_const_1494085880 = Integer(1494085880)
_sage_const_1755571949 = Integer(1755571949)
_sage_const_837655699 = Integer(837655699)
_sage_const_3956001935 = Integer(3956001935)
_sage_const_2275404762 = Integer(2275404762)
_sage_const_439626653 = Integer(439626653)
_sage_const_3809009290 = Integer(3809009290)
_sage_const_3322116919 = Integer(3322116919)
_sage_const_198773039 = Integer(198773039)
_sage_const_3239534950 = Integer(3239534950)
_sage_const_335298040 = Integer(335298040)


from sage.cpython.string import str_to_bytes
import hashlib
import math


def hash(hexlist, aux="aux321"):
	return IntPrime(int(hashlib.sha256(bytes(hexlist, "ascii")+bytes(str(aux), "ascii")).hexdigest(), _sage_const_16 ))

def countBits(number):
    return math.ceil((math.log(number) /
                math.log(_sage_const_2 )));

F = FiniteField (_sage_const_0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F )
C = EllipticCurve ([F (_sage_const_0 ), F (_sage_const_7 )])
#y^2 = x^3 + ax + b standard curve
#y^2 = x^3 + 0*x + 7 this curve
G = -C.lift_x(_sage_const_0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 ) 
Prime = G.order()
print(Prime)
IntPrime = FiniteField(Prime)


lambdaParameter = countBits(Prime)

PrivKey = _sage_const_3943403887 
PubKey = int(PrivKey) * G

w = _sage_const_3 
L =	_sage_const_5 
k1 = _sage_const_2 **w-_sage_const_1  
k2 = max(_sage_const_0 , math.ceil(lambdaParameter - (w + _sage_const_1 ) * L)) # 0
l = k1+k2
print(k1)
print(k2)
print("l = "+str(l))

a = Prime - _sage_const_1 
b = _sage_const_2 **((w+_sage_const_1 )*L+_sage_const_1 )

def padbytes(byteslist, length):
	if len(byteslist) >= length:
		return byteslist
	else:
		return padbytes('0' + byteslist, length)

def padzero(binary, length):
	if (len(binary) >= length):
		return binary
	binary.insert(_sage_const_0 ,'0')
	return padzero(binary, length)

def convertBinary(binaryInt):
	print("start convert Binary")
	print(binaryInt)
	b = list(str(bin(binaryInt))[_sage_const_2 :])
	print(b)
	B = padzero(b, k2)
	B.reverse()
	print(B)
	return B



def randomElement(Field):
	while True:
		element = Field.random_element()
		if element != _sage_const_0 :
			return element

def inRange(rangetup, hashval):
	if (rangetup[_sage_const_0 ] > rangetup[_sage_const_1 ]):
		if (hashval > rangetup[_sage_const_0 ] or hashval < rangetup[_sage_const_1 ]):
			return True
	if (rangetup[_sage_const_0 ] < rangetup[_sage_const_1 ]):
		if (hashval > rangetup[_sage_const_0 ] and hashval < rangetup[_sage_const_1 ]):
			return True
	return False

def join(a, b, level):
	print("RUn join")
	print(len(a))
	print(len(b))
	result = []
	for i in range(_sage_const_0 , len(a)):
		for j in range(_sage_const_0 , len(b)):
			ab = a[i][_sage_const_1 ]+b[j][_sage_const_1 ]  #todo modlus
			if (inRange(Ii(level), ab)):
				result.append((a[i][_sage_const_0 ]+b[j][_sage_const_0 ],ab,a[i][_sage_const_2 ]+b[j][_sage_const_2 ]))
				currentY = a[i][_sage_const_0 ]+b[j][_sage_const_0 ]
				sumY = _sage_const_0 
				for x in range(_sage_const_0 , len(currentY)):
					sumY += currentY[x]
				assert(sumY == ab)
				if (len(result) >= _sage_const_1024 ): 
					return result
	return result

def Ii(i):
	return (IntPrime(_sage_const_0 )-int((Prime-_sage_const_1 )/_sage_const_2 **(((w-i)*L)+_sage_const_1 )),IntPrime(int((Prime-_sage_const_1 )/_sage_const_2 **(((w-i)*L)+_sage_const_1 ))))

def kListHROS(w, L, P):
	#Setup ----
	print("start setup")
	aux = []
	for i in range(_sage_const_0 , _sage_const_2 **L):
		aux.append(i)
	print(aux)
	Liw = []
	for i in range(_sage_const_0 , len(P)):
		print("p"+str(i))
		Li = []
		for j in range(_sage_const_0 , len(aux)):
			Li.append(([IntPrime(hash(encode(P[i]), aux[j]))],IntPrime(hash(encode(P[i]), aux[j])),[aux[j]]))
		Liw.append(Li)
	Tree = [Liw]

	##Collison ----
	for x in range(_sage_const_0 , w): #add one because SUM is inclusive and end range is exclusive minus one because the range should be 1 - w
		print("level: "+str(x))
		FLi = []
		level = w-x
		TreeLevel = Tree[x]
		for j in range(_sage_const_0 , _sage_const_2 **(level-_sage_const_1 )): #add one because SUM is inclusive and end range is exclusive minus one because we are indexing from 0
			print("j"+(str(j)))
			FLi.append(join(TreeLevel[j*_sage_const_2 ],TreeLevel[_sage_const_2 *j+_sage_const_1 ],level)) #minus one because lists are 1 indexed in the paper
		Tree.append(FLi)
		
	finalTree = Tree[w][_sage_const_0 ]
	result = []
	for i in range(_sage_const_0 , len(finalTree)):
		if inRange(Ii(-_sage_const_1 ), finalTree[i][_sage_const_1 ]):
			result = (finalTree[i][_sage_const_0 ], finalTree[i][_sage_const_1 ], finalTree[i][_sage_const_2 ])
			break
		result = ([],_sage_const_0 ,[])
	return result

def main():			
	K = []
	R = []
	M = []
	C = []
	S = []
	CB = []
	zero = []

	midTerm = int((Prime-_sage_const_1 )/_sage_const_2 **((w+_sage_const_1 )*L+_sage_const_1 ))

	

	# print(hashlib.sha256(bytes.fromhex("031e09c104cdb9a41285f802b9f7e80e74781c630f66db2f151dfa991dcc1214299a")).hexdigest())
	#Generate zero array
	for i in range(_sage_const_0 , l):
		zero.append(IntPrime(_sage_const_0 ))
	# GENERATE VALID SIGS
	# M = [[3952459683, 140620442],[2017216018, 2009046716],[1509335457, 4077915080],[1932088938, 2486682281],[3314941358, 499585529],[3362337200, 2211775199],[2330471963, 3606788670],[4134288763, 3260445262],[2586822768, 1128746907],[3723722377, 1544039621],[1516844343, 3838049092],[3234026267, 1742413807],[3209196705, 4042251632],[3975864098, 1096753163],[3633611705, 767066282],[3768454157, 539424771],[3606753106, 18313224],[1075685129, 737257314],[1301487686, 364160362],[4217215080, 1352247727],[1914230622, 142035844],[3445740864, 2469049293],[1797902554, 3319456240],[2229753882, 2191947181],[3976251297, 1619755698],[2552941005, 2301914585],[2503888055, 1844588746],[3047825066, 1928880188],[4155801463, 2583818105],[3106220087, 3279762563],[3212767151, 3807893560],[2229425900, 2739136220],[1632389433, 2902152512],[83693948, 2093956158],[1095902075, 2868146148],[766459304, 1914935438],[3406978115, 1395422425],[2520335904, 1504028136],[4023735222, 3046846676],[1201078568, 375908758],[119286203, 1853781173],[2369168331, 1804912580],[733969225, 3163390675],[328558366, 4154804709],[2922558557, 1022427754],[2077866832, 2841336229],[4112332032, 3683257847],[3115064832, 1424320860],[709678450, 1251382373],[3834362799, 3311489886],[1059044347, 1840764376],[2720090515, 3505032467],[593507574, 661286706],[1143943486, 496329025],[472939875, 2414880472],[2030246970, 324673756],[3697634721, 449647308],[2787228712, 4205775805],[2018848604, 3934436566],[3711878379, 586563327],[1900151571, 1782602950],[204982352, 1168800016],[1760581905, 3312121479],[389216358, 2538577611],[1600728930, 42948890],[2790096070, 2592628431],[603771702, 364764022],[3657953974, 345932725],[2389681322, 2511987192],[2554772220, 4000714081],[2512894656, 1282546849],[607700325, 3520902869],[3760734200, 1167290368],[366505776, 809138353],[1838612482, 3525364779],[1952591117, 3667128651],[577679124, 209929118],[952525595, 2805017976],[1908102323, 3107524892],[3998515704, 2818601629],[1632644731, 1673264357],[2478623148, 2387096063],[1271224779, 3545655642],[1338634086, 208565460],[1144254551, 566749384],[1213444573, 2270680829],[2667338802, 447393599],[2745909947, 1413657208],[2818038301, 2611315625],[558788, 2001781779],[1145522126, 3864133576],[2855615464, 1175579813],[445158637, 817566918],[1344934809, 1890208939],[595665807, 2083040701],[2546103415, 3799539368],[1653802914, 3120286505],[4017684220, 4108938953],[385794252, 3054087990],[2519574417, 2903452730],[1291639897, 826798828],[586206110, 3285585972],[2920486174, 3175925084],[459481797, 466529033],[848706037, 2934537306],[4289714493, 1245082734],[2589996752, 2389930559],[4163622221, 1032226453],[4047370927, 3998477336],[4203406315, 2577438133],[4190796340, 1445431932],[542197919, 1523076747],[3156657627, 1151167272],[899779775, 3888750110],[4178055519, 1059680825],[134098916, 3241953930],[1403191210, 2782617305],[1596932414, 3824062207],[1446860573, 2646807260],[3227579532, 3132938294],[2768482560, 461251643],[661133937, 3012269095],[2269874965, 3805639755],[2364681041, 226700072],[3071628030, 740031554],[1029331527, 4133052612],[206116831, 3546889884],[4110204268, 748254024],[2441189548, 4054227839],[1907595159, 4000683750],[3249068243, 1504667377],[3054475378, 3276497813],[1509430713, 2677043124],[3244208999, 446714967],[1180268955, 1106168058],[1413675763, 711113383],[377958134, 1247237878],[1756911021, 201052169],[1959269810, 3190208469],[3099357099, 3092865037],[195020592, 3379419715],[1392797718, 3609500251],[3967480620, 1470003086],[1611273651, 2678649306],[3793943163, 4263260479],[2272670323, 3552013912],[2327802720, 964409761],[2589215214, 2428882680],[648055316, 4123710212],[1673774034, 3887832523],[1441529431, 4290921581],[807526737, 1496000033],[3361527512, 2194767334],[1819445301, 2517018921],[3594711790, 2796122842],[872001322, 3229855629],[3114124587, 4169245642],[2616053411, 3909511573],[994489645, 3587611841],[2210050416, 437035565],[554583559, 1559347049],[1112273838, 4121356635],[3785139433, 4090626494],[1931371692, 3548553825],[4181304425, 1469510419],[2206424494, 3477963051],[3849342270, 3703460250],[1334252130, 288572380],[971216662, 1815390916],[3493969241, 2608286018],[651275292, 1215400968],[1898101947, 3439487858],[2006176490, 500620238],[730932289, 2279956838],[101866724, 3243125721],[4093792017, 2824718385],[296941721, 2486937000],[3435465698, 3023964098],[1248385944, 3209359661],[433832325, 2414181781],[1035892004, 1267320598],[781849687, 4175962999],[3250906632, 3334829192],[2799399854, 1317434321],[1417465101, 4117758796],[4092211979, 2879341984],[2160184051, 412025946],[3913954063, 2290482390],[2858885770, 1497709652],[2808944091, 1308877778],[3190731050, 1832988858],[978508767, 1900348650],[3251776573, 3896457431],[4094300135, 2656886649],[1616027087, 1809944247],[3790895900, 1974078952],[2826935185, 3261996568],[239419057, 2645414694],[1914423974, 4066359836],[2957408273, 1580192614],[3529152483, 498440598],[2074047399, 3878220458],[28566736, 3717809264],[3717577698, 2786808071],[2634436011, 3528688245],[57331723, 3941478473],[532788744, 3085440955],[631024091, 2092762845],[2900199454, 1681880163],[65030485, 1923886359],[3186692127, 2373847057],[2970320823, 2179393866],[4232235063, 2724142643],[434961598, 2212549068],[1852891838, 2174479740],[205195157, 137033942],[1131010727, 907169493],[594560834, 3286951263],[2279593073, 2628790437],[222639794, 1974918295],[3285634123, 2045561189],[1882398249, 283934601],[1265040621, 3601155789],[3231133674, 1070736492],[2604041139, 1286644694],[3471881410, 3998008737],[4166692921, 1984749305],[3717312094, 170493346],[4151638014, 3100096563],[1781970618, 1469465656],[1129563677, 3126950261],[2598959897, 3930980098],[3145416236, 2065799006],[503245321, 2349936549],[34718926, 466644579],[4081985580, 3273641486],[1620257026, 2982646358],[199380680, 87748991],[1537697907, 1353507210],[649640394, 923002607],[3954168617, 3588753946],[2395140467, 3528208126],[942612979, 535721316],[277984505, 2398191553],[3198280166, 3103354176],[1906004320, 703614489],[2733831898, 167894300],[3927722210, 462166401],[1949372081, 394481983],[142259367, 2142924833],[3723138218, 1513897917],[2229626255, 2108490120],[1230492766, 3008774167],[3812375492, 3074455388],[1848665308, 3120260622],[4141159246, 621593509]]
	M = [[_sage_const_3952459683 ,_sage_const_140620442 ],[_sage_const_2017216018 ,_sage_const_2009046716 ],[_sage_const_1509335457 ,_sage_const_4077915080 ],[_sage_const_1932088938 ,_sage_const_2486682281 ],[_sage_const_3314941358 ,_sage_const_499585529 ],[_sage_const_3362337200 ,_sage_const_2211775199 ],[_sage_const_2330471963 ,_sage_const_3606788670 ],[_sage_const_4134288763 ,_sage_const_3260445262 ],[_sage_const_2586822768 ,_sage_const_1128746907 ],[_sage_const_3723722377 ,_sage_const_1544039621 ],[_sage_const_1516844343 ,_sage_const_3838049092 ],[_sage_const_3234026267 ,_sage_const_1742413807 ],[_sage_const_3209196705 ,_sage_const_4042251632 ],[_sage_const_3975864098 ,_sage_const_1096753163 ],[_sage_const_3633611705 ,_sage_const_767066282 ],[_sage_const_3768454157 ,_sage_const_539424771 ],[_sage_const_3606753106 ,_sage_const_18313224 ],[_sage_const_1075685129 ,_sage_const_737257314 ],[_sage_const_1301487686 ,_sage_const_364160362 ],[_sage_const_4217215080 ,_sage_const_1352247727 ],[_sage_const_1914230622 ,_sage_const_142035844 ],[_sage_const_3445740864 ,_sage_const_2469049293 ],[_sage_const_1797902554 ,_sage_const_3319456240 ],[_sage_const_2229753882 ,_sage_const_2191947181 ],[_sage_const_3976251297 ,_sage_const_1619755698 ],[_sage_const_2552941005 ,_sage_const_2301914585 ],[_sage_const_2503888055 ,_sage_const_1844588746 ],[_sage_const_3047825066 ,_sage_const_1928880188 ],[_sage_const_4155801463 ,_sage_const_2583818105 ],[_sage_const_3106220087 ,_sage_const_3279762563 ],[_sage_const_3212767151 ,_sage_const_3807893560 ],[_sage_const_2229425900 ,_sage_const_2739136220 ],[_sage_const_1632389433 ,_sage_const_2902152512 ],[_sage_const_83693948 ,_sage_const_2093956158 ],[_sage_const_1095902075 ,_sage_const_2868146148 ],[_sage_const_766459304 ,_sage_const_1914935438 ],[_sage_const_3406978115 ,_sage_const_1395422425 ],[_sage_const_2520335904 ,_sage_const_1504028136 ],[_sage_const_4023735222 ,_sage_const_3046846676 ],[_sage_const_1201078568 ,_sage_const_375908758 ],[_sage_const_119286203 ,_sage_const_1853781173 ],[_sage_const_2369168331 ,_sage_const_1804912580 ],[_sage_const_733969225 ,_sage_const_3163390675 ],[_sage_const_328558366 ,_sage_const_4154804709 ],[_sage_const_2922558557 ,_sage_const_1022427754 ],[_sage_const_2077866832 ,_sage_const_2841336229 ],[_sage_const_4112332032 ,_sage_const_3683257847 ],[_sage_const_3115064832 ,_sage_const_1424320860 ],[_sage_const_709678450 ,_sage_const_1251382373 ],[_sage_const_3834362799 ,_sage_const_3311489886 ],[_sage_const_1059044347 ,_sage_const_1840764376 ],[_sage_const_2720090515 ,_sage_const_3505032467 ],[_sage_const_593507574 ,_sage_const_661286706 ],[_sage_const_1143943486 ,_sage_const_496329025 ],[_sage_const_472939875 ,_sage_const_2414880472 ],[_sage_const_2030246970 ,_sage_const_324673756 ],[_sage_const_3697634721 ,_sage_const_449647308 ],[_sage_const_2787228712 ,_sage_const_4205775805 ],[_sage_const_2018848604 ,_sage_const_3934436566 ],[_sage_const_3711878379 ,_sage_const_586563327 ],[_sage_const_1900151571 ,_sage_const_1782602950 ],[_sage_const_204982352 ,_sage_const_1168800016 ],[_sage_const_1760581905 ,_sage_const_3312121479 ],[_sage_const_389216358 ,_sage_const_2538577611 ],[_sage_const_1600728930 ,_sage_const_42948890 ],[_sage_const_2790096070 ,_sage_const_2592628431 ],[_sage_const_603771702 ,_sage_const_364764022 ],[_sage_const_3657953974 ,_sage_const_345932725 ],[_sage_const_2389681322 ,_sage_const_2511987192 ],[_sage_const_2554772220 ,_sage_const_4000714081 ],[_sage_const_2512894656 ,_sage_const_1282546849 ],[_sage_const_607700325 ,_sage_const_3520902869 ],[_sage_const_3760734200 ,_sage_const_1167290368 ],[_sage_const_366505776 ,_sage_const_809138353 ],[_sage_const_1838612482 ,_sage_const_3525364779 ],[_sage_const_1952591117 ,_sage_const_3667128651 ],[_sage_const_577679124 ,_sage_const_209929118 ],[_sage_const_952525595 ,_sage_const_2805017976 ],[_sage_const_1908102323 ,_sage_const_3107524892 ],[_sage_const_3998515704 ,_sage_const_2818601629 ],[_sage_const_1632644731 ,_sage_const_1673264357 ],[_sage_const_2478623148 ,_sage_const_2387096063 ],[_sage_const_1271224779 ,_sage_const_3545655642 ],[_sage_const_1338634086 ,_sage_const_208565460 ],[_sage_const_1144254551 ,_sage_const_566749384 ],[_sage_const_1213444573 ,_sage_const_2270680829 ],[_sage_const_2667338802 ,_sage_const_447393599 ],[_sage_const_2745909947 ,_sage_const_1413657208 ],[_sage_const_2818038301 ,_sage_const_2611315625 ],[_sage_const_558788 ,_sage_const_2001781779 ],[_sage_const_1145522126 ,_sage_const_3864133576 ],[_sage_const_2855615464 ,_sage_const_1175579813 ],[_sage_const_445158637 ,_sage_const_817566918 ],[_sage_const_1344934809 ,_sage_const_1890208939 ],[_sage_const_595665807 ,_sage_const_2083040701 ],[_sage_const_2546103415 ,_sage_const_3799539368 ],[_sage_const_1653802914 ,_sage_const_3120286505 ],[_sage_const_4017684220 ,_sage_const_4108938953 ],[_sage_const_385794252 ,_sage_const_3054087990 ],[_sage_const_2519574417 ,_sage_const_2903452730 ],[_sage_const_1291639897 ,_sage_const_826798828 ],[_sage_const_586206110 ,_sage_const_3285585972 ],[_sage_const_2920486174 ,_sage_const_3175925084 ],[_sage_const_459481797 ,_sage_const_466529033 ],[_sage_const_848706037 ,_sage_const_2934537306 ],[_sage_const_4289714493 ,_sage_const_1245082734 ],[_sage_const_2589996752 ,_sage_const_2389930559 ],[_sage_const_4163622221 ,_sage_const_1032226453 ],[_sage_const_4047370927 ,_sage_const_3998477336 ],[_sage_const_4203406315 ,_sage_const_2577438133 ],[_sage_const_4190796340 ,_sage_const_1445431932 ],[_sage_const_542197919 ,_sage_const_1523076747 ],[_sage_const_3156657627 ,_sage_const_1151167272 ],[_sage_const_899779775 ,_sage_const_3888750110 ],[_sage_const_4178055519 ,_sage_const_1059680825 ],[_sage_const_134098916 ,_sage_const_3241953930 ],[_sage_const_1403191210 ,_sage_const_2782617305 ],[_sage_const_1596932414 ,_sage_const_3824062207 ],[_sage_const_1446860573 ,_sage_const_2646807260 ],[_sage_const_3227579532 ,_sage_const_3132938294 ],[_sage_const_2768482560 ,_sage_const_461251643 ],[_sage_const_661133937 ,_sage_const_3012269095 ],[_sage_const_2269874965 ,_sage_const_3805639755 ],[_sage_const_2364681041 ,_sage_const_226700072 ],[_sage_const_3071628030 ,_sage_const_740031554 ],[_sage_const_1029331527 ,_sage_const_4133052612 ],[_sage_const_206116831 ,_sage_const_3546889884 ],[_sage_const_4110204268 ,_sage_const_748254024 ],[_sage_const_2441189548 ,_sage_const_4054227839 ],[_sage_const_1907595159 ,_sage_const_4000683750 ],[_sage_const_3249068243 ,_sage_const_1504667377 ],[_sage_const_3054475378 ,_sage_const_3276497813 ],[_sage_const_1509430713 ,_sage_const_2677043124 ],[_sage_const_3244208999 ,_sage_const_446714967 ],[_sage_const_1180268955 ,_sage_const_1106168058 ],[_sage_const_1413675763 ,_sage_const_711113383 ],[_sage_const_377958134 ,_sage_const_1247237878 ],[_sage_const_1756911021 ,_sage_const_201052169 ],[_sage_const_1959269810 ,_sage_const_3190208469 ],[_sage_const_3099357099 ,_sage_const_3092865037 ],[_sage_const_195020592 ,_sage_const_3379419715 ],[_sage_const_1392797718 ,_sage_const_3609500251 ],[_sage_const_3967480620 ,_sage_const_1470003086 ],[_sage_const_1611273651 ,_sage_const_2678649306 ],[_sage_const_3793943163 ,_sage_const_4263260479 ],[_sage_const_2272670323 ,_sage_const_3552013912 ],[_sage_const_2327802720 ,_sage_const_964409761 ],[_sage_const_2589215214 ,_sage_const_2428882680 ],[_sage_const_648055316 ,_sage_const_4123710212 ],[_sage_const_1673774034 ,_sage_const_3887832523 ],[_sage_const_1441529431 ,_sage_const_4290921581 ],[_sage_const_807526737 ,_sage_const_1496000033 ],[_sage_const_3361527512 ,_sage_const_2194767334 ],[_sage_const_1819445301 ,_sage_const_2517018921 ],[_sage_const_3594711790 ,_sage_const_2796122842 ],[_sage_const_872001322 ,_sage_const_3229855629 ],[_sage_const_3114124587 ,_sage_const_4169245642 ],[_sage_const_2616053411 ,_sage_const_3909511573 ],[_sage_const_994489645 ,_sage_const_3587611841 ],[_sage_const_2210050416 ,_sage_const_437035565 ],[_sage_const_554583559 ,_sage_const_1559347049 ],[_sage_const_1112273838 ,_sage_const_4121356635 ],[_sage_const_3785139433 ,_sage_const_4090626494 ],[_sage_const_1931371692 ,_sage_const_3548553825 ],[_sage_const_4181304425 ,_sage_const_1469510419 ],[_sage_const_2206424494 ,_sage_const_3477963051 ],[_sage_const_3849342270 ,_sage_const_3703460250 ],[_sage_const_1334252130 ,_sage_const_288572380 ],[_sage_const_971216662 ,_sage_const_1815390916 ],[_sage_const_3493969241 ,_sage_const_2608286018 ],[_sage_const_651275292 ,_sage_const_1215400968 ],[_sage_const_1898101947 ,_sage_const_3439487858 ],[_sage_const_2006176490 ,_sage_const_500620238 ],[_sage_const_730932289 ,_sage_const_2279956838 ],[_sage_const_101866724 ,_sage_const_3243125721 ],[_sage_const_4093792017 ,_sage_const_2824718385 ],[_sage_const_296941721 ,_sage_const_2486937000 ],[_sage_const_3435465698 ,_sage_const_3023964098 ],[_sage_const_1248385944 ,_sage_const_3209359661 ],[_sage_const_433832325 ,_sage_const_2414181781 ],[_sage_const_1035892004 ,_sage_const_1267320598 ],[_sage_const_781849687 ,_sage_const_4175962999 ],[_sage_const_3250906632 ,_sage_const_3334829192 ],[_sage_const_2799399854 ,_sage_const_1317434321 ],[_sage_const_1417465101 ,_sage_const_4117758796 ],[_sage_const_4092211979 ,_sage_const_2879341984 ],[_sage_const_2160184051 ,_sage_const_412025946 ],[_sage_const_3913954063 ,_sage_const_2290482390 ],[_sage_const_2858885770 ,_sage_const_1497709652 ],[_sage_const_2808944091 ,_sage_const_1308877778 ],[_sage_const_3190731050 ,_sage_const_1832988858 ],[_sage_const_978508767 ,_sage_const_1900348650 ],[_sage_const_3251776573 ,_sage_const_3896457431 ],[_sage_const_4094300135 ,_sage_const_2656886649 ],[_sage_const_1616027087 ,_sage_const_1809944247 ],[_sage_const_3790895900 ,_sage_const_1974078952 ],[_sage_const_2826935185 ,_sage_const_3261996568 ],[_sage_const_239419057 ,_sage_const_2645414694 ],[_sage_const_1914423974 ,_sage_const_4066359836 ],[_sage_const_2957408273 ,_sage_const_1580192614 ],[_sage_const_3529152483 ,_sage_const_498440598 ],[_sage_const_2074047399 ,_sage_const_3878220458 ],[_sage_const_28566736 ,_sage_const_3717809264 ],[_sage_const_3717577698 ,_sage_const_2786808071 ],[_sage_const_2634436011 ,_sage_const_3528688245 ],[_sage_const_57331723 ,_sage_const_3941478473 ],[_sage_const_532788744 ,_sage_const_3085440955 ],[_sage_const_631024091 ,_sage_const_2092762845 ],[_sage_const_2900199454 ,_sage_const_1681880163 ],[_sage_const_65030485 ,_sage_const_1923886359 ],[_sage_const_3186692127 ,_sage_const_2373847057 ],[_sage_const_2970320823 ,_sage_const_2179393866 ],[_sage_const_4232235063 ,_sage_const_2724142643 ],[_sage_const_434961598 ,_sage_const_2212549068 ],[_sage_const_1852891838 ,_sage_const_2174479740 ],[_sage_const_205195157 ,_sage_const_137033942 ],[_sage_const_1131010727 ,_sage_const_907169493 ],[_sage_const_594560834 ,_sage_const_3286951263 ],[_sage_const_2279593073 ,_sage_const_2628790437 ],[_sage_const_222639794 ,_sage_const_1974918295 ],[_sage_const_3285634123 ,_sage_const_2045561189 ],[_sage_const_1882398249 ,_sage_const_283934601 ],[_sage_const_1265040621 ,_sage_const_3601155789 ],[_sage_const_3231133674 ,_sage_const_1070736492 ],[_sage_const_2604041139 ,_sage_const_1286644694 ],[_sage_const_3471881410 ,_sage_const_3998008737 ],[_sage_const_4166692921 ,_sage_const_1984749305 ],[_sage_const_3717312094 ,_sage_const_170493346 ],[_sage_const_4151638014 ,_sage_const_3100096563 ],[_sage_const_1781970618 ,_sage_const_1469465656 ],[_sage_const_1129563677 ,_sage_const_3126950261 ],[_sage_const_2598959897 ,_sage_const_3930980098 ],[_sage_const_3145416236 ,_sage_const_2065799006 ],[_sage_const_503245321 ,_sage_const_2349936549 ],[_sage_const_34718926 ,_sage_const_466644579 ],[_sage_const_4081985580 ,_sage_const_3273641486 ],[_sage_const_1620257026 ,_sage_const_2982646358 ],[_sage_const_199380680 ,_sage_const_87748991 ],[_sage_const_1537697907 ,_sage_const_1353507210 ],[_sage_const_649640394 ,_sage_const_923002607 ],[_sage_const_3954168617 ,_sage_const_3588753946 ],[_sage_const_2395140467 ,_sage_const_3528208126 ],[_sage_const_942612979 ,_sage_const_535721316 ],[_sage_const_277984505 ,_sage_const_2398191553 ],[_sage_const_3198280166 ,_sage_const_3103354176 ],[_sage_const_1906004320 ,_sage_const_703614489 ],[_sage_const_2733831898 ,_sage_const_167894300 ],[_sage_const_3927722210 ,_sage_const_462166401 ],[_sage_const_1949372081 ,_sage_const_394481983 ],[_sage_const_142259367 ,_sage_const_2142924833 ],[_sage_const_3723138218 ,_sage_const_1513897917 ],[_sage_const_2229626255 ,_sage_const_2108490120 ],[_sage_const_1230492766 ,_sage_const_3008774167 ],[_sage_const_3812375492 ,_sage_const_3074455388 ],[_sage_const_1848665308 ,_sage_const_3120260622 ],[_sage_const_4141159246 ,_sage_const_621593509 ],[_sage_const_1520284440 ,_sage_const_419672987 ]]
	# K = [3952319235,1972040021,2682795333,4248958407,2430489776,1998982847,2447726525,4186472610,4072971075,193515222,1070797965,836171487,1787824246,664674363,734630056,4028847063,1371828711,4246510952,3343965217,2643351565,1217664939,2940984862,3942219648,505760561,540562365,3221206580,3713131495,3367407149,1345854475,2500012197,877056782,2010460269,1125841596,393541314,1093377296,2207060009,2193458018,3185777727,1734059597,2835440292,3795486676,236382810,196722783,273542651,1939662971,3839481177,3809197040,4127081423,2254237506,3859992183,2935782939,1709109184,1631021458,166788004,1243239501,3911919396,127742131,2799649543,2699707072,894878619,2134355819,874662292,4243725233,2965176282,3631572266,246165295,1326531614,434637048,4093779404,4275927089,330883731,2573083971,4041603319,1078826072,1205178391,2804818001,3648185928,2062983627,3964754414,3825757328,2268216703,3710959221,1198002389,4036779168,2492232218,1928923097,2348851751,1017299113,1270160978,4110788366,2153685733,3728171636,1876621909,485833390,1651722917,2682417343,3230797873,2820676544,2423016272,601987276,4225572480,2647148433,651290631,2147758899,188984776,2082976857,3175276849,3796197588,3554347013,3543187949,496630012,2208459623,3272907041,210407366,3991869385,2357925000,2070201873,977621473,1255307098,4222709020,691479729,3065895902,3055126435,3263974894,3723648766,1604036949,1105364752,4181140885,838845188,2273312903,1766468476,3353527955,1725600089,4137000307,2427062551,3490521428,1415370922,2679882528,3796729361,924907542,2302164408,1407497627,3167248507,1147976257,6118358,4260044114,1848231444,2720759468,3056979594,2970693772,1493032544,744644094,164286594,2711565098,2030457173,1657508875,1184221857,1268943103,2551904019,1925257953,3712826754,3488346100,1981020400,2161469554,1226220086,534564588,307498003,310722413,3173002092,41750711,3187637261,2713095315,433825015,3807644237,2508300676,2968131701,2767486568,294221686,1595137624,1299592670,1522586545,2703264289,798522702,855707870,310120694,3572230065,2333612681,2041702558,104358760,3423081585,2756612595,358222834,1756994402,3854650109,391562022,3945956139,2040176921,557049729,3427457227,4242258101,1633630566,448351314,635648450,779325024,907754110,1853532259,267542844,584127385,3650779727,2777540958,2510108176,3361672012,3942017305,3360905211,2030277480,1409676013,2392006602,3226960738,278983218,3860359492,416534282,2841754813,1278787368,2412452225,331925259,2851460015,1977865620,3364921170,2540431163,383779840,1054421842,4121059223,1972176582,3932834336,1181121744,837376906,2052847070,2711665445,544313009,2639086723,953043149,3861671823,3334016664,891565430,2754391506,1862912009,1494085880,1755571949,837655699,3956001935,2275404762,439626653,3809009290,3322116919,198773039,3239534950]
	K = [_sage_const_3952319235 ,_sage_const_1972040021 ,_sage_const_2682795333 ,_sage_const_4248958407 ,_sage_const_2430489776 ,_sage_const_1998982847 ,_sage_const_2447726525 ,_sage_const_4186472610 ,_sage_const_4072971075 ,_sage_const_193515222 ,_sage_const_1070797965 ,_sage_const_836171487 ,_sage_const_1787824246 ,_sage_const_664674363 ,_sage_const_734630056 ,_sage_const_4028847063 ,_sage_const_1371828711 ,_sage_const_4246510952 ,_sage_const_3343965217 ,_sage_const_2643351565 ,_sage_const_1217664939 ,_sage_const_2940984862 ,_sage_const_3942219648 ,_sage_const_505760561 ,_sage_const_540562365 ,_sage_const_3221206580 ,_sage_const_3713131495 ,_sage_const_3367407149 ,_sage_const_1345854475 ,_sage_const_2500012197 ,_sage_const_877056782 ,_sage_const_2010460269 ,_sage_const_1125841596 ,_sage_const_393541314 ,_sage_const_1093377296 ,_sage_const_2207060009 ,_sage_const_2193458018 ,_sage_const_3185777727 ,_sage_const_1734059597 ,_sage_const_2835440292 ,_sage_const_3795486676 ,_sage_const_236382810 ,_sage_const_196722783 ,_sage_const_273542651 ,_sage_const_1939662971 ,_sage_const_3839481177 ,_sage_const_3809197040 ,_sage_const_4127081423 ,_sage_const_2254237506 ,_sage_const_3859992183 ,_sage_const_2935782939 ,_sage_const_1709109184 ,_sage_const_1631021458 ,_sage_const_166788004 ,_sage_const_1243239501 ,_sage_const_3911919396 ,_sage_const_127742131 ,_sage_const_2799649543 ,_sage_const_2699707072 ,_sage_const_894878619 ,_sage_const_2134355819 ,_sage_const_874662292 ,_sage_const_4243725233 ,_sage_const_2965176282 ,_sage_const_3631572266 ,_sage_const_246165295 ,_sage_const_1326531614 ,_sage_const_434637048 ,_sage_const_4093779404 ,_sage_const_4275927089 ,_sage_const_330883731 ,_sage_const_2573083971 ,_sage_const_4041603319 ,_sage_const_1078826072 ,_sage_const_1205178391 ,_sage_const_2804818001 ,_sage_const_3648185928 ,_sage_const_2062983627 ,_sage_const_3964754414 ,_sage_const_3825757328 ,_sage_const_2268216703 ,_sage_const_3710959221 ,_sage_const_1198002389 ,_sage_const_4036779168 ,_sage_const_2492232218 ,_sage_const_1928923097 ,_sage_const_2348851751 ,_sage_const_1017299113 ,_sage_const_1270160978 ,_sage_const_4110788366 ,_sage_const_2153685733 ,_sage_const_3728171636 ,_sage_const_1876621909 ,_sage_const_485833390 ,_sage_const_1651722917 ,_sage_const_2682417343 ,_sage_const_3230797873 ,_sage_const_2820676544 ,_sage_const_2423016272 ,_sage_const_601987276 ,_sage_const_4225572480 ,_sage_const_2647148433 ,_sage_const_651290631 ,_sage_const_2147758899 ,_sage_const_188984776 ,_sage_const_2082976857 ,_sage_const_3175276849 ,_sage_const_3796197588 ,_sage_const_3554347013 ,_sage_const_3543187949 ,_sage_const_496630012 ,_sage_const_2208459623 ,_sage_const_3272907041 ,_sage_const_210407366 ,_sage_const_3991869385 ,_sage_const_2357925000 ,_sage_const_2070201873 ,_sage_const_977621473 ,_sage_const_1255307098 ,_sage_const_4222709020 ,_sage_const_691479729 ,_sage_const_3065895902 ,_sage_const_3055126435 ,_sage_const_3263974894 ,_sage_const_3723648766 ,_sage_const_1604036949 ,_sage_const_1105364752 ,_sage_const_4181140885 ,_sage_const_838845188 ,_sage_const_2273312903 ,_sage_const_1766468476 ,_sage_const_3353527955 ,_sage_const_1725600089 ,_sage_const_4137000307 ,_sage_const_2427062551 ,_sage_const_3490521428 ,_sage_const_1415370922 ,_sage_const_2679882528 ,_sage_const_3796729361 ,_sage_const_924907542 ,_sage_const_2302164408 ,_sage_const_1407497627 ,_sage_const_3167248507 ,_sage_const_1147976257 ,_sage_const_6118358 ,_sage_const_4260044114 ,_sage_const_1848231444 ,_sage_const_2720759468 ,_sage_const_3056979594 ,_sage_const_2970693772 ,_sage_const_1493032544 ,_sage_const_744644094 ,_sage_const_164286594 ,_sage_const_2711565098 ,_sage_const_2030457173 ,_sage_const_1657508875 ,_sage_const_1184221857 ,_sage_const_1268943103 ,_sage_const_2551904019 ,_sage_const_1925257953 ,_sage_const_3712826754 ,_sage_const_3488346100 ,_sage_const_1981020400 ,_sage_const_2161469554 ,_sage_const_1226220086 ,_sage_const_534564588 ,_sage_const_307498003 ,_sage_const_310722413 ,_sage_const_3173002092 ,_sage_const_41750711 ,_sage_const_3187637261 ,_sage_const_2713095315 ,_sage_const_433825015 ,_sage_const_3807644237 ,_sage_const_2508300676 ,_sage_const_2968131701 ,_sage_const_2767486568 ,_sage_const_294221686 ,_sage_const_1595137624 ,_sage_const_1299592670 ,_sage_const_1522586545 ,_sage_const_2703264289 ,_sage_const_798522702 ,_sage_const_855707870 ,_sage_const_310120694 ,_sage_const_3572230065 ,_sage_const_2333612681 ,_sage_const_2041702558 ,_sage_const_104358760 ,_sage_const_3423081585 ,_sage_const_2756612595 ,_sage_const_358222834 ,_sage_const_1756994402 ,_sage_const_3854650109 ,_sage_const_391562022 ,_sage_const_3945956139 ,_sage_const_2040176921 ,_sage_const_557049729 ,_sage_const_3427457227 ,_sage_const_4242258101 ,_sage_const_1633630566 ,_sage_const_448351314 ,_sage_const_635648450 ,_sage_const_779325024 ,_sage_const_907754110 ,_sage_const_1853532259 ,_sage_const_267542844 ,_sage_const_584127385 ,_sage_const_3650779727 ,_sage_const_2777540958 ,_sage_const_2510108176 ,_sage_const_3361672012 ,_sage_const_3942017305 ,_sage_const_3360905211 ,_sage_const_2030277480 ,_sage_const_1409676013 ,_sage_const_2392006602 ,_sage_const_3226960738 ,_sage_const_278983218 ,_sage_const_3860359492 ,_sage_const_416534282 ,_sage_const_2841754813 ,_sage_const_1278787368 ,_sage_const_2412452225 ,_sage_const_331925259 ,_sage_const_2851460015 ,_sage_const_1977865620 ,_sage_const_3364921170 ,_sage_const_2540431163 ,_sage_const_383779840 ,_sage_const_1054421842 ,_sage_const_4121059223 ,_sage_const_1972176582 ,_sage_const_3932834336 ,_sage_const_1181121744 ,_sage_const_837376906 ,_sage_const_2052847070 ,_sage_const_2711665445 ,_sage_const_544313009 ,_sage_const_2639086723 ,_sage_const_953043149 ,_sage_const_3861671823 ,_sage_const_3334016664 ,_sage_const_891565430 ,_sage_const_2754391506 ,_sage_const_1862912009 ,_sage_const_1494085880 ,_sage_const_1755571949 ,_sage_const_837655699 ,_sage_const_3956001935 ,_sage_const_2275404762 ,_sage_const_439626653 ,_sage_const_3809009290 ,_sage_const_3322116919 ,_sage_const_198773039 ,_sage_const_3239534950 ,_sage_const_335298040 ]
	for i in range(_sage_const_0 , l):
		r = int(K[i]) * G
		R.append(r)
		c0 = hash(encode(r), M[i][_sage_const_0 ])
		c1 = hash(encode(r), M[i][_sage_const_1 ])
		CB.append([c0, c1])

	#DEFINE PL
	def Pl(x, public=True):
		#FT
		firstTerm = _sage_const_0 
		for i in range(_sage_const_0 , l):
			if public:
				a = x[i] - int(CB[i][_sage_const_0 ]) * G
			else:
				a = int(x[i]) - CB[i][_sage_const_0 ]
			b = CB[i][_sage_const_1 ] - CB[i][_sage_const_0 ]
			firstTerm += int(_sage_const_2 **i / b) * a
		#ET
		endTerm = _sage_const_0 
		for i in range(k2, (k1+k2-_sage_const_1 )+_sage_const_1 ):
			endTerm += x[i]
		if public:
			result = firstTerm - (midTerm * G) - endTerm
		else:
			result = firstTerm - midTerm - endTerm
		return result
	#RUN PL ON R TO GET RL
	Rl = Pl(R)
	#RUN PL ON ZERO VECTOR TO GET pll 
	pll = Pl(zero, False)
	#FINISH DEFINinG RL 
	Rl -= (int(pll) * PubKey)
	R.append(Rl)

	#GENERATE ML AND CL WITH RL
	Ml = _sage_const_335298040 
	Cl = hash(encode(Rl), Ml)


	P2 = []
	for i in range(_sage_const_0 , _sage_const_2 **w):
		P2.append(R[k2+i])

	#RUN KLIST
	(Y, s, auxk2l) = kListHROS(w, math.ceil(L), P2)
	print(Y)

	#CONVERT ??? INTO BINARY FOR 0-k2 C's
	smt = s + midTerm
	B = convertBinary(smt)

	#CHOOSE C's
	C = []
	for i in range(_sage_const_0 ,k2):
		C.append(CB[i][int(B[i])])

	#APPEND Y's from KLIST
	for i in range(k2, l):
		C.append(Y[i-k2])

	#IF Klist was used CL = Yl
	if (k2 < l):
		Cl = Y[l-k2]


	#RUN SIGN0 for 0-l SIGS WITH C's
	for i in range(_sage_const_0 , l):
		si = K[i] + IntPrime(PrivKey) * IntPrime(C[i])
		S.append(si)

	#RUN PL on S to get Sl
	Sl = Pl(S, False)


	for i in range(_sage_const_0 ,l):
		print(((int(S[i]) * G) - (int(C[i]) * PubKey)) == R[i])
	print(((int(Sl) * G) - (int(Cl) * PubKey)) == Rl)


	print("1 = "+str(Rl))
	print("2 = "+str(Pl(R) - ))
	print("2 = "+str(int(Sl) * G - int(Cl) * PubKey))


print(main())