path: root/tdutils/td/utils/unicode.cpp

//
// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2026
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
#include "td/utils/unicode.h"

#include "td/utils/logging.h"

namespace td {

// list of [(range_begin << 5) + range_type]
static const uint32 unicode_simple_category_ranges[] = {
    0,       1028,    1056,    1538,    1856,    2081,    2912,      3105,    3936,    5124,    5152,    5441,
    5472,    5699,    5760,    5793,    5824,    5923,    5953,      5984,    6019,    6112,    6145,    6880,
    6913,    7904,    7937,    22592,   22721,   23104,   23553,     23712,   23937,   23968,   24001,   24032,
    28161,   28320,   28353,   28416,   28481,   28608,   28641,     28672,   28865,   28896,   28929,   29024,
    29057,   29088,   29121,   29760,   29793,   32448,   32481,     36928,   37185,   42496,   42529,   43744,
    43809,   43840,   44033,   45344,   47617,   48480,   48609,     48736,   50177,   51552,   52226,   52544,
    52673,   52736,   52769,   55936,   55969,   56000,   56481,     56544,   56769,   56834,   57153,   57248,
    57313,   57344,   57857,   57888,   57921,   58880,   59809,     62656,   63009,   63040,   63490,   63809,
    64864,   65153,   65216,   65345,   65376,   65537,   66240,     66369,   66400,   66689,   66720,   66817,
    66848,   67585,   68384,   68609,   68960,   69121,   69888,     69921,   70112,   70657,   72000,   73857,
    75584,   75681,   75712,   76289,   76320,   76545,   76864,     76994,   77312,   77345,   77856,   77985,
    78240,   78305,   78368,   78433,   79136,   79169,   79392,     79425,   79456,   79553,   79680,   79777,
    79808,   80321,   80352,   80769,   80832,   80865,   80960,     81090,   81409,   81472,   81539,   81728,
    81793,   81824,   82081,   82272,   82401,   82464,   82529,     83232,   83265,   83488,   83521,   83584,
    83617,   83680,   83713,   83776,   84769,   84896,   84929,     84960,   85186,   85504,   85569,   85664,
    86177,   86464,   86497,   86592,   86625,   87328,   87361,     87584,   87617,   87680,   87713,   87872,
    87969,   88000,   88577,   88608,   89089,   89152,   89282,     89600,   89889,   89920,   90273,   90528,
    90593,   90656,   90721,   91424,   91457,   91680,   91713,     91776,   91809,   91968,   92065,   92096,
    93057,   93120,   93153,   93248,   93378,   93696,   93729,     93763,   93952,   94305,   94336,   94369,
    94560,   94657,   94752,   94785,   94912,   95009,   95072,     95105,   95136,   95169,   95232,   95329,
    95392,   95489,   95584,   95681,   96064,   96769,   96800,     97474,   97795,   97888,   98465,   98720,
    98753,   98848,   98881,   99616,   99649,   100160,  100257,    100288,  101121,  101216,  101281,  101312,
    101377,  101440,  101570,  101888,  102147,  102368,  102401,    102432,  102561,  102816,  102849,  102944,
    102977,  103712,  103745,  104064,  104097,  104256,  104353,    104384,  105377,  105440,  105473,  105536,
    105666,  105984,  106017,  106080,  106625,  106912,  106945,    107040,  107073,  108384,  108449,  108480,
    108993,  109024,  109185,  109280,  109315,  109537,  109632,    109762,  110083,  110368,  110401,  110592,
    110753,  111328,  111425,  112192,  112225,  112512,  112545,    112576,  112641,  112864,  113858,  114176,
    114721,  116256,  116289,  116352,  116737,  116960,  117250,    117568,  118817,  118880,  118913,  118944,
    118977,  119136,  119169,  119936,  119969,  120000,  120033,    120352,  120385,  120448,  120737,  120768,
    120833,  120992,  121025,  121056,  121346,  121664,  121729,    121856,  122881,  122912,  123906,  124227,
    124544,  124929,  125184,  125217,  126368,  127233,  127392,    131073,  132448,  133089,  133122,  133440,
    133633,  133824,  133953,  134080,  134177,  134208,  134305,    134368,  134593,  134688,  134817,  135232,
    135617,  135648,  135682,  136000,  136193,  137408,  137441,    137472,  137633,  137664,  137729,  139104,
    139137,  149792,  149825,  149952,  150017,  150240,  150273,    150304,  150337,  150464,  150529,  151840,
    151873,  152000,  152065,  153120,  153153,  153280,  153345,    153568,  153601,  153632,  153665,  153792,
    153857,  154336,  154369,  156192,  156225,  156352,  156417,    158560,  159011,  159648,  159745,  160256,
    160769,  163520,  163585,  163776,  163873,  183712,  183777,    184324,  184353,  185184,  185345,  187744,
    187843,  187937,  188192,  188417,  188992,  189409,  190016,    190465,  191040,  191489,  191904,  191937,
    192032,  192513,  194176,  195297,  195328,  195457,  195488,    195586,  195904,  196099,  196416,  197122,
    197440,  197633,  200480,  200705,  200864,  200929,  202016,    202049,  202080,  202241,  204480,  204801,
    205792,  207042,  207361,  208320,  208385,  208544,  208897,    210304,  210433,  211264,  211458,  211779,
    211808,  212993,  213728,  214017,  215712,  217090,  217408,    217602,  217920,  218337,  218368,  221345,
    222848,  223393,  223648,  223746,  224064,  225377,  226336,    226753,  226818,  227137,  228544,  229377,
    230528,  231426,  231744,  231841,  231938,  232257,  233408,    233473,  233824,  233985,  235360,  235425,
    235520,  236833,  236960,  236993,  237184,  237217,  237280,    237377,  237408,  237569,  243712,  245761,
    254656,  254721,  254912,  254977,  256192,  256257,  256448,    256513,  256768,  256801,  256832,  256865,
    256896,  256929,  256960,  256993,  257984,  258049,  259744,    259777,  260000,  260033,  260064,  260161,
    260256,  260289,  260512,  260609,  260736,  260801,  260992,    261121,  261536,  261697,  261792,  261825,
    262048,  262148,  262496,  263428,  263488,  263652,  263680,    265188,  265216,  265731,  265761,  265792,
    265859,  266048,  266209,  266243,  266560,  266753,  267168,    270401,  270432,  270561,  270592,  270657,
    270976,  271009,  271040,  271137,  271296,  271489,  271520,    271553,  271584,  271617,  271648,  271681,
    271808,  271841,  272192,  272257,  272384,  272545,  272704,    272833,  272864,  272899,  274529,  274595,
    274752,  297987,  299904,  302403,  303104,  323267,  324224,    360449,  367776,  367969,  368096,  368193,
    368256,  368547,  368576,  368641,  369856,  369889,  369920,    370081,  370112,  370177,  371968,  372193,
    372224,  372737,  373472,  373761,  373984,  374017,  374240,    374273,  374496,  374529,  374752,  374785,
    375008,  375041,  375264,  375297,  375520,  375553,  375776,    378337,  378368,  393220,  393248,  393377,
    393443,  393472,  394275,  394560,  394785,  394944,  395011,    395105,  395168,  395297,  398048,  398241,
    398336,  398369,  401248,  401281,  401408,  401569,  402944,    402977,  405984,  406083,  406208,  406529,
    407552,  409089,  409600,  410627,  410944,  411907,  412160,    412195,  412672,  413699,  414016,  415267,
    415744,  425985,  636928,  638977,  1348000, 1350145, 1351616,   1351681, 1360288, 1360385, 1360898, 1361217,
    1361280, 1361921, 1363424, 1363937, 1364928, 1364993, 1367235,   1367552, 1368801, 1369088, 1369153, 1372448,
    1372513, 1374656, 1374721, 1374784, 1374817, 1374848, 1374881,   1375136, 1375809, 1376320, 1376353, 1376448,
    1376481, 1376608, 1376641, 1377376, 1377795, 1377984, 1378305,   1379968, 1380417, 1382016, 1382914, 1383232,
    1384001, 1384192, 1384289, 1384320, 1384353, 1384416, 1384450,   1384769, 1385664, 1385985, 1386720, 1387521,
    1388448, 1388673, 1390176, 1391073, 1391106, 1391424, 1391617,   1391776, 1391809, 1392130, 1392449, 1392608,
    1392641, 1393952, 1394689, 1394784, 1394817, 1395072, 1395202,   1395520, 1395713, 1396448, 1396545, 1396576,
    1396673, 1398272, 1398305, 1398336, 1398433, 1398496, 1398561,   1398720, 1398785, 1398816, 1398849, 1398880,
    1399649, 1399744, 1399809, 1400160, 1400385, 1400480, 1400865,   1401056, 1401121, 1401312, 1401377, 1401568,
    1401857, 1402080, 1402113, 1402336, 1402369, 1403744, 1403777,   1404224, 1404417, 1408096, 1408514, 1408832,
    1409025, 1766528, 1766913, 1767648, 1767777, 1769344, 2039809,   2051520, 2051585, 2054976, 2056193, 2056416,
    2056801, 2056960, 2057121, 2057152, 2057185, 2057504, 2057537,   2057952, 2057985, 2058144, 2058177, 2058208,
    2058241, 2058304, 2058337, 2058400, 2058433, 2061888, 2062945,   2074560, 2075137, 2077184, 2077249, 2078976,
    2080257, 2080640, 2084353, 2084512, 2084545, 2088864, 2089474,   2089792, 2090017, 2090848, 2091041, 2091872,
    2092225, 2095072, 2095169, 2095360, 2095425, 2095616, 2095681,   2095872, 2095937, 2096032, 2097153, 2097536,
    2097569, 2098400, 2098433, 2099040, 2099073, 2099136, 2099169,   2099648, 2099713, 2100160, 2101249, 2105184,
    2105571, 2107008, 2107395, 2109216, 2109763, 2109824, 2117633,   2118560, 2118657, 2120224, 2120739, 2121600,
    2121729, 2122755, 2122880, 2123169, 2123811, 2123841, 2124099,   2124128, 2124289, 2125504, 2125825, 2126784,
    2126849, 2128000, 2128129, 2128384, 2128419, 2128576, 2129921,   2134976, 2135042, 2135360, 2135553, 2136704,
    2136833, 2137984, 2138113, 2139392, 2139649, 2141312, 2141697,   2142048, 2142081, 2142560, 2142593, 2142816,
    2142849, 2142912, 2142945, 2143296, 2143329, 2143808, 2143841,   2144064, 2144097, 2144160, 2144257, 2145920,
    2146305, 2156256, 2156545, 2157248, 2157569, 2157824, 2158593,   2158784, 2158817, 2160160, 2160193, 2160480,
    2162689, 2162880, 2162945, 2162976, 2163009, 2164416, 2164449,   2164512, 2164609, 2164640, 2164705, 2165440,
    2165507, 2165761, 2166496, 2166563, 2166785, 2167776, 2168035,   2168320, 2169857, 2170464, 2170497, 2170560,
    2170723, 2170881, 2171587, 2171776, 2171905, 2172736, 2174977,   2176768, 2176899, 2176961, 2177027, 2177536,
    2177603, 2179073, 2179104, 2179585, 2179712, 2179745, 2179840,   2179873, 2180800, 2181123, 2181408, 2182145,
    2183075, 2183136, 2183169, 2184099, 2184192, 2185217, 2185472,   2185505, 2186400, 2186595, 2186752, 2187265,
    2188992, 2189313, 2190016, 2190083, 2190337, 2190944, 2191107,   2191361, 2191936, 2192675, 2192896, 2195457,
    2197792, 2199553, 2201184, 2201601, 2203232, 2203459, 2203649,   2204800, 2205186, 2205504, 2205698, 2206017,
    2206912, 2207201, 2207936, 2214915, 2215904, 2215937, 2217280,   2217473, 2217536, 2218049, 2218144, 2220033,
    2220963, 2221281, 2221312, 2221569, 2222272, 2222627, 2222752,   2223617, 2224192, 2225665, 2226339, 2226560,
    2227201, 2227936, 2228321, 2230016, 2230851, 2231490, 2231808,   2231841, 2231904, 2231969, 2232000, 2232417,
    2233856, 2234881, 2235680, 2235906, 2236224, 2236513, 2237664,   2238146, 2238464, 2238593, 2238624, 2238689,
    2238720, 2238977, 2240096, 2240193, 2240224, 2240609, 2242144,   2242593, 2242720, 2243074, 2243393, 2243424,
    2243457, 2243488, 2243619, 2244256, 2244609, 2245184, 2245217,   2246016, 2246625, 2246688, 2248705, 2248928,
    2248961, 2248992, 2249025, 2249152, 2249185, 2249664, 2249697,   2250016, 2250241, 2251744, 2252290, 2252608,
    2252961, 2253216, 2253281, 2253344, 2253409, 2254112, 2254145,   2254368, 2254401, 2254464, 2254497, 2254656,
    2254753, 2254784, 2255361, 2255392, 2255777, 2255936, 2256897,   2257216, 2257249, 2257280, 2257345, 2257376,
    2257409, 2258624, 2258657, 2258688, 2259489, 2259520, 2259553,   2259584, 2260993, 2262688, 2263265, 2263392,
    2263554, 2263872, 2264033, 2264128, 2265089, 2266624, 2267265,   2267328, 2267361, 2267392, 2267650, 2267968,
    2273281, 2274784, 2276097, 2276224, 2277377, 2278912, 2279553,   2279584, 2279938, 2280256, 2281473, 2282848,
    2283265, 2283296, 2283522, 2283840, 2284034, 2284672, 2285569,   2286432, 2287106, 2287427, 2287488, 2287617,
    2287840, 2293761, 2295168, 2298881, 2300930, 2301251, 2301536,   2301921, 2302176, 2302241, 2302272, 2302337,
    2302592, 2302625, 2302688, 2302721, 2303488, 2303969, 2304000,   2304033, 2304064, 2304514, 2304832, 2307073,
    2307328, 2307393, 2308640, 2309153, 2309184, 2309217, 2309248,   2310145, 2310176, 2310497, 2311776, 2312001,
    2312032, 2312705, 2312736, 2313089, 2314560, 2315169, 2315200,   2315777, 2318112, 2324481, 2325536, 2326018,
    2326336, 2326529, 2326816, 2326849, 2328032, 2328577, 2328608,   2329090, 2329411, 2330016, 2330177, 2331136,
    2334721, 2334944, 2334977, 2335040, 2335073, 2336288, 2336961,   2336992, 2337282, 2337600, 2337793, 2337984,
    2338017, 2338080, 2338113, 2339136, 2339585, 2339616, 2339842,   2340160, 2350081, 2350688, 2351169, 2351200,
    2351233, 2351648, 2351681, 2352768, 2353666, 2353984, 2356737,   2356768, 2357251, 2357920, 2359297, 2388800,
    2392067, 2395616, 2396161, 2402432, 2486785, 2489888, 2490369,   2524672, 2525217, 2525408, 2526209, 2654048,
    2654209, 2672864, 2891777, 2892736, 2893314, 2893632, 2949121,   2967328, 2967553, 2968544, 2968578, 2968896,
    2969089, 2971616, 2971650, 2971968, 2972161, 2973120, 2973697,   2975232, 2975745, 2975872, 2976258, 2976576,
    2976611, 2976832, 2976865, 2977536, 2977697, 2978304, 2992129,   2993568, 2993666, 2993984, 3000321, 3002371,
    3003104, 3006465, 3008864, 3009025, 3009056, 3011169, 3011584,   3013633, 3013696, 3013729, 3013760, 3014657,
    3211008, 3211265, 3250880, 3252193, 3252512, 3538433, 3538560,   3538593, 3538816, 3538849, 3538912, 3538945,
    3548256, 3548737, 3548768, 3549697, 3549792, 3549857, 3549888,   3550337, 3550464, 3550721, 3563392, 3637249,
    3640672, 3640833, 3641248, 3641345, 3641632, 3641857, 3642176,   3776002, 3776320, 3823619, 3824256, 3824643,
    3825280, 3828739, 3829536, 3833857, 3836576, 3836609, 3838880,   3838913, 3838976, 3839041, 3839072, 3839137,
    3839200, 3839265, 3839392, 3839425, 3839808, 3839841, 3839872,   3839905, 3840128, 3840161, 3842240, 3842273,
    3842400, 3842465, 3842720, 3842753, 3842976, 3843009, 3843904,   3843937, 3844064, 3844097, 3844256, 3844289,
    3844320, 3844417, 3844640, 3844673, 3855552, 3855617, 3856416,   3856449, 3857248, 3857281, 3858272, 3858305,
    3859104, 3859137, 3860128, 3860161, 3860960, 3860993, 3861984,   3862017, 3862816, 3862849, 3863840, 3863873,
    3864672, 3864705, 3864960, 3865026, 3866624, 3923969, 3924960,   3925153, 3925344, 3933697, 3935680, 3940353,
    3941792, 3942113, 3942336, 3942402, 3942720, 3942849, 3942880,   3953153, 3954112, 3954689, 3956096, 3956226,
    3956544, 3971585, 3972480, 3972610, 3972928, 3979777, 3980736,   3980801, 3980834, 3981152, 3996673, 3996896,
    3996929, 3997056, 3997089, 3997152, 3997185, 3997664, 3997697,   4004000, 4004067, 4004352, 4005889, 4008064,
    4008289, 4008320, 4008450, 4008768, 4034083, 4035968, 4036003,   4036096, 4036131, 4036256, 4038691, 4040128,
    4040163, 4040640, 4046849, 4046976, 4047009, 4047872, 4047905,   4047968, 4048001, 4048032, 4048097, 4048128,
    4048161, 4048480, 4048513, 4048640, 4048673, 4048704, 4048737,   4048768, 4048961, 4048992, 4049121, 4049152,
    4049185, 4049216, 4049249, 4049280, 4049313, 4049408, 4049441,   4049504, 4049537, 4049568, 4049633, 4049664,
    4049697, 4049728, 4049761, 4049792, 4049825, 4049856, 4049889,   4049920, 4049953, 4050016, 4050049, 4050080,
    4050145, 4050272, 4050305, 4050528, 4050561, 4050688, 4050721,   4050848, 4050881, 4050912, 4050945, 4051264,
    4051297, 4051840, 4052001, 4052096, 4052129, 4052288, 4052321,   4052864, 4071427, 4071840, 4161026, 4161344,
    4194305, 5561344, 5562369, 5695296, 5695489, 5702592, 5702657,   5887040, 5887489, 6126624, 6127105, 6147008,
    6225921, 6243264, 6291457, 6449504, 6449665, 6583808, 4294967295};

static const uint16 unicode_simple_category_jump_pos[] = {
    1,    9,    27,   27,   27,   27,   36,   44,   55,   55,   57,   63,   68,   75,   86,   91,   102,  114,  119,
    130,  158,  180,  202,  225,  250,  271,  292,  312,  324,  332,  357,  365,  368,  383,  397,  397,  397,  407,
    423,  431,  436,  437,  437,  437,  437,  440,  448,  458,  467,  472,  480,  487,  494,  498,  503,  509,  516,
    524,  538,  538,  540,  540,  540,  558,  578,  592,  595,  622,  625,  625,  625,  625,  625,  626,  629,  629,
    629,  629,  629,  630,  631,  631,  631,  631,  631,  631,  631,  631,  632,  632,  640,  650,  667,  669,  669,
    669,  670,  682,  689,  692,  699,  706,  709,  709,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,
    710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,
    710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,  710,
    710,  710,  710,  710,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,  712,
    712,  712,  712,  712,  712,  712,  712,  716,  716,  716,  724,  728,  731,  741,  752,  763,  769,  781,  793,
    810,  825,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,
    829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,
    829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,
    829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,
    829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  829,  834,  834,  834,  834,  834,
    834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,
    834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,
    834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,  834,
    834,  834,  834,  834,  835,  835,  835,  837,  839,  857,  859,  859,  859,  861,  866,  869,  870,  877,  887,
    899,  900,  904,  906,  907,  913,  923,  931,  931,  939,  945,  961,  961,  961,  967,  973,  989,  998,  1003,
    1010, 1023, 1032, 1040, 1044, 1046, 1051, 1058, 1059, 1062, 1068, 1076, 1082, 1091, 1097, 1109, 1121, 1127, 1140,
    1159, 1173, 1181, 1188, 1189, 1193, 1199, 1207, 1213, 1214, 1215, 1220, 1235, 1244, 1252, 1257, 1257, 1262, 1271,
    1273, 1287, 1292, 1292, 1294, 1302, 1307, 1307, 1307, 1307, 1307, 1307, 1307, 1307, 1309, 1311, 1311, 1312, 1312,
    1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312, 1312,
    1315, 1315, 1315, 1315, 1315, 1315, 1315, 1315, 1315, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319,
    1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319, 1319,
    1319, 1319, 1321, 1321, 1321, 1321, 1321, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322,
    1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322,
    1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322, 1322,
    1322, 1322, 1322, 1323, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1326, 1327, 1327,
    1327, 1327, 1327, 1333, 1339, 1349, 1350, 1350, 1350, 1354, 1354, 1356, 1358, 1361, 1368, 1368, 1368, 1368, 1368,
    1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368,
    1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368, 1368,
    1368, 1368, 1368, 1368, 1368, 1370, 1370, 1370, 1370, 1370, 1370, 1370, 1370, 1370, 1370, 1372, 1373, 1373, 1373,
    1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373,
    1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373,
    1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373,
    1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1373, 1380, 1380, 1380, 1390, 1390, 1390, 1391, 1391, 1391, 1391,
    1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1391, 1392, 1396, 1399, 1399, 1399,
    1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399,
    1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1399, 1401, 1401, 1401, 1401, 1401, 1401, 1401, 1401, 1401,
    1401, 1401, 1401, 1405, 1407, 1408, 1410, 1426, 1444, 1444, 1444, 1452, 1460, 1469, 1469, 1469, 1469, 1469, 1469,
    1469, 1469, 1469, 1469, 1469, 1469, 1469, 1469, 1470, 1473, 1473, 1475, 1476, 1483, 1483, 1483, 1489, 1489, 1489,
    1489, 1493, 1493, 1498, 1498, 1498, 1498, 1507, 1507, 1511, 1516, 1516, 1516, 1516, 1516, 1516, 1517, 1522, 1526,
    1527, 1583, 1592, 1592, 1592, 1592, 1593, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594,
    1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1594, 1596, 1596, 1596, 1596, 1596, 1596, 1596, 1596, 1597, 1611,
    1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614, 1614};

static const char *unicode_simple_category_table =
    "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
    "\x00\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x02\x02\x02\x02\x02\x02\x02"
    "\x02\x02\x00\x00\x00\x00\x00\x00\x00\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
    "\x01\x01\x01\x01\x01\x01\x01\x00\x00\x00\x00\x00\x00\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01"
    "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x00\x00\x00\x00\x00";

static constexpr uint32 TABLE_SIZE = 1280;

static const int16 prepare_search_character_table[TABLE_SIZE] = {
    0,     32,   32,   32,   32,    32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,
    32,    32,   32,   32,   32,    32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,
    32,    32,   32,   32,   32,    32,   32,   32,   32,   32,   48,   49,   50,   51,   52,   53,   54,   55,   56,
    57,    32,   32,   32,   32,    32,   32,   32,   97,   98,   99,   100,  101,  102,  103,  104,  105,  106,  107,
    108,   109,  110,  111,  112,   113,  114,  115,  116,  117,  118,  119,  120,  121,  122,  32,   32,   32,   32,
    32,    32,   97,   98,   99,    100,  101,  102,  103,  104,  105,  106,  107,  108,  109,  110,  111,  112,  113,
    114,   115,  116,  117,  118,   119,  120,  121,  122,  32,   32,   32,   32,   32,   32,   32,   32,   32,   32,
    32,    32,   32,   32,   32,    32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,
    32,    32,   32,   32,   32,    32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   32,   170,
    32,    32,   0,    32,   32,    32,   32,   178,  179,  32,   956,  32,   0,    32,   185,  186,  32,   188,  189,
    190,   32,   224,  225,  226,   227,  228,  229,  230,  231,  232,  233,  234,  235,  236,  237,  238,  239,  240,
    241,   242,  243,  244,  245,   246,  32,   248,  249,  250,  251,  252,  253,  254,  223,  224,  225,  226,  227,
    228,   229,  230,  231,  232,   233,  234,  235,  236,  237,  238,  239,  240,  241,  242,  243,  244,  245,  246,
    32,    248,  249,  250,  251,   252,  253,  254,  255,  257,  257,  259,  259,  261,  261,  263,  263,  265,  265,
    267,   267,  269,  269,  271,   271,  273,  273,  275,  275,  277,  277,  279,  279,  281,  281,  283,  283,  285,
    285,   287,  287,  289,  289,   291,  291,  293,  293,  295,  295,  297,  297,  299,  299,  301,  301,  303,  303,
    105,   305,  307,  307,  309,   309,  311,  311,  312,  314,  314,  316,  316,  318,  318,  320,  320,  322,  322,
    324,   324,  326,  326,  328,   328,  329,  331,  331,  333,  333,  335,  335,  337,  337,  339,  339,  341,  341,
    343,   343,  345,  345,  347,   347,  349,  349,  351,  351,  353,  353,  355,  355,  357,  357,  359,  359,  361,
    361,   363,  363,  365,  365,   367,  367,  369,  369,  371,  371,  373,  373,  375,  375,  255,  378,  378,  380,
    380,   382,  382,  115,  384,   595,  387,  387,  389,  389,  596,  392,  392,  598,  599,  396,  396,  397,  477,
    601,   603,  402,  402,  608,   611,  405,  617,  616,  409,  409,  410,  411,  623,  626,  414,  629,  417,  417,
    419,   419,  421,  421,  640,   424,  424,  643,  426,  427,  429,  429,  648,  432,  432,  650,  651,  436,  436,
    438,   438,  658,  441,  441,   442,  443,  445,  445,  446,  447,  448,  449,  450,  451,  454,  454,  454,  457,
    457,   457,  460,  460,  460,   462,  462,  464,  464,  466,  466,  468,  468,  470,  470,  472,  472,  474,  474,
    476,   476,  477,  479,  479,   481,  481,  483,  483,  485,  485,  487,  487,  489,  489,  491,  491,  493,  493,
    495,   495,  496,  499,  499,   499,  501,  501,  405,  447,  505,  505,  507,  507,  509,  509,  511,  511,  513,
    513,   515,  515,  517,  517,   519,  519,  521,  521,  523,  523,  525,  525,  527,  527,  529,  529,  531,  531,
    533,   533,  535,  535,  537,   537,  539,  539,  541,  541,  543,  543,  414,  545,  547,  547,  549,  549,  551,
    551,   553,  553,  555,  555,   557,  557,  559,  559,  561,  561,  563,  563,  564,  565,  566,  567,  568,  569,
    11365, 572,  572,  410,  11366, 575,  576,  578,  578,  384,  649,  652,  583,  583,  585,  585,  587,  587,  589,
    589,   591,  591,  592,  593,   594,  595,  596,  597,  598,  599,  600,  601,  602,  603,  604,  605,  606,  607,
    608,   609,  610,  611,  612,   613,  614,  615,  616,  617,  618,  619,  620,  621,  622,  623,  624,  625,  626,
    627,   628,  629,  630,  631,   632,  633,  634,  635,  636,  637,  638,  639,  640,  641,  642,  643,  644,  645,
    646,   647,  648,  649,  650,   651,  652,  653,  654,  655,  656,  657,  658,  659,  660,  661,  662,  663,  664,
    665,   666,  667,  668,  669,   670,  671,  672,  673,  674,  675,  676,  677,  678,  679,  680,  681,  682,  683,
    684,   685,  686,  687,  688,   689,  690,  691,  692,  693,  694,  695,  696,  697,  698,  699,  0,    701,  0,
    703,   704,  705,  32,   32,    32,   32,   710,  711,  712,  713,  714,  715,  716,  717,  718,  719,  720,  721,
    32,    32,   32,   32,   32,    32,   32,   32,   32,   32,   32,   32,   32,   32,   736,  737,  738,  739,  740,
    32,    32,   32,   32,   32,    32,   32,   748,  32,   750,  32,   32,   32,   32,   32,   32,   32,   32,   32,
    32,    32,   32,   32,   32,    32,   32,   32,   0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,     0,    0,    0,    0,     0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,     0,    0,    0,    0,     0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,     0,    0,    0,    0,     0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,     837,  0,    0,    0,     0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,     0,    0,    0,    0,     0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,     0,    0,    0,    0,     0,    881,  881,  883,  883,  884,  32,   887,  887,  888,  889,  890,  891,  892,
    893,   32,   1011, 896,  897,   898,  899,  32,   32,   940,  32,   941,  942,  943,  907,  972,  909,  973,  974,
    912,   945,  946,  947,  948,   949,  950,  951,  952,  953,  954,  955,  956,  957,  958,  959,  960,  961,  930,
    963,   964,  965,  966,  967,   968,  969,  970,  971,  940,  941,  942,  943,  944,  945,  946,  947,  948,  949,
    950,   951,  952,  953,  954,   955,  956,  957,  958,  959,  960,  961,  963,  963,  964,  965,  966,  967,  968,
    969,   970,  971,  972,  973,   974,  983,  946,  952,  965,  965,  965,  966,  960,  983,  985,  985,  987,  987,
    989,   989,  991,  991,  993,   993,  995,  995,  997,  997,  999,  999,  1001, 1001, 1003, 1003, 1005, 1005, 1007,
    1007,  954,  961,  963,  1011,  952,  949,  32,   1016, 1016, 1010, 1019, 1019, 1020, 891,  892,  893,  1104, 1105,
    1106,  1107, 1108, 1109, 1110,  1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1072, 1073, 1074, 1075, 1076,
    1077,  1078, 1079, 1080, 1081,  1082, 1083, 1084, 1085, 1086, 1087, 1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095,
    1096,  1097, 1098, 1099, 1100,  1101, 1102, 1103, 1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1081, 1082,
    1083,  1084, 1085, 1086, 1087,  1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099, 1100, 1101,
    1102,  1103, 1104, 1105, 1106,  1107, 1108, 1109, 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1121,
    1121,  1123, 1123, 1125, 1125,  1127, 1127, 1129, 1129, 1131, 1131, 1133, 1133, 1135, 1135, 1137, 1137, 1139, 1139,
    1141,  1141, 1143, 1143, 1145,  1145, 1147, 1147, 1149, 1149, 1151, 1151, 1153, 1153, 32,   0,    0,    0,    0,
    0,     0,    0,    1163, 1163,  1165, 1165, 1167, 1167, 1169, 1169, 1171, 1171, 1173, 1173, 1175, 1175, 1177, 1177,
    1179,  1179, 1181, 1181, 1183,  1183, 1185, 1185, 1187, 1187, 1189, 1189, 1191, 1191, 1193, 1193, 1195, 1195, 1197,
    1197,  1199, 1199, 1201, 1201,  1203, 1203, 1205, 1205, 1207, 1207, 1209, 1209, 1211, 1211, 1213, 1213, 1215, 1215,
    1231,  1218, 1218, 1220, 1220,  1222, 1222, 1224, 1224, 1226, 1226, 1228, 1228, 1230, 1230, 1231, 1233, 1233, 1235,
    1235,  1237, 1237, 1239, 1239,  1241, 1241, 1243, 1243, 1245, 1245, 1247, 1247, 1249, 1249, 1251, 1251, 1253, 1253,
    1255,  1255, 1257, 1257, 1259,  1259, 1261, 1261, 1263, 1263, 1265, 1265, 1267, 1267, 1269, 1269, 1271, 1271, 1273,
    1273,  1275, 1275, 1277, 1277,  1279, 1279};

static const int32 prepare_search_character_ranges[] = {
    1280,   2097153, 1328,   1328,    1329,    -1378,   1367,    -1368,    1370,    32,      1376,       -1377,
    1417,   32,      1419,   -1420,   1421,    32,      1424,    1424,     1425,    0,       1470,       32,
    1471,   0,       1472,   32,      1473,    0,       1475,    32,       1476,    0,       1478,       32,
    1479,   0,       1480,   -1481,   1523,    32,      1525,    -1526,    1536,    0,       1542,       32,
    1552,   0,       1563,   32,      1564,    0,       1565,    32,       1568,    -1569,   1611,       0,
    1632,   -1633,   1642,   32,      1646,    -1647,   1648,    0,        1649,    -1650,   1748,       32,
    1749,   1749,    1750,   0,       1758,    32,      1759,    0,        1765,    -1766,   1767,       0,
    1769,   32,      1770,   0,       1774,    -1775,   1789,    32,       1791,    1791,    1792,       32,
    1806,   1806,    1807,   0,       1808,    1808,    1809,    0,        1810,    -1811,   1840,       0,
    1867,   -1868,   1958,   0,       1969,    -1970,   2027,    0,        2036,    -2037,   2038,       32,
    2042,   -2043,   2045,   0,       2046,    32,      2048,    -2049,    2070,    0,       2074,       2074,
    2075,   0,       2084,   2084,    2085,    0,       2088,    2088,     2089,    0,       2094,       -2095,
    2096,   32,      2111,   -2112,   2137,    0,       2140,    -2141,    2142,    32,      2143,       -2144,
    2184,   32,      2185,   -2186,   2192,    0,       2194,    -2195,    2199,    0,       2208,       -2209,
    2250,   0,       2308,   -2309,   2362,    0,       2365,    2365,     2366,    0,       2384,       2384,
    2385,   0,       2392,   -2393,   2402,    0,       2404,    32,       2406,    -2407,   2416,       32,
    2417,   -2418,   2433,   0,       2436,    -2437,   2492,    0,        2493,    2493,    2494,       0,
    2501,   -2502,   2503,   0,       2505,    -2506,   2507,    0,        2510,    -2511,   2519,       0,
    2520,   -2521,   2530,   0,       2532,    -2533,   2546,    32,       2548,    -2549,   2554,       32,
    2556,   2556,    2557,   32,      2558,    0,       2559,    -2560,    2561,    0,       2564,       -2565,
    2620,   0,       2621,   2621,    2622,    0,       2627,    -2628,    2631,    0,       2633,       -2634,
    2635,   0,       2638,   -2639,   2641,    0,       2642,    -2643,    2672,    0,       2674,       -2675,
    2677,   0,       2678,   32,      2679,    -2680,   2689,    0,        2692,    -2693,   2748,       0,
    2749,   2749,    2750,   0,       2758,    2758,    2759,    0,        2762,    2762,    2763,       0,
    2766,   -2767,   2786,   0,       2788,    -2789,   2800,    32,       2802,    -2803,   2810,       0,
    2816,   2816,    2817,   0,       2820,    -2821,   2876,    0,        2877,    2877,    2878,       0,
    2885,   -2886,   2887,   0,       2889,    -2890,   2891,    0,        2894,    -2895,   2901,       0,
    2904,   -2905,   2914,   0,       2916,    -2917,   2928,    32,       2929,    -2930,   2946,       0,
    2947,   -2948,   3006,   0,       3011,    -3012,   3014,    0,        3017,    3017,    3018,       0,
    3022,   -3023,   3031,   0,       3032,    -3033,   3059,    32,       3067,    -3068,   3072,       0,
    3077,   -3078,   3132,   0,       3133,    3133,    3134,    0,        3141,    3141,    3142,       0,
    3145,   3145,    3146,   0,       3150,    -3151,   3157,    0,        3159,    -3160,   3170,       0,
    3172,   -3173,   3191,   32,      3192,    -3193,   3199,    32,       3200,    3200,    3201,       0,
    3204,   32,      3205,   -3206,   3260,    0,       3261,    3261,     3262,    0,       3269,       3269,
    3270,   0,       3273,   3273,    3274,    0,       3278,    -3279,    3285,    0,       3287,       -3288,
    3298,   0,       3300,   -3301,   3315,    0,       3316,    -3317,    3328,    0,       3332,       -3333,
    3387,   0,       3389,   3389,    3390,    0,       3397,    3397,     3398,    0,       3401,       3401,
    3402,   0,       3406,   3406,    3407,    32,      3408,    -3409,    3415,    0,       3416,       -3417,
    3426,   0,       3428,   -3429,   3449,    32,      3450,    -3451,    3457,    0,       3460,       -3461,
    3530,   0,       3531,   -3532,   3535,    0,       3541,    3541,     3542,    0,       3543,       3543,
    3544,   0,       3552,   -3553,   3570,    0,       3572,    32,       3573,    -3574,   3633,       0,
    3634,   -3635,   3636,   0,       3643,    -3644,   3647,    32,       3648,    -3649,   3655,       0,
    3663,   32,      3664,   -3665,   3674,    32,      3676,    -3677,    3761,    0,       3762,       -3763,
    3764,   0,       3773,   -3774,   3784,    0,       3791,    -3792,    3841,    32,      3864,       0,
    3866,   32,      3872,   -3873,   3892,    32,      3893,    0,        3894,    32,      3895,       0,
    3896,   32,      3897,   0,       3898,    32,      3902,    0,        3904,    -3905,   3953,       0,
    3973,   32,      3974,   0,       3976,    -3977,   3981,    0,        3992,    3992,    3993,       0,
    4029,   4029,    4030,   32,      4038,    0,       4039,    32,       4045,    4045,    4046,       32,
    4059,   -4060,   4139,   0,       4159,    -4160,   4170,    32,       4176,    -4177,   4182,       0,
    4186,   -4187,   4190,   0,       4193,    4193,    4194,    0,        4197,    -4198,   4199,       0,
    4206,   -4207,   4209,   0,       4213,    -4214,   4226,    0,        4238,    4238,    4239,       0,
    4240,   -4241,   4250,   0,       4254,    32,      4256,    -11521,   4294,    4294,    4295,       11559,
    4296,   -4297,   4301,   11565,   4302,    -4303,   4347,    32,       4348,    -4349,   4957,       0,
    4960,   32,      4969,   -4970,   5008,    32,      5018,    -5019,    5112,    -5105,   5118,       -5119,
    5120,   32,      5121,   -5122,   5741,    32,      5743,    -5744,    5760,    32,      5761,       -5762,
    5787,   32,      5789,   -5790,   5867,    32,      5870,    -5871,    5906,    0,       5910,       -5911,
    5938,   0,       5941,   32,      5943,    -5944,   5970,    0,        5972,    -5973,   6002,       0,
    6004,   -6005,   6068,   0,       6100,    32,      6103,    6103,     6104,    32,      6108,       6108,
    6109,   0,       6110,   -6111,   6144,    32,      6155,    0,        6160,    -6161,   6277,       0,
    6279,   -6280,   6313,   0,       6314,    -6315,   6432,    0,        6444,    -6445,   6448,       0,
    6460,   -6461,   6464,   32,      6465,    -6466,   6468,    32,       6470,    -6471,   6622,       32,
    6656,   -6657,   6679,   0,       6684,    -6685,   6686,    32,       6688,    -6689,   6741,       0,
    6751,   6751,    6752,   0,       6781,    -6782,   6783,    0,        6784,    -6785,   6816,       32,
    6823,   6823,    6824,   32,      6830,    -6831,   6832,    0,        6863,    -6864,   6912,       0,
    6917,   -6918,   6964,   0,       6981,    -6982,   6990,    32,       6992,    -6993,   7002,       32,
    7019,   0,       7028,   32,      7040,    0,       7043,    -7044,    7073,    0,       7086,       -7087,
    7142,   0,       7156,   -7157,   7164,    32,      7168,    -7169,    7204,    0,       7224,       -7225,
    7227,   32,      7232,   -7233,   7294,    32,      7296,    1074,     7297,    1076,    7298,       1086,
    7299,   -1090,   7301,   1090,    7302,    1098,    7303,    1123,     7304,    42571,   7305,       7306,
    7307,   -7308,   7312,   -4305,   7355,    -7356,   7357,    -4350,    7360,    32,      7368,       -7369,
    7376,   0,       7379,   32,      7380,    0,       7401,    -7402,    7405,    0,       7406,       -7407,
    7412,   0,       7413,   -7414,   7415,    0,       7418,    -7419,    7468,    97,      7469,       230,
    7470,   98,      7471,   7471,    7472,    -101,    7474,    477,      7475,    -104,    7483,       7483,
    7484,   111,     7485,   547,     7486,    112,     7487,    114,      7488,    -117,    7490,       119,
    7491,   -7492,   7616,   0,       7680,    2097153, 7830,    -7831,    7835,    7777,    7836,       -7837,
    7838,   223,     7839,   2097153, 7936,    -7937,   7944,    -7937,    7952,    -7953,   7960,       -7953,
    7966,   -7967,   7976,   -7969,   7984,    -7985,   7992,    -7985,    8000,    -8001,   8008,       -8001,
    8014,   -8015,   8025,   8017,    8026,    8026,    8027,    8019,     8028,    8028,    8029,       8021,
    8030,   8030,    8031,   8023,    8032,    -8033,   8040,    -8033,    8048,    -8049,   8072,       -8065,
    8080,   -8081,   8088,   -8081,   8096,    -8097,   8104,    -8097,    8112,    -8113,   8120,       -8113,
    8122,   -8049,   8124,   8115,    8125,    32,      8126,    953,      8127,    32,      8130,       -8131,
    8136,   -8051,   8140,   8131,    8141,    32,      8144,    -8145,    8147,    912,     8148,       -8149,
    8152,   -8145,   8154,   -8055,   8156,    8156,    8157,    32,       8160,    -8161,   8163,       944,
    8164,   -8165,   8168,   -8161,   8170,    -8059,   8172,    8165,     8173,    32,      8176,       -8177,
    8184,   -8057,   8186,   -8061,   8188,    8179,    8189,    32,       8191,    8191,    8192,       32,
    8203,   0,       8208,   32,      8234,    0,       8239,    32,       8288,    0,       8293,       8293,
    8294,   0,       8304,   -8305,   8314,    32,      8319,    -8320,    8330,    32,      8335,       -8336,
    8352,   32,      8385,   -8386,   8400,    0,       8433,    -8434,    8448,    32,      8450,       99,
    8452,   32,      8455,   603,     8456,    32,      8457,    102,      8458,    8458,    8459,       104,
    8462,   -8463,   8464,   105,     8466,    108,     8467,    8467,     8468,    32,      8469,       110,
    8470,   32,      8473,   -113,    8476,    114,     8478,    32,       8484,    122,     8485,       32,
    8486,   969,     8487,   32,      8488,    122,     8489,    32,       8490,    107,     8491,       229,
    8492,   -99,     8494,   32,      8495,    8495,    8496,    -102,     8498,    8526,    8499,       109,
    8500,   -8501,   8506,   32,      8508,    -8509,   8510,    947,      8511,    960,     8512,       32,
    8517,   100,     8518,   -8519,   8522,    32,      8526,    8526,     8527,    32,      8528,       -8529,
    8544,   -8561,   8560,   -8561,   8579,    8580,    8581,    -8582,    8586,    32,      8588,       -8589,
    8592,   32,      9258,   -9259,   9280,    32,      9291,    -9292,    9372,    32,      9398,       -9425,
    9424,   -9425,   9472,   32,      10102,   -10103,  10132,   32,       11124,   -11125,  11126,      32,
    11158,  11158,   11159,  32,      11264,   -11313,  11312,   -11313,   11360,   11361,   11362,      619,
    11363,  7549,    11364,  637,     11365,   -11366,  11367,   11368,    11369,   11370,   11371,      11372,
    11373,  593,     11374,  625,     11375,   592,     11376,   594,      11377,   2097153, 11380,      11380,
    11381,  11382,   11383,  -11384,  11389,   118,     11390,   -576,     11392,   2097153, 11492,      11492,
    11493,  32,      11499,  11500,   11501,   11502,   11503,   0,        11506,   11507,   11508,      -11509,
    11513,  32,      11517,  11517,   11518,   32,      11520,   -11521,   11632,   32,      11633,      -11634,
    11647,  0,       11648,  -11649,  11744,   0,       11776,   32,       11823,   11823,   11824,      32,
    11870,  -11871,  11904,  32,      11930,   11930,   11931,   32,       11935,   11935,   11936,      32,
    12019,  -12020,  12272,  32,      12293,   -12294,  12296,   32,       12321,   -12322,  12330,      0,
    12336,  32,      12337,  -12338,  12342,   32,      12344,   -12345,   12349,   32,      12352,      -12353,
    12441,  0,       12443,  32,      12445,   -12446,  12448,   32,       12449,   -12450,  12539,      32,
    12540,  0,       12541,  -12542,  12688,   32,      12690,   -12691,   12736,   32,      12774,      -12775,
    12783,  32,      12784,  -12785,  12800,   32,      12831,   -12832,   12842,   32,      12868,      -12869,
    12880,  32,      12881,  -12882,  12910,   32,      12928,   -12929,   12992,   32,      13008,      -13009,
    13055,  32,      13312,  -13313,  19904,   32,      19968,   -19969,   42128,   32,      42183,      -42184,
    42238,  32,      42240,  -42241,  42509,   32,      42512,   -42513,   42560,   2097153, 42606,      42606,
    42607,  0,       42611,  32,      42612,   0,       42622,   32,       42623,   2097153, 42652,      -42653,
    42654,  0,       42656,  -42657,  42736,   0,       42738,   32,       42744,   -42745,  42752,      32,
    42775,  -42776,  42784,  32,      42786,   2097153, 42800,   -42801,   42802,   2097153, 42864,      -42865,
    42873,  42874,   42875,  42876,   42877,   7545,    42878,   2097153,  42888,   42888,   42889,      32,
    42891,  42892,   42893,  613,     42894,   -42895,  42896,   2097153,  42900,   -42901,  42902,      2097153,
    42922,  614,     42923,  604,     42924,   609,     42925,   620,      42926,   618,     42927,      42927,
    42928,  670,     42929,  647,     42930,   669,     42931,   43859,    42932,   2097153, 42948,      42900,
    42949,  642,     42950,  7566,    42951,   42952,   42953,   42954,    42955,   612,     42956,      42957,
    42958,  -42959,  42960,  42961,   42962,   -42963,  42966,   2097153,  42972,   411,     42973,      -42974,
    42994,  99,      42995,  102,     42996,   113,     42997,   42998,    42999,   42999,   43000,      295,
    43001,  -43002,  43010,  0,       43011,   -43012,  43014,   0,        43015,   -43016,  43019,      0,
    43020,  -43021,  43043,  0,       43048,   32,      43052,   0,        43053,   -43054,  43062,      32,
    43066,  -43067,  43124,  32,      43128,   -43129,  43136,   0,        43138,   -43139,  43188,      0,
    43206,  -43207,  43214,  32,      43216,   -43217,  43232,   0,        43250,   -43251,  43256,      32,
    43259,  43259,   43260,  32,      43261,   -43262,  43263,   0,        43264,   -43265,  43302,      0,
    43310,  32,      43312,  -43313,  43335,   0,       43348,   -43349,   43359,   32,      43360,      -43361,
    43392,  0,       43396,  -43397,  43443,   0,       43457,   32,       43470,   -43471,  43486,      32,
    43488,  -43489,  43493,  0,       43494,   -43495,  43561,   0,        43575,   -43576,  43587,      0,
    43588,  -43589,  43596,  0,       43598,   -43599,  43612,   32,       43616,   -43617,  43639,      32,
    43642,  43642,   43643,  0,       43646,   -43647,  43696,   0,        43697,   43697,   43698,      0,
    43701,  -43702,  43703,  0,       43705,   -43706,  43710,   0,        43712,   43712,   43713,      0,
    43714,  -43715,  43742,  32,      43744,   -43745,  43755,   0,        43760,   32,      43762,      -43763,
    43765,  0,       43767,  -43768,  43867,   32,      43868,   -43869,   43882,   32,      43884,      -43885,
    43888,  -5025,   43968,  -43969,  44003,   0,       44011,   32,       44012,   0,       44014,      -44015,
    55296,  0,       57344,  -57345,  64261,   64262,   64263,   -64264,   64286,   0,       64287,      -64288,
    64297,  32,      64298,  -64299,  64434,   32,      64451,   -64452,   64830,   32,      64848,      -64849,
    64975,  32,      65008,  -65009,  65020,   32,      65024,   0,        65040,   32,      65050,      -65051,
    65056,  0,       65072,  32,      65107,   65107,   65108,   32,       65127,   65127,   65128,      32,
    65132,  -65133,  65279,  0,       65280,   65280,   65281,   32,       65296,   -65297,  65306,      32,
    65313,  -65346,  65339,  32,      65345,   -65346,  65371,   32,       65382,   -65383,  65504,      32,
    65511,  65511,   65512,  32,      65519,   -65520,  65529,   0,        65532,   32,      65536,      -65537,
    65792,  32,      65795,  -65796,  65847,   32,      65856,   -65857,   65913,   32,      65930,      -65931,
    65932,  32,      65935,  65935,   65936,   32,      65949,   -65950,   65952,   32,      65953,      -65954,
    66000,  32,      66045,  0,       66046,   -66047,  66272,   0,        66273,   -66274,  66422,      0,
    66427,  -66428,  66463,  32,      66464,   -66465,  66512,   32,       66513,   -66514,  66560,      -66601,
    66600,  -66601,  66736,  -66777,  66772,   -66773,  66927,   32,       66928,   -66968,  66939,      66939,
    66940,  -66980,  66955,  66955,   66956,   -66996,  66963,   66963,    66964,   -67004,  66966,      -66967,
    67671,  32,      67672,  -67673,  67703,   32,      67705,   -67706,   67871,   32,      67872,      -67873,
    67903,  32,      67904,  -67905,  68097,   0,       68100,   68100,    68101,   0,       68103,      -68104,
    68108,  0,       68112,  -68113,  68152,   0,       68155,   -68156,   68159,   0,       68160,      -68161,
    68176,  32,      68185,  -68186,  68223,   32,      68224,   -68225,   68296,   32,      68297,      -68298,
    68325,  0,       68327,  -68328,  68336,   32,      68343,   -68344,   68409,   32,      68416,      -68417,
    68505,  32,      68509,  -68510,  68736,   -68801,  68787,   -68788,   68900,   0,       68904,      -68905,
    68944,  -68977,  68966,  -68967,  68969,   0,       68974,   32,       68975,   -68976,  69006,      32,
    69008,  -69009,  69291,  0,       69293,   32,      69294,   -69295,   69372,   0,       69376,      -69377,
    69446,  0,       69457,  -69458,  69461,   32,      69466,   -69467,   69506,   0,       69510,      32,
    69514,  -69515,  69632,  0,       69635,   -69636,  69688,   0,        69703,   32,      69710,      -69711,
    69744,  0,       69745,  -69746,  69747,   0,       69749,   -69750,   69759,   0,       69763,      -69764,
    69808,  0,       69819,  32,      69821,   0,       69822,   32,       69826,   0,       69827,      -69828,
    69837,  0,       69838,  -69839,  69888,   0,       69891,   -69892,   69927,   0,       69941,      -69942,
    69952,  32,      69956,  69956,   69957,   0,       69959,   -69960,   70003,   0,       70004,      32,
    70006,  -70007,  70016,  0,       70019,   -70020,  70067,   0,        70081,   -70082,  70085,      32,
    70089,  0,       70093,  32,      70094,   0,       70096,   -70097,   70107,   32,      70108,      70108,
    70109,  32,      70112,  -70113,  70188,   0,       70200,   32,       70206,   0,       70207,      -70208,
    70209,  0,       70210,  -70211,  70313,   32,      70314,   -70315,   70367,   0,       70379,      -70380,
    70400,  0,       70404,  -70405,  70459,   0,       70461,   70461,    70462,   0,       70469,      -70470,
    70471,  0,       70473,  -70474,  70475,   0,       70478,   -70479,   70487,   0,       70488,      -70489,
    70498,  0,       70500,  -70501,  70502,   0,       70509,   -70510,   70512,   0,       70517,      -70518,
    70584,  0,       70593,  70593,   70594,   0,       70595,   -70596,   70597,   0,       70598,      70598,
    70599,  0,       70603,  70603,   70604,   0,       70609,   70609,    70610,   0,       70611,      70611,
    70612,  32,      70614,  70614,   70615,   32,      70617,   -70618,   70625,   0,       70627,      -70628,
    70709,  0,       70727,  -70728,  70731,   32,      70736,   -70737,   70746,   32,      70748,      70748,
    70749,  32,      70750,  0,       70751,   -70752,  70832,   0,        70852,   -70853,  70854,      32,
    70855,  -70856,  71087,  0,       71094,   -71095,  71096,   0,        71105,   32,      71128,      -71129,
    71132,  0,       71134,  -71135,  71216,   0,       71233,   32,       71236,   -71237,  71264,      32,
    71277,  -71278,  71339,  0,       71352,   71352,   71353,   32,       71354,   -71355,  71453,      0,
    71468,  -71469,  71484,  32,      71488,   -71489,  71724,   0,        71739,   32,      71740,      -71741,
    71840,  -71873,  71872,  -71873,  71984,   0,       71990,   71990,    71991,   0,       71993,      -71994,
    71995,  0,       71999,  71999,   72000,   0,       72001,   72001,    72002,   0,       72004,      32,
    72007,  -72008,  72145,  0,       72152,   -72153,  72154,   0,        72161,   72161,   72162,      32,
    72163,  72163,   72164,  0,       72165,   -72166,  72193,   0,        72203,   -72204,  72243,      0,
    72250,  72250,   72251,  0,       72255,   32,      72263,   0,        72264,   -72265,  72273,      0,
    72284,  -72285,  72330,  0,       72346,   32,      72349,   72349,    72350,   32,      72355,      -72356,
    72448,  32,      72458,  -72459,  72673,   32,      72674,   -72675,   72751,   0,       72759,      72759,
    72760,  0,       72768,  72768,   72769,   32,      72774,   -72775,   72816,   32,      72818,      -72819,
    72850,  0,       72872,  72872,   72873,   0,       72887,   -72888,   73009,   0,       73015,      -73016,
    73018,  0,       73019,  73019,   73020,   0,       73022,   73022,    73023,   0,       73030,      73030,
    73031,  0,       73032,  -73033,  73098,   0,       73103,   73103,    73104,   0,       73106,      73106,
    73107,  0,       73112,  -73113,  73459,   0,       73463,   32,       73465,   -73466,  73472,      0,
    73474,  73474,   73475,  0,       73476,   -73477,  73524,   0,        73531,   -73532,  73534,      0,
    73539,  32,      73552,  -73553,  73562,   0,       73563,   -73564,   73685,   32,      73714,      -73715,
    73727,  32,      73728,  -73729,  74864,   32,      74869,   -74870,   77809,   32,      77811,      -77812,
    78896,  0,       78913,  -78914,  78919,   0,       78934,   -78935,   90398,   0,       90416,      -90417,
    92782,  32,      92784,  -92785,  92912,   0,       92917,   32,       92918,   -92919,  92976,      0,
    92983,  32,      92992,  -92993,  92996,   32,      92998,   -92999,   93549,   32,      93552,      -93553,
    93760,  -93793,  93792,  -93793,  93847,   32,      93851,   -93852,   94031,   0,       94032,      94032,
    94033,  0,       94088,  -94089,  94095,   0,       94099,   -94100,   94178,   32,      94179,      94179,
    94180,  0,       94181,  -94182,  94192,   0,       94194,   -94195,   113820,  32,      113821,     0,
    113823, 32,      113824, 0,       113828,  -113829, 117760,  32,       117974,  -98,     118000,     -118001,
    118016, 32,      118452, -118453, 118528,  0,       118574,  -118575,  118576,  0,       118599,     -118600,
    118608, 32,      118724, -118725, 118784,  32,      119030,  -119031,  119040,  32,      119079,     -119080,
    119081, 32,      119141, 0,       119146,  32,      119149,  0,        119171,  32,      119173,     0,
    119180, 32,      119210, 0,       119214,  32,      119275,  -119276,  119296,  32,      119362,     0,
    119365, 32,      119366, -119367, 119552,  32,      119639,  -119640,  119808,  -98,     119834,     -119835,
    119860, -98,     119886, -119887, 119912,  -98,     119938,  -119939,  119964,  97,      119965,     119965,
    119966, -100,    119968, -119969, 119970,  103,     119971,  -119972,  119973,  -107,    119975,     -119976,
    119977, -111,    119981, 119981,  119982,  -116,    119990,  -119991,  120016,  -98,     120042,     -120043,
    120068, -98,     120070, 120070,  120071,  -101,    120075,  -120076,  120077,  -107,    120085,     120085,
    120086, -116,    120093, -120094, 120120,  -98,     120122,  120122,   120123,  -101,    120127,     120127,
    120128, -106,    120133, 120133,  120134,  111,     120135,  -120136,  120138,  -116,    120145,     -120146,
    120172, -98,     120198, -120199, 120224,  -98,     120250,  -120251,  120276,  -98,     120302,     -120303,
    120328, -98,     120354, -120355, 120380,  -98,     120406,  -120407,  120432,  -98,     120458,     -120459,
    120488, -946,    120505, 952,     120506,  -964,    120513,  32,       120514,  -120515, 120531,     963,
    120532, -120533, 120539, 32,      120540,  -120541, 120546,  -946,     120563,  952,     120564,     -964,
    120571, 32,      120572, -120573, 120589,  963,     120590,  -120591,  120597,  32,      120598,     -120599,
    120604, -946,    120621, 952,     120622,  -964,    120629,  32,       120630,  -120631, 120647,     963,
    120648, -120649, 120655, 32,      120656,  -120657, 120662,  -946,     120679,  952,     120680,     -964,
    120687, 32,      120688, -120689, 120705,  963,     120706,  -120707,  120713,  32,      120714,     -120715,
    120720, -946,    120737, 952,     120738,  -964,    120745,  32,       120746,  -120747, 120763,     963,
    120764, -120765, 120771, 32,      120772,  -120773, 120778,  989,      120779,  -120780, 120832,     32,
    121344, 0,       121399, 32,      121403,  0,       121453,  32,       121461,  0,       121462,     32,
    121476, 0,       121477, 32,      121484,  -121485, 121499,  0,        121504,  121504,  121505,     0,
    121520, -121521, 122880, 0,       122887,  122887,  122888,  0,        122905,  -122906, 122907,     0,
    122914, 122914,  122915, 0,       122917,  122917,  122918,  0,        122923,  -122924, 123023,     0,
    123024, -123025, 123184, 0,       123191,  -123192, 123215,  32,       123216,  -123217, 123566,     0,
    123567, -123568, 123628, 0,       123632,  -123633, 123647,  32,       123648,  -123649, 124140,     0,
    124144, -124145, 124398, 0,       124400,  -124401, 124415,  32,       124416,  -124417, 125136,     0,
    125143, -125144, 125184, -125219, 125218,  -125219, 125252,  0,        125259,  -125260, 125278,     32,
    125280, -125281, 126124, 32,      126125,  -126126, 126128,  32,       126129,  -126130, 126254,     32,
    126255, -126256, 126704, 32,      126706,  -126707, 126976,  32,       127020,  -127021, 127024,     32,
    127124, -127125, 127136, 32,      127151,  -127152, 127153,  32,       127168,  127168,  127169,     32,
    127184, 127184,  127185, 32,      127222,  -127223, 127245,  32,       127275,  99,      127276,     114,
    127277, 32,      127280, -98,     127306,  32,      127406,  -127407,  127462,  32,      127490,     -127491,
    127552, 32,      127561, -127562, 127584,  32,      127590,  -127591,  127744,  32,      128728,     -128729,
    128732, 32,      128749, -128750, 128752,  32,      128765,  -128766,  128768,  32,      128887,     -128888,
    128891, 32,      128986, -128987, 128992,  32,      129004,  -129005,  129008,  32,      129009,     -129010,
    129024, 32,      129036, -129037, 129040,  32,      129096,  -129097,  129104,  32,      129114,     -129115,
    129120, 32,      129160, -129161, 129168,  32,      129198,  -129199,  129200,  32,      129212,     -129213,
    129216, 32,      129218, -129219, 129280,  32,      129620,  -129621,  129632,  32,      129646,     -129647,
    129648, 32,      129661, -129662, 129664,  32,      129674,  -129675,  129679,  32,      129735,     -129736,
    129742, 32,      129757, -129758, 129759,  32,      129770,  -129771,  129776,  32,      129785,     -129786,
    129792, 32,      129939, 129939,  129940,  32,      130032,  -130033,  131070,  32,      131072,     -131073,
    196606, 32,      196608, -196609, 262142,  32,      262144,  -262145,  327678,  32,      327680,     -327681,
    393214, 32,      393216, -393217, 458750,  32,      458752,  -458753,  524286,  32,      524288,     -524289,
    589822, 32,      589824, -589825, 655358,  32,      655360,  -655361,  720894,  32,      720896,     -720897,
    786430, 32,      786432, -786433, 851966,  32,      851968,  -851969,  917502,  32,      917504,     917504,
    917505, 0,       917506, -917507, 917536,  0,       917632,  -917633,  917760,  0,       918000,     -918001,
    983038, 32,      983040, -983041, 1048574, 32,      1048576, -1048577, 1114110, 32,      2147483647, 0};

static const int16 to_lower_table[TABLE_SIZE] = {
    0,     1,    2,    3,    4,     5,    6,    7,    8,    9,    10,   11,   12,   13,   14,   15,   16,   17,   18,
    19,    20,   21,   22,   23,    24,   25,   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,
    38,    39,   40,   41,   42,    43,   44,   45,   46,   47,   48,   49,   50,   51,   52,   53,   54,   55,   56,
    57,    58,   59,   60,   61,    62,   63,   64,   97,   98,   99,   100,  101,  102,  103,  104,  105,  106,  107,
    108,   109,  110,  111,  112,   113,  114,  115,  116,  117,  118,  119,  120,  121,  122,  91,   92,   93,   94,
    95,    96,   97,   98,   99,    100,  101,  102,  103,  104,  105,  106,  107,  108,  109,  110,  111,  112,  113,
    114,   115,  116,  117,  118,   119,  120,  121,  122,  123,  124,  125,  126,  127,  128,  129,  130,  131,  132,
    133,   134,  135,  136,  137,   138,  139,  140,  141,  142,  143,  144,  145,  146,  147,  148,  149,  150,  151,
    152,   153,  154,  155,  156,   157,  158,  159,  160,  161,  162,  163,  164,  165,  166,  167,  168,  169,  170,
    171,   172,  173,  174,  175,   176,  177,  178,  179,  180,  181,  182,  183,  184,  185,  186,  187,  188,  189,
    190,   191,  224,  225,  226,   227,  228,  229,  230,  231,  232,  233,  234,  235,  236,  237,  238,  239,  240,
    241,   242,  243,  244,  245,   246,  215,  248,  249,  250,  251,  252,  253,  254,  223,  224,  225,  226,  227,
    228,   229,  230,  231,  232,   233,  234,  235,  236,  237,  238,  239,  240,  241,  242,  243,  244,  245,  246,
    247,   248,  249,  250,  251,   252,  253,  254,  255,  257,  257,  259,  259,  261,  261,  263,  263,  265,  265,
    267,   267,  269,  269,  271,   271,  273,  273,  275,  275,  277,  277,  279,  279,  281,  281,  283,  283,  285,
    285,   287,  287,  289,  289,   291,  291,  293,  293,  295,  295,  297,  297,  299,  299,  301,  301,  303,  303,
    105,   305,  307,  307,  309,   309,  311,  311,  312,  314,  314,  316,  316,  318,  318,  320,  320,  322,  322,
    324,   324,  326,  326,  328,   328,  329,  331,  331,  333,  333,  335,  335,  337,  337,  339,  339,  341,  341,
    343,   343,  345,  345,  347,   347,  349,  349,  351,  351,  353,  353,  355,  355,  357,  357,  359,  359,  361,
    361,   363,  363,  365,  365,   367,  367,  369,  369,  371,  371,  373,  373,  375,  375,  255,  378,  378,  380,
    380,   382,  382,  383,  384,   595,  387,  387,  389,  389,  596,  392,  392,  598,  599,  396,  396,  397,  477,
    601,   603,  402,  402,  608,   611,  405,  617,  616,  409,  409,  410,  411,  623,  626,  414,  629,  417,  417,
    419,   419,  421,  421,  640,   424,  424,  643,  426,  427,  429,  429,  648,  432,  432,  650,  651,  436,  436,
    438,   438,  658,  441,  441,   442,  443,  445,  445,  446,  447,  448,  449,  450,  451,  454,  454,  454,  457,
    457,   457,  460,  460,  460,   462,  462,  464,  464,  466,  466,  468,  468,  470,  470,  472,  472,  474,  474,
    476,   476,  477,  479,  479,   481,  481,  483,  483,  485,  485,  487,  487,  489,  489,  491,  491,  493,  493,
    495,   495,  496,  499,  499,   499,  501,  501,  405,  447,  505,  505,  507,  507,  509,  509,  511,  511,  513,
    513,   515,  515,  517,  517,   519,  519,  521,  521,  523,  523,  525,  525,  527,  527,  529,  529,  531,  531,
    533,   533,  535,  535,  537,   537,  539,  539,  541,  541,  543,  543,  414,  545,  547,  547,  549,  549,  551,
    551,   553,  553,  555,  555,   557,  557,  559,  559,  561,  561,  563,  563,  564,  565,  566,  567,  568,  569,
    11365, 572,  572,  410,  11366, 575,  576,  578,  578,  384,  649,  652,  583,  583,  585,  585,  587,  587,  589,
    589,   591,  591,  592,  593,   594,  595,  596,  597,  598,  599,  600,  601,  602,  603,  604,  605,  606,  607,
    608,   609,  610,  611,  612,   613,  614,  615,  616,  617,  618,  619,  620,  621,  622,  623,  624,  625,  626,
    627,   628,  629,  630,  631,   632,  633,  634,  635,  636,  637,  638,  639,  640,  641,  642,  643,  644,  645,
    646,   647,  648,  649,  650,   651,  652,  653,  654,  655,  656,  657,  658,  659,  660,  661,  662,  663,  664,
    665,   666,  667,  668,  669,   670,  671,  672,  673,  674,  675,  676,  677,  678,  679,  680,  681,  682,  683,
    684,   685,  686,  687,  688,   689,  690,  691,  692,  693,  694,  695,  696,  697,  698,  699,  700,  701,  702,
    703,   704,  705,  706,  707,   708,  709,  710,  711,  712,  713,  714,  715,  716,  717,  718,  719,  720,  721,
    722,   723,  724,  725,  726,   727,  728,  729,  730,  731,  732,  733,  734,  735,  736,  737,  738,  739,  740,
    741,   742,  743,  744,  745,   746,  747,  748,  749,  750,  751,  752,  753,  754,  755,  756,  757,  758,  759,
    760,   761,  762,  763,  764,   765,  766,  767,  768,  769,  770,  771,  772,  773,  774,  775,  776,  777,  778,
    779,   780,  781,  782,  783,   784,  785,  786,  787,  788,  789,  790,  791,  792,  793,  794,  795,  796,  797,
    798,   799,  800,  801,  802,   803,  804,  805,  806,  807,  808,  809,  810,  811,  812,  813,  814,  815,  816,
    817,   818,  819,  820,  821,   822,  823,  824,  825,  826,  827,  828,  829,  830,  831,  832,  833,  834,  835,
    836,   837,  838,  839,  840,   841,  842,  843,  844,  845,  846,  847,  848,  849,  850,  851,  852,  853,  854,
    855,   856,  857,  858,  859,   860,  861,  862,  863,  864,  865,  866,  867,  868,  869,  870,  871,  872,  873,
    874,   875,  876,  877,  878,   879,  881,  881,  883,  883,  884,  885,  887,  887,  888,  889,  890,  891,  892,
    893,   894,  1011, 896,  897,   898,  899,  900,  901,  940,  903,  941,  942,  943,  907,  972,  909,  973,  974,
    912,   945,  946,  947,  948,   949,  950,  951,  952,  953,  954,  955,  956,  957,  958,  959,  960,  961,  930,
    963,   964,  965,  966,  967,   968,  969,  970,  971,  940,  941,  942,  943,  944,  945,  946,  947,  948,  949,
    950,   951,  952,  953,  954,   955,  956,  957,  958,  959,  960,  961,  962,  963,  964,  965,  966,  967,  968,
    969,   970,  971,  972,  973,   974,  983,  976,  977,  978,  979,  980,  981,  982,  983,  985,  985,  987,  987,
    989,   989,  991,  991,  993,   993,  995,  995,  997,  997,  999,  999,  1001, 1001, 1003, 1003, 1005, 1005, 1007,
    1007,  1008, 1009, 1010, 1011,  952,  1013, 1014, 1016, 1016, 1010, 1019, 1019, 1020, 891,  892,  893,  1104, 1105,
    1106,  1107, 1108, 1109, 1110,  1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1072, 1073, 1074, 1075, 1076,
    1077,  1078, 1079, 1080, 1081,  1082, 1083, 1084, 1085, 1086, 1087, 1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095,
    1096,  1097, 1098, 1099, 1100,  1101, 1102, 1103, 1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1081, 1082,
    1083,  1084, 1085, 1086, 1087,  1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099, 1100, 1101,
    1102,  1103, 1104, 1105, 1106,  1107, 1108, 1109, 1110, 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1121,
    1121,  1123, 1123, 1125, 1125,  1127, 1127, 1129, 1129, 1131, 1131, 1133, 1133, 1135, 1135, 1137, 1137, 1139, 1139,
    1141,  1141, 1143, 1143, 1145,  1145, 1147, 1147, 1149, 1149, 1151, 1151, 1153, 1153, 1154, 1155, 1156, 1157, 1158,
    1159,  1160, 1161, 1163, 1163,  1165, 1165, 1167, 1167, 1169, 1169, 1171, 1171, 1173, 1173, 1175, 1175, 1177, 1177,
    1179,  1179, 1181, 1181, 1183,  1183, 1185, 1185, 1187, 1187, 1189, 1189, 1191, 1191, 1193, 1193, 1195, 1195, 1197,
    1197,  1199, 1199, 1201, 1201,  1203, 1203, 1205, 1205, 1207, 1207, 1209, 1209, 1211, 1211, 1213, 1213, 1215, 1215,
    1231,  1218, 1218, 1220, 1220,  1222, 1222, 1224, 1224, 1226, 1226, 1228, 1228, 1230, 1230, 1231, 1233, 1233, 1235,
    1235,  1237, 1237, 1239, 1239,  1241, 1241, 1243, 1243, 1245, 1245, 1247, 1247, 1249, 1249, 1251, 1251, 1253, 1253,
    1255,  1255, 1257, 1257, 1259,  1259, 1261, 1261, 1263, 1263, 1265, 1265, 1267, 1267, 1269, 1269, 1271, 1271, 1273,
    1273,  1275, 1275, 1277, 1277,  1279, 1279};

static const int32 to_lower_ranges[] = {
    1280,    2097153,    1328,    1328,    1329,    -1378,  1367,    -1368,   4256,   -11521,  4294,   4294,    4295,
    11559,   4296,       -4297,   4301,    11565,   4302,   -4303,   5024,    -43889, 5104,    -5113,  5110,    -5111,
    7305,    7306,       7307,    -7308,   7312,    -4305,  7355,    -7356,   7357,   -4350,   7360,   -7361,   7680,
    2097153, 7830,       -7831,   7838,    223,     7839,   2097153, 7936,    -7937,  7944,    -7937,  7952,    -7953,
    7960,    -7953,      7966,    -7967,   7976,    -7969,  7984,    -7985,   7992,   -7985,   8000,   -8001,   8008,
    -8001,   8014,       -8015,   8025,    8017,    8026,   8026,    8027,    8019,   8028,    8028,   8029,    8021,
    8030,    8030,       8031,    8023,    8032,    -8033,  8040,    -8033,   8048,   -8049,   8072,   -8065,   8080,
    -8081,   8088,       -8081,   8096,    -8097,   8104,   -8097,   8112,    -8113,  8120,    -8113,  8122,    -8049,
    8124,    8115,       8125,    -8126,   8136,    -8051,  8140,    8131,    8141,   -8142,   8152,   -8145,   8154,
    -8055,   8156,       -8157,   8168,    -8161,   8170,   -8059,   8172,    8165,   8173,    -8174,  8184,    -8057,
    8186,    -8061,      8188,    8179,    8189,    -8190,  8486,    969,     8487,   -8488,   8490,   107,     8491,
    229,     8492,       -8493,   8498,    8526,    8499,   -8500,   8544,    -8561,  8560,    -8561,  8579,    8580,
    8581,    -8582,      9398,    -9425,   9424,    -9425,  11264,   -11313,  11312,  -11313,  11360,  11361,   11362,
    619,     11363,      7549,    11364,   637,     11365,  -11366,  11367,   11368,  11369,   11370,  11371,   11372,
    11373,   593,        11374,   625,     11375,   592,    11376,   594,     11377,  2097153, 11380,  11380,   11381,
    11382,   11383,      -11384,  11390,   -576,    11392,  2097153, 11492,   -11493, 11499,   11500,  11501,   11502,
    11503,   -11504,     11506,   11507,   11508,   -11509, 42560,   2097153, 42606,  -42607,  42624,  2097153, 42652,
    -42653,  42786,      2097153, 42800,   -42801,  42802,  2097153, 42864,   -42865, 42873,   42874,  42875,   42876,
    42877,   7545,       42878,   2097153, 42888,   -42889, 42891,   42892,   42893,  613,     42894,  -42895,  42896,
    2097153, 42900,      -42901,  42902,   2097153, 42922,  614,     42923,   604,    42924,   609,    42925,   620,
    42926,   618,        42927,   42927,   42928,   670,    42929,   647,     42930,  669,     42931,  43859,   42932,
    2097153, 42948,      42900,   42949,   642,     42950,  7566,    42951,   42952,  42953,   42954,  42955,   612,
    42956,   42957,      42958,   -42959,  42960,   42961,  42962,   -42963,  42966,  2097153, 42972,  411,     42973,
    -42974,  42997,      42998,   42999,   -43000,  65313,  -65346,  65339,   -65340, 66560,   -66601, 66600,   -66601,
    66736,   -66777,     66772,   -66773,  66928,   -66968, 66939,   66939,   66940,  -66980,  66955,  66955,   66956,
    -66996,  66963,      66963,   66964,   -67004,  66966,  -66967,  68736,   -68801, 68787,   -68788, 68944,   -68977,
    68966,   -68967,     71840,   -71873,  71872,   -71873, 93760,   -93793,  93792,  -93793,  125184, -125219, 125218,
    -125219, 2147483647, 0};

static const int16 without_diacritics_table[TABLE_SIZE] = {
    0,    1,    2,    3,    4,    5,    6,    7,    8,    9,    10,   11,   12,   13,   14,   15,   16,   17,   18,
    19,   20,   21,   22,   23,   24,   25,   26,   27,   28,   29,   30,   31,   32,   33,   34,   35,   36,   37,
    38,   39,   40,   41,   42,   43,   44,   45,   46,   47,   48,   49,   50,   51,   52,   53,   54,   55,   56,
    57,   58,   59,   60,   61,   62,   63,   64,   65,   66,   67,   68,   69,   70,   71,   72,   73,   74,   75,
    76,   77,   78,   79,   80,   81,   82,   83,   84,   85,   86,   87,   88,   89,   90,   91,   92,   93,   94,
    95,   96,   97,   98,   99,   100,  101,  102,  103,  104,  105,  106,  107,  108,  109,  110,  111,  112,  113,
    114,  115,  116,  117,  118,  119,  120,  121,  122,  123,  124,  125,  126,  127,  128,  129,  130,  131,  132,
    133,  134,  135,  136,  137,  138,  139,  140,  141,  142,  143,  144,  145,  146,  147,  148,  149,  150,  151,
    152,  153,  154,  155,  156,  157,  158,  159,  32,   161,  162,  163,  164,  165,  166,  167,  32,   169,  97,
    171,  172,  0,    174,  32,   176,  177,  50,   51,   32,   956,  182,  0,    32,   49,   111,  187,  188,  189,
    190,  191,  65,   65,   65,   65,   65,   65,   198,  67,   69,   69,   69,   69,   73,   73,   73,   73,   208,
    78,   79,   79,   79,   79,   79,   215,  216,  85,   85,   85,   85,   89,   222,  223,  97,   97,   97,   97,
    97,   97,   230,  99,   101,  101,  101,  101,  105,  105,  105,  105,  240,  110,  111,  111,  111,  111,  111,
    247,  248,  117,  117,  117,  117,  121,  254,  121,  65,   97,   65,   97,   65,   97,   67,   99,   67,   99,
    67,   99,   67,   99,   68,   100,  272,  273,  69,   101,  69,   101,  69,   101,  69,   101,  69,   101,  71,
    103,  71,   103,  71,   103,  71,   103,  72,   104,  294,  295,  73,   105,  73,   105,  73,   105,  73,   105,
    73,   305,  306,  307,  74,   106,  75,   107,  312,  76,   108,  76,   108,  76,   108,  76,   108,  321,  322,
    78,   110,  78,   110,  78,   110,  110,  330,  331,  79,   111,  79,   111,  79,   111,  338,  339,  82,   114,
    82,   114,  82,   114,  83,   115,  83,   115,  83,   115,  83,   115,  84,   116,  84,   116,  358,  359,  85,
    117,  85,   117,  85,   117,  85,   117,  85,   117,  85,   117,  87,   119,  89,   121,  89,   90,   122,  90,
    122,  90,   122,  115,  384,  385,  386,  387,  388,  389,  390,  391,  392,  393,  394,  395,  396,  397,  398,
    399,  400,  401,  402,  403,  404,  405,  406,  407,  408,  409,  410,  411,  412,  413,  414,  415,  79,   111,
    418,  419,  420,  421,  422,  423,  424,  425,  426,  427,  428,  429,  430,  85,   117,  433,  434,  435,  436,
    437,  438,  439,  440,  441,  442,  443,  444,  445,  446,  447,  448,  449,  450,  451,  452,  453,  454,  455,
    456,  457,  458,  459,  460,  65,   97,   73,   105,  79,   111,  85,   117,  85,   117,  85,   117,  85,   117,
    85,   117,  477,  65,   97,   65,   97,   198,  230,  484,  485,  71,   103,  75,   107,  79,   111,  79,   111,
    439,  658,  106,  497,  498,  499,  71,   103,  502,  503,  78,   110,  65,   97,   198,  230,  216,  248,  65,
    97,   65,   97,   69,   101,  69,   101,  73,   105,  73,   105,  79,   111,  79,   111,  82,   114,  82,   114,
    85,   117,  85,   117,  83,   115,  84,   116,  540,  541,  72,   104,  544,  545,  546,  547,  548,  549,  65,
    97,   69,   101,  79,   111,  79,   111,  79,   111,  79,   111,  89,   121,  564,  565,  566,  567,  568,  569,
    570,  571,  572,  573,  574,  575,  576,  577,  578,  579,  580,  581,  582,  583,  584,  585,  586,  587,  588,
    589,  590,  591,  592,  593,  594,  595,  596,  597,  598,  599,  600,  601,  602,  603,  604,  605,  606,  607,
    608,  609,  610,  611,  612,  613,  614,  615,  616,  617,  618,  619,  620,  621,  622,  623,  624,  625,  626,
    627,  628,  629,  630,  631,  632,  633,  634,  635,  636,  637,  638,  639,  640,  641,  642,  643,  644,  645,
    646,  647,  648,  649,  650,  651,  652,  653,  654,  655,  656,  657,  658,  659,  660,  661,  662,  663,  664,
    665,  666,  667,  668,  669,  670,  671,  672,  673,  674,  675,  676,  677,  678,  679,  680,  681,  682,  683,
    684,  685,  686,  687,  104,  614,  106,  114,  633,  635,  641,  119,  121,  697,  698,  699,  0,    701,  0,
    703,  704,  705,  706,  707,  708,  709,  710,  711,  712,  713,  714,  715,  716,  717,  718,  719,  720,  721,
    722,  723,  724,  725,  726,  727,  32,   32,   32,   32,   32,   32,   734,  735,  611,  108,  115,  120,  661,
    741,  742,  743,  744,  745,  746,  747,  748,  749,  750,  751,  752,  753,  754,  755,  756,  757,  758,  759,
    760,  761,  762,  763,  764,  765,  766,  767,  0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,    837,  0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,    0,
    0,    0,    0,    0,    0,    0,    880,  881,  882,  883,  697,  885,  886,  887,  888,  889,  32,   891,  892,
    893,  59,   895,  896,  897,  898,  899,  32,   32,   913,  903,  917,  919,  921,  907,  927,  909,  933,  937,
    953,  913,  914,  915,  916,  917,  918,  919,  920,  921,  922,  923,  924,  925,  926,  927,  928,  929,  930,
    931,  932,  933,  934,  935,  936,  937,  921,  933,  945,  949,  951,  953,  965,  945,  946,  947,  948,  949,
    950,  951,  952,  953,  954,  955,  956,  957,  958,  959,  960,  961,  962,  963,  964,  965,  966,  967,  968,
    969,  953,  965,  959,  965,  969,  975,  946,  952,  933,  933,  933,  966,  960,  983,  984,  985,  986,  987,
    988,  989,  990,  991,  992,  993,  994,  995,  996,  997,  998,  999,  1000, 1001, 1002, 1003, 1004, 1005, 1006,
    1007, 954,  961,  962,  1011, 920,  949,  1014, 1015, 1016, 931,  1018, 1019, 1020, 1021, 1022, 1023, 1045, 1045,
    1026, 1043, 1028, 1029, 1030, 1030, 1032, 1033, 1034, 1035, 1050, 1048, 1059, 1039, 1040, 1041, 1042, 1043, 1044,
    1045, 1046, 1047, 1048, 1048, 1050, 1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063,
    1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080, 1080, 1082,
    1083, 1084, 1085, 1086, 1087, 1088, 1089, 1090, 1091, 1092, 1093, 1094, 1095, 1096, 1097, 1098, 1099, 1100, 1101,
    1102, 1103, 1077, 1077, 1106, 1075, 1108, 1109, 1110, 1110, 1112, 1113, 1114, 1115, 1082, 1080, 1091, 1119, 1120,
    1121, 1122, 1123, 1124, 1125, 1126, 1127, 1128, 1129, 1130, 1131, 1132, 1133, 1134, 1135, 1136, 1137, 1138, 1139,
    1140, 1141, 1140, 1141, 1144, 1145, 1146, 1147, 1148, 1149, 1150, 1151, 1152, 1153, 1154, 0,    0,    0,    0,
    0,    0,    0,    1162, 1163, 1164, 1165, 1166, 1167, 1168, 1169, 1170, 1171, 1172, 1173, 1174, 1175, 1176, 1177,
    1178, 1179, 1180, 1181, 1182, 1183, 1184, 1185, 1186, 1187, 1188, 1189, 1190, 1191, 1192, 1193, 1194, 1195, 1196,
    1197, 1198, 1199, 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208, 1209, 1210, 1211, 1212, 1213, 1214, 1215,
    1216, 1046, 1078, 1219, 1220, 1221, 1222, 1223, 1224, 1225, 1226, 1227, 1228, 1229, 1230, 1231, 1040, 1072, 1040,
    1072, 1236, 1237, 1045, 1077, 1240, 1241, 1240, 1241, 1046, 1078, 1047, 1079, 1248, 1249, 1048, 1080, 1048, 1080,
    1054, 1086, 1256, 1257, 1256, 1257, 1069, 1101, 1059, 1091, 1059, 1091, 1059, 1091, 1063, 1095, 1270, 1271, 1067,
    1099, 1274, 1275, 1276, 1277, 1278, 1279};

static const int32 without_diacritics_ranges[] = {
    1280,   -1281,   1425,   0,       1470,   1470,    1471,   0,       1472,       1472,    1473,   0,
    1475,   1475,    1476,   0,       1478,   1478,    1479,   0,       1480,       -1481,   1536,   0,
    1542,   -1543,   1552,   0,       1563,   1563,    1564,   0,       1565,       -1566,   1570,   1575,
    1572,   1608,    1573,   1575,    1574,   1610,    1575,   -1576,   1611,       0,       1632,   -1633,
    1648,   0,       1649,   -1650,   1728,   1749,    1729,   2097154, 1732,       -1733,   1747,   2097152,
    1749,   1749,    1750,   0,       1758,   1758,    1759,   0,       1765,       -1766,   1767,   0,
    1769,   1769,    1770,   0,       1774,   -1775,   1807,   0,       1808,       1808,    1809,   0,
    1810,   -1811,   1840,   0,       1867,   -1868,   1958,   0,       1969,       -1970,   2027,   0,
    2036,   -2037,   2045,   0,       2046,   -2047,   2070,   0,       2074,       2074,    2075,   0,
    2084,   2084,    2085,   0,       2088,   2088,    2089,   0,       2094,       -2095,   2137,   0,
    2140,   -2141,   2192,   0,       2194,   -2195,   2199,   0,       2208,       -2209,   2250,   0,
    2308,   -2309,   2345,   2097152, 2347,   -2348,   2353,   2097152, 2355,       2097154, 2358,   -2359,
    2362,   0,       2365,   2365,    2366,   0,       2384,   2384,    2385,       0,       2392,   -2326,
    2395,   2332,    2396,   -2338,   2398,   2347,    2399,   2351,    2400,       -2401,   2402,   0,
    2404,   -2405,   2433,   0,       2436,   -2437,   2492,   0,       2493,       2493,    2494,   0,
    2501,   -2502,   2503,   0,       2505,   -2506,   2507,   0,       2510,       -2511,   2519,   0,
    2520,   -2521,   2524,   -2466,   2526,   2526,    2527,   2479,    2528,       -2529,   2530,   0,
    2532,   -2533,   2558,   0,       2559,   -2560,   2561,   0,       2564,       -2565,   2611,   2097152,
    2613,   2613,    2614,   2616,    2615,   -2616,   2620,   0,       2621,       2621,    2622,   0,
    2627,   -2628,   2631,   0,       2633,   -2634,   2635,   0,       2638,       -2639,   2641,   0,
    2642,   -2643,   2649,   -2583,   2651,   2588,    2652,   -2653,   2654,       2603,    2655,   -2656,
    2672,   0,       2674,   -2675,   2677,   0,       2678,   -2679,   2689,       0,       2692,   -2693,
    2748,   0,       2749,   2749,    2750,   0,       2758,   2758,    2759,       0,       2762,   2762,
    2763,   0,       2766,   -2767,   2786,   0,       2788,   -2789,   2810,       0,       2816,   2816,
    2817,   0,       2820,   -2821,   2876,   0,       2877,   2877,    2878,       0,       2885,   -2886,
    2887,   0,       2889,   -2890,   2891,   0,       2894,   -2895,   2901,       0,       2904,   -2905,
    2908,   -2850,   2910,   -2911,   2914,   0,       2916,   -2917,   2946,       0,       2947,   -2948,
    2964,   2962,    2965,   -2966,   3006,   0,       3011,   -3012,   3014,       0,       3017,   3017,
    3018,   0,       3022,   -3023,   3031,   0,       3032,   -3033,   3072,       0,       3077,   -3078,
    3132,   0,       3133,   3133,    3134,   0,       3141,   3141,    3142,       0,       3145,   3145,
    3146,   0,       3150,   -3151,   3157,   0,       3159,   -3160,   3170,       0,       3172,   -3173,
    3201,   0,       3204,   -3205,   3260,   0,       3261,   3261,    3262,       0,       3269,   3269,
    3270,   0,       3273,   3273,    3274,   0,       3278,   -3279,   3285,       0,       3287,   -3288,
    3298,   0,       3300,   -3301,   3315,   0,       3316,   -3317,   3328,       0,       3332,   -3333,
    3387,   0,       3389,   3389,    3390,   0,       3397,   3397,    3398,       0,       3401,   3401,
    3402,   0,       3406,   -3407,   3415,   0,       3416,   -3417,   3426,       0,       3428,   -3429,
    3457,   0,       3460,   -3461,   3530,   0,       3531,   -3532,   3535,       0,       3541,   3541,
    3542,   0,       3543,   3543,    3544,   0,       3552,   -3553,   3570,       0,       3572,   -3573,
    3633,   0,       3634,   3634,    3636,   0,       3643,   -3644,   3655,       0,       3663,   -3664,
    3761,   0,       3762,   3762,    3764,   0,       3773,   -3774,   3784,       0,       3791,   -3792,
    3852,   2097154, 3854,   -3855,   3864,   0,       3866,   -3867,   3893,       0,       3894,   3894,
    3895,   0,       3896,   3896,    3897,   0,       3898,   -3899,   3902,       0,       3904,   -3905,
    3907,   2097152, 3909,   -3910,   3917,   2097152, 3919,   -3920,   3922,       2097154, 3924,   -3925,
    3927,   2097152, 3929,   -3930,   3932,   2097154, 3934,   -3935,   3945,       3904,    3946,   -3947,
    3953,   0,       3973,   3973,    3974,   0,       3976,   -3977,   3981,       0,       3992,   3992,
    3993,   0,       4029,   -4030,   4038,   0,       4039,   -4040,   4134,       2097154, 4136,   -4137,
    4139,   0,       4159,   -4160,   4182,   0,       4186,   -4187,   4190,       0,       4193,   4193,
    4194,   0,       4197,   -4198,   4199,   0,       4206,   -4207,   4209,       0,       4213,   -4214,
    4226,   0,       4238,   4238,    4239,   0,       4240,   -4241,   4250,       0,       4254,   -4255,
    4348,   4316,    4349,   -4350,   4957,   0,       4960,   -4961,   5906,       0,       5910,   -5911,
    5938,   0,       5941,   -5942,   5970,   0,       5972,   -5973,   6002,       0,       6004,   -6005,
    6068,   0,       6100,   -6101,   6109,   0,       6110,   -6111,   6155,       0,       6160,   -6161,
    6277,   0,       6279,   -6280,   6313,   0,       6314,   -6315,   6432,       0,       6444,   -6445,
    6448,   0,       6460,   -6461,   6679,   0,       6684,   -6685,   6741,       0,       6751,   6751,
    6752,   0,       6781,   -6782,   6783,   0,       6784,   -6785,   6832,       0,       6863,   -6864,
    6912,   0,       6917,   2097154, 6928,   -6929,   6930,   2097154, 6932,       -6933,   6964,   0,
    6981,   -6982,   7019,   0,       7028,   -7029,   7040,   0,       7043,       -7044,   7073,   0,
    7086,   -7087,   7142,   0,       7156,   -7157,   7204,   0,       7224,       -7225,   7376,   0,
    7379,   7379,    7380,   0,       7401,   -7402,   7405,   0,       7406,       -7407,   7412,   0,
    7413,   -7414,   7415,   0,       7418,   -7419,   7468,   65,      7469,       198,     7470,   66,
    7471,   7471,    7472,   -69,     7474,   398,     7475,   -72,     7483,       7483,    7484,   79,
    7485,   546,     7486,   80,      7487,   82,      7488,   -85,     7490,       87,      7491,   97,
    7492,   -593,    7494,   7426,    7495,   98,      7496,   -101,    7498,       601,     7499,   -604,
    7501,   103,     7502,   7502,    7503,   107,     7504,   109,     7505,       331,     7506,   111,
    7507,   596,     7508,   -7447,   7510,   112,     7511,   -117,    7513,       7453,    7514,   623,
    7515,   118,     7516,   7461,    7517,   -947,    7520,   -967,    7522,       105,     7523,   114,
    7524,   -118,    7526,   -947,    7528,   961,     7529,   -967,    7531,       -7532,   7544,   1085,
    7545,   -7546,   7579,   594,     7580,   99,      7581,   597,     7582,       240,     7583,   604,
    7584,   102,     7585,   607,     7586,   609,     7587,   613,     7588,       -617,    7591,   7547,
    7592,   669,     7593,   621,     7594,   7557,    7595,   671,     7596,       625,     7597,   624,
    7598,   -627,    7602,   632,     7603,   -643,    7605,   427,     7606,       -650,    7608,   7452,
    7609,   -652,    7611,   122,     7612,   -657,    7615,   952,     7616,       0,       7680,   65,
    7681,   97,      7682,   66,      7683,   98,      7684,   66,      7685,       98,      7686,   66,
    7687,   98,      7688,   67,      7689,   99,      7690,   68,      7691,       100,     7692,   68,
    7693,   100,     7694,   68,      7695,   100,     7696,   68,      7697,       100,     7698,   68,
    7699,   100,     7700,   69,      7701,   101,     7702,   69,      7703,       101,     7704,   69,
    7705,   101,     7706,   69,      7707,   101,     7708,   69,      7709,       101,     7710,   70,
    7711,   102,     7712,   71,      7713,   103,     7714,   72,      7715,       104,     7716,   72,
    7717,   104,     7718,   72,      7719,   104,     7720,   72,      7721,       104,     7722,   72,
    7723,   104,     7724,   73,      7725,   105,     7726,   73,      7727,       105,     7728,   75,
    7729,   107,     7730,   75,      7731,   107,     7732,   75,      7733,       107,     7734,   76,
    7735,   108,     7736,   76,      7737,   108,     7738,   76,      7739,       108,     7740,   76,
    7741,   108,     7742,   77,      7743,   109,     7744,   77,      7745,       109,     7746,   77,
    7747,   109,     7748,   78,      7749,   110,     7750,   78,      7751,       110,     7752,   78,
    7753,   110,     7754,   78,      7755,   110,     7756,   79,      7757,       111,     7758,   79,
    7759,   111,     7760,   79,      7761,   111,     7762,   79,      7763,       111,     7764,   80,
    7765,   112,     7766,   80,      7767,   112,     7768,   82,      7769,       114,     7770,   82,
    7771,   114,     7772,   82,      7773,   114,     7774,   82,      7775,       114,     7776,   83,
    7777,   115,     7778,   83,      7779,   115,     7780,   83,      7781,       115,     7782,   83,
    7783,   115,     7784,   83,      7785,   115,     7786,   84,      7787,       116,     7788,   84,
    7789,   116,     7790,   84,      7791,   116,     7792,   84,      7793,       116,     7794,   85,
    7795,   117,     7796,   85,      7797,   117,     7798,   85,      7799,       117,     7800,   85,
    7801,   117,     7802,   85,      7803,   117,     7804,   86,      7805,       118,     7806,   86,
    7807,   118,     7808,   87,      7809,   119,     7810,   87,      7811,       119,     7812,   87,
    7813,   119,     7814,   87,      7815,   119,     7816,   87,      7817,       119,     7818,   88,
    7819,   120,     7820,   88,      7821,   120,     7822,   89,      7823,       121,     7824,   90,
    7825,   122,     7826,   90,      7827,   122,     7828,   90,      7829,       122,     7830,   104,
    7831,   116,     7832,   119,     7833,   121,     7834,   97,      7835,       115,     7836,   -7837,
    7840,   65,      7841,   97,      7842,   65,      7843,   97,      7844,       65,      7845,   97,
    7846,   65,      7847,   97,      7848,   65,      7849,   97,      7850,       65,      7851,   97,
    7852,   65,      7853,   97,      7854,   65,      7855,   97,      7856,       65,      7857,   97,
    7858,   65,      7859,   97,      7860,   65,      7861,   97,      7862,       65,      7863,   97,
    7864,   69,      7865,   101,     7866,   69,      7867,   101,     7868,       69,      7869,   101,
    7870,   69,      7871,   101,     7872,   69,      7873,   101,     7874,       69,      7875,   101,
    7876,   69,      7877,   101,     7878,   69,      7879,   101,     7880,       73,      7881,   105,
    7882,   73,      7883,   105,     7884,   79,      7885,   111,     7886,       79,      7887,   111,
    7888,   79,      7889,   111,     7890,   79,      7891,   111,     7892,       79,      7893,   111,
    7894,   79,      7895,   111,     7896,   79,      7897,   111,     7898,       79,      7899,   111,
    7900,   79,      7901,   111,     7902,   79,      7903,   111,     7904,       79,      7905,   111,
    7906,   79,      7907,   111,     7908,   85,      7909,   117,     7910,       85,      7911,   117,
    7912,   85,      7913,   117,     7914,   85,      7915,   117,     7916,       85,      7917,   117,
    7918,   85,      7919,   117,     7920,   85,      7921,   117,     7922,       89,      7923,   121,
    7924,   89,      7925,   121,     7926,   89,      7927,   121,     7928,       89,      7929,   121,
    7930,   -7931,   7936,   945,     7944,   913,     7952,   949,     7958,       -7959,   7960,   917,
    7966,   -7967,   7968,   951,     7976,   919,     7984,   953,     7992,       921,     8000,   959,
    8006,   -8007,   8008,   927,     8014,   -8015,   8016,   965,     8024,       8024,    8025,   933,
    8026,   8026,    8027,   933,     8028,   8028,    8029,   933,     8030,       8030,    8031,   933,
    8032,   969,     8040,   937,     8048,   945,     8050,   949,     8052,       951,     8054,   953,
    8056,   959,     8058,   965,     8060,   969,     8062,   -8063,   8064,       945,     8072,   913,
    8080,   951,     8088,   919,     8096,   969,     8104,   937,     8112,       945,     8117,   8117,
    8118,   945,     8120,   913,     8125,   32,      8126,   953,     8127,       32,      8130,   951,
    8133,   8133,    8134,   951,     8136,   917,     8138,   919,     8141,       32,      8144,   953,
    8148,   -8149,   8150,   953,     8152,   921,     8156,   8156,    8157,       32,      8160,   965,
    8164,   961,     8166,   965,     8168,   933,     8172,   929,     8173,       32,      8175,   96,
    8176,   -8177,   8178,   969,     8181,   8181,    8182,   969,     8184,       927,     8186,   937,
    8189,   32,      8191,   8191,    8192,   32,      8203,   0,       8208,       2097152, 8211,   -8212,
    8215,   32,      8216,   -8217,   8228,   46,      8229,   -8230,   8234,       0,       8239,   32,
    8240,   -8241,   8254,   32,      8255,   -8256,   8287,   32,      8288,       0,       8293,   8293,
    8294,   0,       8304,   48,      8305,   105,     8306,   -8307,   8308,       -53,     8314,   43,
    8315,   8722,    8316,   61,      8317,   -41,     8319,   110,     8320,       -49,     8330,   43,
    8331,   8722,    8332,   61,      8333,   -41,     8335,   8335,    8336,       97,      8337,   101,
    8338,   111,     8339,   120,     8340,   601,     8341,   104,     8342,       -108,    8346,   112,
    8347,   -116,    8349,   -8350,   8400,   0,       8433,   -8434,   8450,       67,      8452,   -8453,
    8455,   400,     8456,   8456,    8457,   70,      8458,   103,     8459,       72,      8462,   104,
    8463,   295,     8464,   73,      8466,   76,      8467,   108,     8468,       8468,    8469,   78,
    8470,   -8471,   8473,   -81,     8476,   82,      8478,   -8479,   8484,       90,      8485,   8485,
    8486,   937,     8487,   8487,    8488,   90,      8489,   8489,    8490,       75,      8491,   -66,
    8494,   8494,    8495,   101,     8496,   -70,     8498,   8498,    8499,       77,      8500,   111,
    8501,   -1489,   8505,   105,     8506,   -8507,   8508,   960,     8509,       947,     8510,   915,
    8511,   928,     8512,   8721,    8513,   -8514,   8517,   68,      8518,       -101,    8520,   -106,
    8522,   -8523,   8543,   49,      8544,   73,      8545,   -8546,   8548,       86,      8549,   -8550,
    8553,   88,      8554,   -8555,   8556,   76,      8557,   -68,     8559,       77,      8560,   105,
    8561,   -8562,   8564,   118,     8565,   -8566,   8569,   120,     8570,       -8571,   8572,   108,
    8573,   -100,    8575,   109,     8576,   -8577,   8602,   8592,    8603,       8594,    8604,   -8605,
    8622,   8596,    8623,   -8624,   8653,   8656,    8654,   8660,    8655,       8658,    8656,   -8657,
    8708,   2097154, 8710,   -8711,   8713,   2097152, 8715,   2097154, 8718,       -8719,   8740,   2097154,
    8744,   -8745,   8769,   8764,    8770,   -8771,   8772,   2097154, 8774,       8774,    8775,   8773,
    8776,   2097152, 8779,   -8780,   8800,   61,      8801,   2097154, 8804,       -8805,   8813,   8781,
    8814,   60,      8815,   62,      8816,   -8805,   8818,   -8819,   8820,       -8819,   8822,   -8823,
    8824,   -8823,   8826,   -8827,   8832,   -8827,   8834,   -8835,   8836,       -8835,   8838,   -8839,
    8840,   -8839,   8842,   -8843,   8876,   8866,    8877,   -8873,   8879,       8875,    8880,   -8881,
    8928,   -8829,   8930,   -8850,   8932,   -8933,   8938,   -8883,   8942,       -8943,   9001,   -12297,
    9003,   -9004,   9312,   -50,     9321,   -9322,   9352,   -50,     9361,       -9362,   9398,   -66,
    9424,   -98,     9450,   48,      9451,   -9452,   10972,  10973,   10974,      -10975,  11388,  106,
    11389,  86,      11390,  -11391,  11503,  0,       11506,  -11507,  11631,      11617,   11632,  -11633,
    11647,  0,       11648,  -11649,  11744,  0,       11776,  -11777,  11935,      27597,   11936,  -11937,
    12019,  40863,   12020,  -12021,  12032,  19968,   12033,  20008,   12034,      20022,   12035,  20031,
    12036,  20057,   12037,  20101,   12038,  20108,   12039,  20128,   12040,      20154,   12041,  20799,
    12042,  20837,   12043,  20843,   12044,  20866,   12045,  20886,   12046,      20907,   12047,  20960,
    12048,  20981,   12049,  20992,   12050,  21147,   12051,  21241,   12052,      21269,   12053,  21274,
    12054,  21304,   12055,  21313,   12056,  21340,   12057,  21353,   12058,      21378,   12059,  21430,
    12060,  21448,   12061,  21475,   12062,  22231,   12063,  22303,   12064,      22763,   12065,  22786,
    12066,  22794,   12067,  22805,   12068,  22823,   12069,  22899,   12070,      23376,   12071,  23424,
    12072,  23544,   12073,  23567,   12074,  23586,   12075,  23608,   12076,      23662,   12077,  23665,
    12078,  24027,   12079,  24037,   12080,  24049,   12081,  24062,   12082,      24178,   12083,  24186,
    12084,  24191,   12085,  24308,   12086,  24318,   12087,  24331,   12088,      24339,   12089,  24400,
    12090,  24417,   12091,  24435,   12092,  24515,   12093,  25096,   12094,      25142,   12095,  25163,
    12096,  25903,   12097,  25908,   12098,  25991,   12099,  26007,   12100,      26020,   12101,  26041,
    12102,  26080,   12103,  26085,   12104,  26352,   12105,  26376,   12106,      26408,   12107,  27424,
    12108,  27490,   12109,  27513,   12110,  27571,   12111,  27595,   12112,      27604,   12113,  27611,
    12114,  27663,   12115,  27668,   12116,  27700,   12117,  28779,   12118,      29226,   12119,  29238,
    12120,  29243,   12121,  29247,   12122,  29255,   12123,  29273,   12124,      29275,   12125,  29356,
    12126,  29572,   12127,  29577,   12128,  29916,   12129,  29926,   12130,      29976,   12131,  29983,
    12132,  29992,   12133,  30000,   12134,  30091,   12135,  30098,   12136,      30326,   12137,  30333,
    12138,  30382,   12139,  30399,   12140,  30446,   12141,  30683,   12142,      30690,   12143,  30707,
    12144,  31034,   12145,  31160,   12146,  31166,   12147,  31348,   12148,      31435,   12149,  31481,
    12150,  31859,   12151,  31992,   12152,  32566,   12153,  32593,   12154,      32650,   12155,  32701,
    12156,  32769,   12157,  32780,   12158,  32786,   12159,  32819,   12160,      32895,   12161,  32905,
    12162,  33251,   12163,  33258,   12164,  33267,   12165,  33276,   12166,      33292,   12167,  33307,
    12168,  33311,   12169,  33390,   12170,  33394,   12171,  33400,   12172,      34381,   12173,  34411,
    12174,  34880,   12175,  34892,   12176,  34915,   12177,  35198,   12178,      35211,   12179,  35282,
    12180,  35328,   12181,  35895,   12182,  35910,   12183,  35925,   12184,      35960,   12185,  35997,
    12186,  36196,   12187,  36208,   12188,  36275,   12189,  36523,   12190,      36554,   12191,  36763,
    12192,  36784,   12193,  36789,   12194,  37009,   12195,  37193,   12196,      37318,   12197,  37324,
    12198,  37329,   12199,  38263,   12200,  38272,   12201,  38428,   12202,      38582,   12203,  38585,
    12204,  38632,   12205,  38737,   12206,  38750,   12207,  38754,   12208,      38761,   12209,  38859,
    12210,  38893,   12211,  38899,   12212,  38913,   12213,  39080,   12214,      39131,   12215,  39135,
    12216,  39318,   12217,  39321,   12218,  39340,   12219,  39592,   12220,      39640,   12221,  39647,
    12222,  39717,   12223,  39727,   12224,  39730,   12225,  39740,   12226,      39770,   12227,  40165,
    12228,  40565,   12229,  40575,   12230,  40613,   12231,  40635,   12232,      40643,   12233,  40653,
    12234,  40657,   12235,  40697,   12236,  40701,   12237,  40718,   12238,      40723,   12239,  40736,
    12240,  40763,   12241,  40778,   12242,  40786,   12243,  40845,   12244,      40860,   12245,  40864,
    12246,  -12247,  12288,  32,      12289,  -12290,  12330,  0,       12336,      -12337,  12342,  12306,
    12343,  12343,   12344,  21313,   12345,  -21317,  12347,  -12348,  12364,      2097154, 12388,  2097152,
    12395,  -12396,  12400,  12399,   12402,  12402,   12405,  12405,   12408,      12408,   12411,  12411,
    12414,  -12415,  12436,  12358,   12437,  -12438,  12441,  0,       12443,      32,      12445,  2097154,
    12448,  -12449,  12460,  2097154, 12484,  2097152, 12491,  -12492,  12496,      12495,   12498,  12498,
    12501,  12501,   12504,  12504,   12507,  12507,   12510,  -12511,  12532,      12454,   12533,  -12534,
    12535,  -12528,  12539,  12539,   12540,  0,       12541,  2097154, 12544,      -12545,  12593,  -4353,
    12595,  4522,    12596,  4354,    12597,  -4525,   12599,  -4356,   12602,      -4529,   12608,  4378,
    12609,  -4359,   12612,  4385,    12613,  -4362,   12623,  -4450,   12644,      4448,    12645,  -4373,
    12647,  -4552,   12649,  4556,    12650,  4558,    12651,  4563,    12652,      4567,    12653,  4569,
    12654,  4380,    12655,  4573,    12656,  4575,    12657,  -4382,   12659,      4384,    12660,  -4387,
    12662,  4391,    12663,  4393,    12664,  -4396,   12669,  4402,    12670,      4406,    12671,  4416,
    12672,  4423,    12673,  4428,    12674,  -4594,   12676,  -4440,   12679,      -4485,   12681,  4488,
    12682,  -4498,   12684,  4500,    12685,  4510,    12686,  4513,    12687,      -12688,  12690,  19968,
    12691,  20108,   12692,  19977,   12693,  22235,   12694,  19978,   12695,      20013,   12696,  19979,
    12697,  30002,   12698,  20057,   12699,  19993,   12700,  19969,   12701,      22825,   12702,  22320,
    12703,  20154,   12704,  -12705,  12868,  21839,   12869,  24188,   12870,      25991,   12871,  31631,
    12872,  -12873,  12896,  4352,    12897,  -4355,   12899,  -4358,   12902,      4361,    12903,  -4364,
    12905,  -4367,   12910,  -12911,  12928,  19968,   12929,  20108,   12930,      19977,   12931,  22235,
    12932,  20116,   12933,  20845,   12934,  19971,   12935,  20843,   12936,      20061,   12937,  21313,
    12938,  26376,   12939,  28779,   12940,  27700,   12941,  26408,   12942,      37329,   12943,  22303,
    12944,  26085,   12945,  26666,   12946,  26377,   12947,  31038,   12948,      21517,   12949,  29305,
    12950,  36001,   12951,  31069,   12952,  21172,   12953,  31192,   12954,      30007,   12955,  22899,
    12956,  36969,   12957,  20778,   12958,  21360,   12959,  27880,   12960,      38917,   12961,  20241,
    12962,  20889,   12963,  27491,   12964,  19978,   12965,  20013,   12966,      19979,   12967,  24038,
    12968,  21491,   12969,  21307,   12970,  23447,   12971,  23398,   12972,      30435,   12973,  20225,
    12974,  36039,   12975,  21332,   12976,  22812,   12977,  -12978,  13008,      12450,   13009,  12452,
    13010,  12454,   13011,  12456,   13012,  -12459,  13014,  12461,   13015,      12463,   13016,  12465,
    13017,  12467,   13018,  12469,   13019,  12471,   13020,  12473,   13021,      12475,   13022,  12477,
    13023,  12479,   13024,  12481,   13025,  12484,   13026,  12486,   13027,      12488,   13028,  -12491,
    13034,  12498,   13035,  12501,   13036,  12504,   13037,  12507,   13038,      -12511,  13043,  12516,
    13044,  12518,   13045,  -12521,  13051,  -12528,  13055,  -13056,  42607,      0,       42611,  42611,
    42612,  0,       42622,  -42623,  42652,  1098,    42653,  1100,    42654,      0,       42656,  -42657,
    42736,  0,       42738,  -42739,  42864,  2097154, 42866,  -42867,  42994,      67,      42995,  70,
    42996,  81,      42997,  -42998,  43000,  294,     43001,  339,     43002,      -43003,  43010,  0,
    43011,  -43012,  43014,  0,       43015,  -43016,  43019,  0,       43020,      -43021,  43043,  0,
    43048,  -43049,  43052,  0,       43053,  -43054,  43136,  0,       43138,      -43139,  43188,  0,
    43206,  -43207,  43232,  0,       43250,  -43251,  43263,  0,       43264,      -43265,  43302,  0,
    43310,  -43311,  43335,  0,       43348,  -43349,  43392,  0,       43396,      -43397,  43443,  0,
    43457,  -43458,  43493,  0,       43494,  -43495,  43561,  0,       43575,      -43576,  43587,  0,
    43588,  -43589,  43596,  0,       43598,  -43599,  43643,  0,       43646,      -43647,  43696,  0,
    43697,  43697,   43698,  0,       43701,  -43702,  43703,  0,       43705,      -43706,  43710,  0,
    43712,  43712,   43713,  0,       43714,  -43715,  43755,  0,       43760,      -43761,  43765,  0,
    43767,  -43768,  43868,  42791,   43869,  43831,   43870,  619,     43871,      43858,   43872,  -43873,
    43881,  653,     43882,  -43883,  44003,  0,       44011,  44011,   44012,      0,       44014,  -44015,
    55296,  0,       57344,  -57345,  63744,  35912,   63745,  26356,   63746,      36554,   63747,  36040,
    63748,  28369,   63749,  20018,   63750,  21477,   63751,  40860,   63753,      22865,   63754,  37329,
    63755,  21895,   63756,  22856,   63757,  25078,   63758,  30313,   63759,      32645,   63760,  34367,
    63761,  34746,   63762,  35064,   63763,  37007,   63764,  27138,   63765,      27931,   63766,  28889,
    63767,  29662,   63768,  33853,   63769,  37226,   63770,  39409,   63771,      20098,   63772,  21365,
    63773,  27396,   63774,  29211,   63775,  34349,   63776,  40478,   63777,      23888,   63778,  28651,
    63779,  34253,   63780,  35172,   63781,  25289,   63782,  33240,   63783,      34847,   63784,  24266,
    63785,  26391,   63786,  28010,   63787,  29436,   63788,  37070,   63789,      20358,   63790,  20919,
    63791,  21214,   63792,  25796,   63793,  27347,   63794,  29200,   63795,      30439,   63796,  32769,
    63797,  34310,   63798,  34396,   63799,  36335,   63800,  38706,   63801,      39791,   63802,  40442,
    63803,  30860,   63804,  31103,   63805,  32160,   63806,  33737,   63807,      37636,   63808,  40575,
    63809,  35542,   63810,  22751,   63811,  24324,   63812,  31840,   63813,      32894,   63814,  29282,
    63815,  30922,   63816,  36034,   63817,  38647,   63818,  22744,   63819,      23650,   63820,  27155,
    63821,  28122,   63822,  28431,   63823,  32047,   63824,  32311,   63825,      38475,   63826,  21202,
    63827,  32907,   63828,  20956,   63829,  20940,   63830,  31260,   63831,      32190,   63832,  33777,
    63833,  38517,   63834,  35712,   63835,  25295,   63836,  27138,   63837,      35582,   63838,  20025,
    63839,  23527,   63840,  24594,   63841,  29575,   63842,  30064,   63843,      21271,   63844,  30971,
    63845,  20415,   63846,  24489,   63847,  19981,   63848,  27852,   63849,      25976,   63850,  32034,
    63851,  21443,   63852,  22622,   63853,  30465,   63854,  33865,   63855,      35498,   63856,  27578,
    63857,  36784,   63858,  27784,   63859,  25342,   63860,  33509,   63861,      25504,   63862,  30053,
    63863,  20142,   63864,  20841,   63865,  20937,   63866,  26753,   63867,      31975,   63868,  33391,
    63869,  35538,   63870,  37327,   63871,  21237,   63872,  21570,   63873,      22899,   63874,  24300,
    63875,  26053,   63876,  28670,   63877,  31018,   63878,  38317,   63879,      39530,   63880,  40599,
    63881,  40654,   63882,  21147,   63883,  26310,   63884,  27511,   63885,      36706,   63886,  24180,
    63887,  24976,   63888,  25088,   63889,  25754,   63890,  28451,   63891,      29001,   63892,  29833,
    63893,  31178,   63894,  32244,   63895,  32879,   63896,  36646,   63897,      34030,   63898,  36899,
    63899,  37706,   63900,  21015,   63901,  21155,   63902,  21693,   63903,      28872,   63904,  35010,
    63905,  35498,   63906,  24265,   63907,  24565,   63908,  25467,   63909,      27566,   63910,  31806,
    63911,  29557,   63912,  20196,   63913,  22265,   63914,  23527,   63915,      23994,   63916,  24604,
    63917,  29618,   63918,  29801,   63919,  32666,   63920,  32838,   63921,      37428,   63922,  38646,
    63923,  38728,   63924,  38936,   63925,  20363,   63926,  31150,   63927,      37300,   63928,  38584,
    63929,  24801,   63930,  20102,   63931,  20698,   63932,  23534,   63933,      23615,   63934,  26009,
    63935,  27138,   63936,  29134,   63937,  30274,   63938,  34044,   63939,      36988,   63940,  40845,
    63941,  26248,   63942,  38446,   63943,  21129,   63944,  26491,   63945,      26611,   63946,  27969,
    63947,  28316,   63948,  29705,   63949,  30041,   63950,  30827,   63951,      32016,   63952,  39006,
    63953,  20845,   63954,  25134,   63955,  38520,   63956,  20523,   63957,      23833,   63958,  28138,
    63959,  36650,   63960,  24459,   63961,  24900,   63962,  26647,   63963,      29575,   63964,  38534,
    63965,  21033,   63966,  21519,   63967,  23653,   63968,  26131,   63969,      26446,   63970,  26792,
    63971,  27877,   63972,  29702,   63973,  30178,   63974,  32633,   63975,      35023,   63976,  35041,
    63977,  37324,   63978,  38626,   63979,  21311,   63980,  28346,   63981,      21533,   63982,  29136,
    63983,  29848,   63984,  34298,   63985,  38563,   63986,  40023,   63987,      40607,   63988,  26519,
    63989,  28107,   63990,  33256,   63991,  31435,   63992,  31520,   63993,      31890,   63994,  29376,
    63995,  28825,   63996,  35672,   63997,  20160,   63998,  33590,   63999,      21050,   64000,  20999,
    64001,  24230,   64002,  25299,   64003,  31958,   64004,  23429,   64005,      27934,   64006,  26292,
    64007,  36667,   64008,  34892,   64009,  38477,   64010,  35211,   64011,      24275,   64012,  20800,
    64013,  21952,   64014,  -64015,  64016,  22618,   64017,  64017,   64018,      26228,   64019,  -64020,
    64021,  20958,   64022,  29482,   64023,  30410,   64024,  31036,   64025,      31070,   64026,  31077,
    64027,  31119,   64028,  38742,   64029,  31934,   64030,  32701,   64031,      64031,   64032,  34322,
    64033,  64033,   64034,  35576,   64035,  -64036,  64037,  36920,   64038,      37117,   64039,  -64040,
    64042,  39151,   64043,  39164,   64044,  39208,   64045,  40372,   64046,      37086,   64047,  38583,
    64048,  20398,   64049,  20711,   64050,  20813,   64051,  21193,   64052,      21220,   64053,  21329,
    64054,  21917,   64055,  22022,   64056,  22120,   64057,  22592,   64058,      22696,   64059,  23652,
    64060,  23662,   64061,  24724,   64062,  24936,   64063,  24974,   64064,      25074,   64065,  25935,
    64066,  26082,   64067,  26257,   64068,  26757,   64069,  28023,   64070,      28186,   64071,  28450,
    64072,  29038,   64073,  29227,   64074,  29730,   64075,  30865,   64076,      31038,   64077,  31049,
    64078,  31048,   64079,  31056,   64080,  31062,   64081,  31069,   64082,      -31118,  64084,  31296,
    64085,  31361,   64086,  31680,   64087,  32244,   64088,  32265,   64089,      32321,   64090,  32626,
    64091,  32773,   64092,  33261,   64093,  33401,   64095,  33879,   64096,      35088,   64097,  35222,
    64098,  35585,   64099,  35641,   64100,  36051,   64101,  36104,   64102,      36790,   64103,  36920,
    64104,  38627,   64105,  38911,   64106,  38971,   64107,  24693,   64108,      148206,  64109,  33304,
    64110,  -64111,  64112,  20006,   64113,  20917,   64114,  20840,   64115,      20352,   64116,  20805,
    64117,  20864,   64118,  21191,   64119,  21242,   64120,  21917,   64121,      21845,   64122,  21913,
    64123,  21986,   64124,  22618,   64125,  22707,   64126,  22852,   64127,      22868,   64128,  23138,
    64129,  23336,   64130,  24274,   64131,  24281,   64132,  24425,   64133,      24493,   64134,  24792,
    64135,  24910,   64136,  24840,   64137,  24974,   64138,  24928,   64139,      25074,   64140,  25140,
    64141,  25540,   64142,  25628,   64143,  25682,   64144,  25942,   64145,      26228,   64146,  26391,
    64147,  26395,   64148,  26454,   64149,  27513,   64150,  27578,   64151,      27969,   64152,  28379,
    64153,  28363,   64154,  28450,   64155,  28702,   64156,  29038,   64157,      30631,   64158,  29237,
    64159,  29359,   64160,  29482,   64161,  29809,   64162,  29958,   64163,      30011,   64164,  30237,
    64165,  30239,   64166,  30410,   64167,  30427,   64168,  30452,   64169,      30538,   64170,  30528,
    64171,  30924,   64172,  31409,   64173,  31680,   64174,  31867,   64175,      32091,   64176,  32244,
    64177,  32574,   64178,  32773,   64179,  33618,   64180,  33775,   64181,      34681,   64182,  35137,
    64183,  35206,   64184,  35222,   64185,  35519,   64186,  35576,   64187,      35531,   64188,  35585,
    64189,  35582,   64190,  35565,   64191,  35641,   64192,  35722,   64193,      36104,   64194,  36664,
    64195,  36978,   64196,  37273,   64197,  37494,   64198,  38524,   64199,      38627,   64200,  38742,
    64201,  38875,   64202,  38911,   64203,  38923,   64204,  38971,   64205,      39698,   64206,  40860,
    64207,  141386,  64208,  141380,  64209,  144341,  64210,  15261,   64211,      16408,   64212,  16441,
    64213,  152137,  64214,  154832,  64215,  163539,  64216,  40771,   64217,      40846,   64218,  -64219,
    64285,  1497,    64286,  0,       64287,  1522,    64288,  1506,    64289,      1488,    64290,  -1492,
    64292,  -1500,   64295,  1512,    64296,  1514,    64297,  43,      64298,      1513,    64302,  1488,
    64305,  -1490,   64311,  64311,   64312,  -1497,   64317,  64317,   64318,      1502,    64319,  64319,
    64320,  -1505,   64322,  64322,   64323,  -1508,   64325,  64325,   64326,      -1511,   64331,  1493,
    64332,  1489,    64333,  1499,    64334,  1508,    64335,  64335,   64336,      1649,    64338,  1659,
    64342,  1662,    64346,  1664,    64350,  1658,    64354,  1663,    64358,      1657,    64362,  1700,
    64366,  1702,    64370,  1668,    64374,  1667,    64378,  1670,    64382,      1671,    64386,  1677,
    64388,  1676,    64390,  1678,    64392,  1672,    64394,  1688,    64396,      1681,    64398,  1705,
    64402,  1711,    64406,  1715,    64410,  1713,    64414,  1722,    64416,      1723,    64420,  1749,
    64422,  1729,    64426,  1726,    64430,  1746,    64434,  -64435,  64467,      1709,    64471,  1735,
    64473,  1734,    64475,  1736,    64477,  1655,    64478,  1739,    64480,      1733,    64482,  1737,
    64484,  1744,    64488,  1609,    64490,  -64491,  64508,  1740,    64512,      -64513,  64603,  -1585,
    64605,  1609,    64606,  32,      64612,  -64613,  64656,  1609,    64657,      -64658,  64729,  1607,
    64730,  -64731,  64754,  1600,    64757,  -64758,  64828,  1575,    64830,      -64831,  65024,  0,
    65040,  44,      65041,  -12290,  65043,  -59,     65045,  33,      65046,      63,      65047,  -12311,
    65049,  8230,    65050,  -65051,  65056,  0,       65072,  8229,    65073,      8212,    65074,  8211,
    65075,  95,      65077,  -41,     65079,  123,     65080,  125,     65081,      -12309,  65083,  -12305,
    65085,  -12299,  65087,  -12297,  65089,  -12301,  65093,  -65094,  65095,      91,      65096,  93,
    65097,  32,      65101,  95,      65104,  44,      65105,  12289,   65106,      46,      65107,  65107,
    65108,  59,      65109,  58,      65110,  63,      65111,  33,      65112,      8212,    65113,  -41,
    65115,  123,     65116,  125,     65117,  -12309,  65119,  35,      65120,      38,      65121,  -43,
    65123,  45,      65124,  60,      65125,  62,      65126,  61,      65127,      65127,   65128,  92,
    65129,  -37,     65131,  64,      65132,  -65133,  65136,  32,      65137,      1600,    65138,  32,
    65139,  65139,   65140,  32,      65141,  65141,   65142,  32,      65143,      1600,    65144,  32,
    65145,  1600,    65146,  32,      65147,  1600,    65148,  32,      65149,      1600,    65150,  32,
    65151,  1600,    65152,  1569,    65153,  1575,    65157,  1608,    65159,      1575,    65161,  1610,
    65165,  1575,    65167,  1576,    65171,  1577,    65173,  1578,    65177,      1579,    65181,  1580,
    65185,  1581,    65189,  1582,    65193,  1583,    65195,  1584,    65197,      1585,    65199,  1586,
    65201,  1587,    65205,  1588,    65209,  1589,    65213,  1590,    65217,      1591,    65221,  1592,
    65225,  1593,    65229,  1594,    65233,  1601,    65237,  1602,    65241,      1603,    65245,  1604,
    65249,  1605,    65253,  1606,    65257,  1607,    65261,  1608,    65263,      1609,    65265,  1610,
    65269,  -65270,  65279,  0,       65280,  65280,   65281,  -34,     65375,      -10630,  65377,  12290,
    65378,  -12301,  65380,  12289,   65381,  12539,   65382,  12530,   65383,      12449,   65384,  12451,
    65385,  12453,   65386,  12455,   65387,  12457,   65388,  12515,   65389,      12517,   65390,  12519,
    65391,  12483,   65392,  65392,   65393,  12450,   65394,  12452,   65395,      12454,   65396,  12456,
    65397,  -12459,  65399,  12461,   65400,  12463,   65401,  12465,   65402,      12467,   65403,  12469,
    65404,  12471,   65405,  12473,   65406,  12475,   65407,  12477,   65408,      12479,   65409,  12481,
    65410,  12484,   65411,  12486,   65412,  12488,   65413,  -12491,  65419,      12498,   65420,  12501,
    65421,  12504,   65422,  12507,   65423,  -12511,  65428,  12516,   65429,      12518,   65430,  -12521,
    65436,  12527,   65437,  12531,   65438,  -65439,  65440,  4448,    65441,      -4353,   65443,  4522,
    65444,  4354,    65445,  -4525,   65447,  -4356,   65450,  -4529,   65456,      4378,    65457,  -4359,
    65460,  4385,    65461,  -4362,   65471,  -65472,  65474,  -4450,   65480,      -65481,  65482,  -4456,
    65488,  -65489,  65490,  -4462,   65496,  -65497,  65498,  -4468,   65501,      -65502,  65504,  -163,
    65506,  172,     65507,  32,      65508,  166,     65509,  165,     65510,      8361,    65511,  65511,
    65512,  9474,    65513,  -8593,   65517,  9632,    65518,  9675,    65519,      -65520,  65529,  0,
    65532,  -65533,  66045,  0,       66046,  -66047,  66272,  0,       66273,      -66274,  66422,  0,
    66427,  -66428,  67017,  67026,   67018,  -67019,  67044,  67034,   67045,      -67046,  67457,  -721,
    67459,  230,     67460,  665,     67461,  595,     67462,  67462,   67463,      675,     67464,  43878,
    67465,  677,     67466,  676,     67467,  -599,    67469,  7569,    67470,      600,     67471,  606,
    67472,  681,     67473,  612,     67474,  610,     67475,  608,     67476,      667,     67477,  295,
    67478,  668,     67479,  615,     67480,  644,     67481,  -683,    67483,      620,     67484,  122628,
    67485,  42894,   67486,  622,     67487,  122629,  67488,  654,     67489,      122630,  67490,  248,
    67491,  -631,    67493,  113,     67494,  634,     67495,  122632,  67496,      -638,    67498,  640,
    67499,  680,     67500,  678,     67501,  43879,   67502,  679,     67503,      648,     67504,  11377,
    67505,  67505,   67506,  655,     67507,  -674,    67509,  664,     67510,      -449,    67513,  122634,
    67514,  122654,  67515,  -67516,  68097,  0,       68100,  68100,   68101,      0,       68103,  -68104,
    68108,  0,       68112,  -68113,  68152,  0,       68155,  -68156,  68159,      0,       68160,  -68161,
    68325,  0,       68327,  -68328,  68900,  0,       68904,  -68905,  68969,      0,       68974,  -68975,
    69291,  0,       69293,  -69294,  69372,  0,       69376,  -69377,  69446,      0,       69457,  -69458,
    69506,  0,       69510,  -69511,  69632,  0,       69635,  -69636,  69688,      0,       69703,  -69704,
    69744,  0,       69745,  -69746,  69747,  0,       69749,  -69750,  69759,      0,       69763,  -69764,
    69786,  2097154, 69790,  -69791,  69803,  69797,   69804,  -69805,  69808,      0,       69819,  -69820,
    69821,  0,       69822,  -69823,  69826,  0,       69827,  -69828,  69837,      0,       69838,  -69839,
    69888,  0,       69891,  -69892,  69927,  0,       69941,  -69942,  69957,      0,       69959,  -69960,
    70003,  0,       70004,  -70005,  70016,  0,       70019,  -70020,  70067,      0,       70081,  -70082,
    70089,  0,       70093,  70093,   70094,  0,       70096,  -70097,  70188,      0,       70200,  -70201,
    70206,  0,       70207,  -70208,  70209,  0,       70210,  -70211,  70367,      0,       70379,  -70380,
    70400,  0,       70404,  -70405,  70459,  0,       70461,  70461,   70462,      0,       70469,  -70470,
    70471,  0,       70473,  -70474,  70475,  0,       70478,  -70479,  70487,      0,       70488,  -70489,
    70498,  0,       70500,  -70501,  70502,  0,       70509,  -70510,  70512,      0,       70517,  -70518,
    70531,  2097152, 70535,  -70536,  70542,  70539,   70543,  -70544,  70545,      2097152, 70547,  -70548,
    70584,  0,       70593,  70593,   70594,  0,       70595,  -70596,  70597,      0,       70598,  70598,
    70599,  0,       70603,  70603,   70604,  0,       70609,  70609,   70610,      0,       70611,  -70612,
    70625,  0,       70627,  -70628,  70709,  0,       70727,  -70728,  70750,      0,       70751,  -70752,
    70832,  0,       70852,  -70853,  71087,  0,       71094,  -71095,  71096,      0,       71105,  -71106,
    71132,  0,       71134,  -71135,  71216,  0,       71233,  -71234,  71339,      0,       71352,  -71353,
    71453,  0,       71468,  -71469,  71724,  0,       71739,  -71740,  71984,      0,       71990,  71990,
    71991,  0,       71993,  -71994,  71995,  0,       71999,  71999,   72000,      0,       72001,  72001,
    72002,  0,       72004,  -72005,  72145,  0,       72152,  -72153,  72154,      0,       72161,  -72162,
    72164,  0,       72165,  -72166,  72193,  0,       72203,  -72204,  72243,      0,       72250,  72250,
    72251,  0,       72255,  -72256,  72263,  0,       72264,  -72265,  72273,      0,       72284,  -72285,
    72330,  0,       72346,  -72347,  72751,  0,       72759,  72759,   72760,      0,       72768,  -72769,
    72850,  0,       72872,  72872,   72873,  0,       72887,  -72888,  73009,      0,       73015,  -73016,
    73018,  0,       73019,  73019,   73020,  0,       73022,  73022,   73023,      0,       73030,  73030,
    73031,  0,       73032,  -73033,  73098,  0,       73103,  73103,   73104,      0,       73106,  73106,
    73107,  0,       73112,  -73113,  73459,  0,       73463,  -73464,  73472,      0,       73474,  73474,
    73475,  0,       73476,  -73477,  73524,  0,       73531,  -73532,  73534,      0,       73539,  -73540,
    73562,  0,       73563,  -73564,  78896,  0,       78913,  -78914,  78919,      0,       78934,  -78935,
    90398,  0,       90416,  -90417,  92912,  0,       92917,  -92918,  92976,      0,       92983,  -92984,
    94031,  0,       94032,  94032,   94033,  0,       94088,  -94089,  94095,      0,       94099,  -94100,
    94180,  0,       94181,  -94182,  94192,  0,       94194,  -94195,  113821,     0,       113823, 113823,
    113824, 0,       113828, -113829, 117974, -66,     118000, -49,     118010,     -118011, 118528, 0,
    118574, -118575, 118576, 0,       118599, -118600, 119134, -119128, 119136,     119128,  119141, 0,
    119146, -119147, 119149, 0,       119171, -119172, 119173, 0,       119180,     -119181, 119210, 0,
    119214, -119215, 119227, -119226, 119229, -119226, 119231, -119226, 119233,     -119234, 119362, 0,
    119365, -119366, 119808, -66,     119834, -98,     119860, -66,     119886,     -98,     119893, 119893,
    119894, -106,    119912, -66,     119938, -98,     119964, 65,      119965,     119965,  119966, -68,
    119968, -119969, 119970, 71,      119971, -119972, 119973, -75,     119975,     -119976, 119977, -79,
    119981, 119981,  119982, -84,     119990, -98,     119994, 119994,  119995,     102,     119996, 119996,
    119997, -105,    120004, 120004,  120005, -113,    120016, -66,     120042,     -98,     120068, -66,
    120070, 120070,  120071, -69,     120075, -120076, 120077, -75,     120085,     120085,  120086, -84,
    120093, 120093,  120094, -98,     120120, -66,     120122, 120122,  120123,     -69,     120127, 120127,
    120128, -74,     120133, 120133,  120134, 79,      120135, -120136, 120138,     -84,     120145, 120145,
    120146, -98,     120172, -66,     120198, -98,     120224, -66,     120250,     -98,     120276, -66,
    120302, -98,     120328, -66,     120354, -98,     120380, -66,     120406,     -98,     120432, -66,
    120458, -98,     120484, 305,     120485, 567,     120486, -120487, 120488,     -914,    120505, 920,
    120506, -932,    120513, 8711,    120514, -946,    120539, 8706,    120540,     949,     120541, 952,
    120542, 954,     120543, 966,     120544, 961,     120545, 960,     120546,     -914,    120563, 920,
    120564, -932,    120571, 8711,    120572, -946,    120597, 8706,    120598,     949,     120599, 952,
    120600, 954,     120601, 966,     120602, 961,     120603, 960,     120604,     -914,    120621, 920,
    120622, -932,    120629, 8711,    120630, -946,    120655, 8706,    120656,     949,     120657, 952,
    120658, 954,     120659, 966,     120660, 961,     120661, 960,     120662,     -914,    120679, 920,
    120680, -932,    120687, 8711,    120688, -946,    120713, 8706,    120714,     949,     120715, 952,
    120716, 954,     120717, 966,     120718, 961,     120719, 960,     120720,     -914,    120737, 920,
    120738, -932,    120745, 8711,    120746, -946,    120771, 8706,    120772,     949,     120773, 952,
    120774, 954,     120775, 966,     120776, 961,     120777, 960,     120778,     -989,    120780, -120781,
    120782, -49,     120792, -49,     120802, -49,     120812, -49,     120822,     -49,     120832, -120833,
    121344, 0,       121399, -121400, 121403, 0,       121453, -121454, 121461,     0,       121462, -121463,
    121476, 0,       121477, -121478, 121499, 0,       121504, 121504,  121505,     0,       121520, -121521,
    122880, 0,       122887, 122887,  122888, 0,       122905, -122906, 122907,     0,       122914, 122914,
    122915, 0,       122917, 122917,  122918, 0,       122923, -122924, 122928,     -1073,   122937, -1083,
    122940, -1087,   122951, 1099,    122952, -1102,   122954, 42633,   122955,     1241,    122956, 1110,
    122957, 1112,    122958, 1257,    122959, 1199,    122960, 1231,    122961,     -1073,   122970, -1083,
    122972, -1087,   122974, 1089,    122975, -1092,   122981, -1099,   122983,     1169,    122984, 1110,
    122985, 1109,    122986, 1119,    122987, 1195,    122988, 42577,   122989,     1201,    122990, -122991,
    123023, 0,       123024, -123025, 123184, 0,       123191, -123192, 123566,     0,       123567, -123568,
    123628, 0,       123632, -123633, 124140, 0,       124144, -124145, 124398,     0,       124400, -124401,
    125136, 0,       125143, -125144, 125252, 0,       125259, -125260, 126464,     -1576,   126466, 1580,
    126467, 1583,    126468, 126468,  126469, 1608,    126470, 1586,    126471,     1581,    126472, 1591,
    126473, 1610,    126474, -1604,   126478, 1587,    126479, 1593,    126480,     1601,    126481, 1589,
    126482, 1602,    126483, 1585,    126484, 1588,    126485, -1579,   126487,     1582,    126488, 1584,
    126489, 1590,    126490, 1592,    126491, 1594,    126492, 1646,    126493,     1722,    126494, 1697,
    126495, 1647,    126496, 126496,  126497, 1576,    126498, 1580,    126499,     126499,  126500, 1607,
    126501, -126502, 126503, 1581,    126504, 126504,  126505, 1610,    126506,     -1604,   126510, 1587,
    126511, 1593,    126512, 1601,    126513, 1589,    126514, 1602,    126515,     126515,  126516, 1588,
    126517, -1579,   126519, 1582,    126520, 126520,  126521, 1590,    126522,     126522,  126523, 1594,
    126524, -126525, 126530, 1580,    126531, -126532, 126535, 1581,    126536,     126536,  126537, 1610,
    126538, 126538,  126539, 1604,    126540, 126540,  126541, 1606,    126542,     1587,    126543, 1593,
    126544, 126544,  126545, 1589,    126546, 1602,    126547, 126547,  126548,     1588,    126549, -126550,
    126551, 1582,    126552, 126552,  126553, 1590,    126554, 126554,  126555,     1594,    126556, 126556,
    126557, 1722,    126558, 126558,  126559, 1647,    126560, 126560,  126561,     1576,    126562, 1580,
    126563, 126563,  126564, 1607,    126565, -126566, 126567, 1581,    126568,     1591,    126569, 1610,
    126570, 1603,    126571, 126571,  126572, -1606,   126574, 1587,    126575,     1593,    126576, 1601,
    126577, 1589,    126578, 1602,    126579, 126579,  126580, 1588,    126581,     -1579,   126583, 1582,
    126584, 126584,  126585, 1590,    126586, 1592,    126587, 1594,    126588,     1646,    126589, 126589,
    126590, 1697,    126591, 126591,  126592, -1576,   126594, 1580,    126595,     1583,    126596, -1608,
    126598, 1586,    126599, 1581,    126600, 1591,    126601, 1610,    126602,     126602,  126603, -1605,
    126606, 1587,    126607, 1593,    126608, 1601,    126609, 1589,    126610,     1602,    126611, 1585,
    126612, 1588,    126613, -1579,   126615, 1582,    126616, 1584,    126617,     1590,    126618, 1592,
    126619, 1594,    126620, -126621, 126625, 1576,    126626, 1580,    126627,     1583,    126628, 126628,
    126629, 1608,    126630, 1586,    126631, 1581,    126632, 1591,    126633,     1610,    126634, 126634,
    126635, -1605,   126638, 1587,    126639, 1593,    126640, 1601,    126641,     1589,    126642, 1602,
    126643, 1585,    126644, 1588,    126645, -1579,   126647, 1582,    126648,     1584,    126649, 1590,
    126650, 1592,    126651, 1594,    126652, -126653, 127232, 48,      127234,     -50,     127243, -127244,
    127275, 67,      127276, 82,      127277, -127278, 127280, -66,     127306,     -127307, 127490, 12469,
    127491, -127492, 127504, 25163,   127505, 23383,   127506, 21452,   127507,     12486,   127508, 20108,
    127509, 22810,   127510, 35299,   127511, 22825,   127512, 20132,   127513,     26144,   127514, 28961,
    127515, 26009,   127516, 21069,   127517, 24460,   127518, 20877,   127519,     26032,   127520, 21021,
    127521, 32066,   127522, 29983,   127523, 36009,   127524, 22768,   127525,     21561,   127526, 28436,
    127527, 25237,   127528, 25429,   127529, 19968,   127530, 19977,   127531,     36938,   127532, 24038,
    127533, 20013,   127534, 21491,   127535, 25351,   127536, 36208,   127537,     25171,   127538, 31105,
    127539, 31354,   127540, 21512,   127541, 28288,   127542, 26377,   127543,     26376,   127544, 30003,
    127545, 21106,   127546, 21942,   127547, 37197,   127548, -127549, 127568,     24471,   127569, 21487,
    127570, -127571, 130032, -49,     130042, -130043, 194560, 20029,   194561,     20024,   194562, 20033,
    194563, 131362,  194564, 20320,   194565, 20398,   194566, 20411,   194567,     20482,   194568, 20602,
    194569, 20633,   194570, 20711,   194571, 20687,   194572, 13470,   194573,     132666,  194574, 20813,
    194575, 20820,   194576, 20836,   194577, 20855,   194578, 132380,  194579,     13497,   194580, 20839,
    194581, 20877,   194582, 132427,  194583, 20887,   194584, 20900,   194585,     20172,   194586, 20908,
    194587, 20917,   194588, 168415,  194589, 20981,   194590, 20995,   194591,     13535,   194592, 21051,
    194593, 21062,   194594, 21106,   194595, 21111,   194596, 13589,   194597,     21191,   194598, 21193,
    194599, 21220,   194600, 21242,   194601, -21254,  194603, 21271,   194604,     21321,   194605, 21329,
    194606, 21338,   194607, 21363,   194608, 21373,   194609, 21375,   194612,     133676,  194613, 28784,
    194614, 21450,   194615, 21471,   194616, 133987,  194617, 21483,   194618,     21489,   194619, 21510,
    194620, 21662,   194621, 21560,   194622, 21576,   194623, 21608,   194624,     21666,   194625, 21750,
    194626, 21776,   194627, 21843,   194628, 21859,   194629, 21892,   194631,     21913,   194632, 21931,
    194633, 21939,   194634, 21954,   194635, 22294,   194636, 22022,   194637,     22295,   194638, 22097,
    194639, 22132,   194640, 20999,   194641, 22766,   194642, 22478,   194643,     22516,   194644, 22541,
    194645, 22411,   194646, 22578,   194647, 22577,   194648, 22700,   194649,     136420,  194650, 22770,
    194651, 22775,   194652, 22790,   194653, 22810,   194654, 22818,   194655,     22882,   194656, 136872,
    194657, 136938,  194658, 23020,   194659, 23067,   194660, 23079,   194661,     23000,   194662, 23142,
    194663, 14062,   194664, 14076,   194665, 23304,   194666, 23358,   194668,     137672,  194669, 23491,
    194670, 23512,   194671, 23527,   194672, 23539,   194673, 138008,  194674,     23551,   194675, 23558,
    194676, 24403,   194677, 23586,   194678, 14209,   194679, 23648,   194680,     23662,   194681, 23744,
    194682, 23693,   194683, 138724,  194684, 23875,   194685, 138726,  194686,     23918,   194687, 23915,
    194688, 23932,   194689, -24034,  194691, 14383,   194692, 24061,   194693,     24104,   194694, 24125,
    194695, 24169,   194696, 14434,   194697, 139651,  194698, 14460,   194699,     24240,   194700, 24243,
    194701, 24246,   194702, 24266,   194703, 172946,  194704, 24318,   194705,     140081,  194707, 33281,
    194708, 24354,   194710, 14535,   194711, 144056,  194712, 156122,  194713,     24418,   194714, 24427,
    194715, 14563,   194716, 24474,   194717, 24525,   194718, 24535,   194719,     24569,   194720, 24705,
    194721, 14650,   194722, 14620,   194723, 24724,   194724, 141012,  194725,     24775,   194726, 24904,
    194727, 24908,   194728, 24910,   194729, 24908,   194730, 24954,   194731,     24974,   194732, 25010,
    194733, 24996,   194734, 25007,   194735, 25054,   194736, 25074,   194737,     25078,   194738, 25104,
    194739, 25115,   194740, 25181,   194741, 25265,   194742, 25300,   194743,     25424,   194744, 142092,
    194745, 25405,   194746, 25340,   194747, 25448,   194748, 25475,   194749,     25572,   194750, 142321,
    194751, 25634,   194752, 25541,   194753, 25513,   194754, 14894,   194755,     25705,   194756, 25726,
    194757, 25757,   194758, 25719,   194759, 14956,   194760, 25935,   194761,     25964,   194762, 143370,
    194763, 26083,   194764, 26360,   194765, 26185,   194766, 15129,   194767,     26257,   194768, 15112,
    194769, 15076,   194770, 20882,   194771, 20885,   194772, 26368,   194773,     26268,   194774, 32941,
    194775, 17369,   194776, 26391,   194777, 26395,   194778, 26401,   194779,     26462,   194780, 26451,
    194781, 144323,  194782, 15177,   194783, 26618,   194784, 26501,   194785,     26706,   194786, 26757,
    194787, 144493,  194788, 26766,   194789, 26655,   194790, 26900,   194791,     15261,   194792, 26946,
    194793, 27043,   194794, 27114,   194795, 27304,   194796, 145059,  194797,     27355,   194798, 15384,
    194799, 27425,   194800, 145575,  194801, 27476,   194802, 15438,   194803,     27506,   194804, 27551,
    194805, -27579,  194807, 146061,  194808, 138507,  194809, 146170,  194810,     27726,   194811, 146620,
    194812, 27839,   194813, 27853,   194814, 27751,   194815, 27926,   194816,     27966,   194817, 28023,
    194818, 27969,   194819, 28009,   194820, 28024,   194821, 28037,   194822,     146718,  194823, 27956,
    194824, 28207,   194825, 28270,   194826, 15667,   194827, 28363,   194828,     28359,   194829, 147153,
    194830, 28153,   194831, 28526,   194832, 147294,  194833, 147342,  194834,     28614,   194835, 28729,
    194836, 28702,   194837, 28699,   194838, 15766,   194839, 28746,   194840,     28797,   194841, 28791,
    194842, 28845,   194843, 132389,  194844, 28997,   194845, 148067,  194846,     29084,   194847, 148395,
    194848, 29224,   194849, 29237,   194850, 29264,   194851, 149000,  194852,     29312,   194853, 29333,
    194854, 149301,  194855, 149524,  194856, 29562,   194857, 29579,   194858,     16044,   194859, 29605,
    194860, 16056,   194862, 29767,   194863, 29788,   194864, 29809,   194865,     29829,   194866, 29898,
    194867, 16155,   194868, 29988,   194869, 150582,  194870, 30014,   194871,     150674,  194872, 30064,
    194873, 139679,  194874, 30224,   194875, 151457,  194876, 151480,  194877,     151620,  194878, 16380,
    194879, 16392,   194880, 30452,   194881, 151795,  194882, 151794,  194883,     151833,  194884, 151859,
    194885, -30495,  194887, 30495,   194888, 30538,   194889, 16441,   194890,     30603,   194891, 16454,
    194892, 16534,   194893, 152605,  194894, 30798,   194895, 30860,   194896,     30924,   194897, 16611,
    194898, 153126,  194899, 31062,   194900, 153242,  194901, 153285,  194902,     31119,   194903, 31211,
    194904, 16687,   194905, 31296,   194906, 31306,   194907, 31311,   194908,     153980,  194909, 154279,
    194911, 31470,   194912, 16898,   194913, 154539,  194914, 31686,   194915,     31689,   194916, 16935,
    194917, 154752,  194918, 31954,   194919, 17056,   194920, 31976,   194921,     31971,   194922, 32000,
    194923, 155526,  194924, 32099,   194925, 17153,   194926, 32199,   194927,     32258,   194928, 32325,
    194929, 17204,   194930, 156200,  194931, 156231,  194932, 17241,   194933,     156377,  194934, 32634,
    194935, 156478,  194936, 32661,   194937, 32762,   194938, 32773,   194939,     156890,  194940, 156963,
    194941, 32864,   194942, 157096,  194943, 32880,   194944, 144223,  194945,     17365,   194946, 32946,
    194947, 33027,   194948, 17419,   194949, 33086,   194950, 23221,   194951,     157607,  194952, 157621,
    194953, 144275,  194954, 144284,  194955, 33281,   194956, 33284,   194957,     36766,   194958, 17515,
    194959, 33425,   194960, 33419,   194961, 33437,   194962, 21171,   194963,     33457,   194964, 33459,
    194965, 33469,   194966, 33510,   194967, 158524,  194968, 33509,   194969,     33565,   194970, 33635,
    194971, 33709,   194972, 33571,   194973, 33725,   194974, 33767,   194975,     33879,   194976, 33619,
    194977, 33738,   194978, 33740,   194979, 33756,   194980, 158774,  194981,     159083,  194982, 158933,
    194983, 17707,   194984, 34033,   194985, 34035,   194986, 34070,   194987,     160714,  194988, 34148,
    194989, 159532,  194990, 17757,   194991, 17761,   194992, 159665,  194993,     159954,  194994, 17771,
    194995, 34384,   194996, 34396,   194997, 34407,   194998, 34409,   194999,     34473,   195000, 34440,
    195001, 34574,   195002, 34530,   195003, 34681,   195004, 34600,   195005,     34667,   195006, 34694,
    195007, 17879,   195008, 34785,   195009, 34817,   195010, 17913,   195011,     34912,   195012, 34915,
    195013, 161383,  195014, 35031,   195015, 35038,   195016, 17973,   195017,     35066,   195018, 13499,
    195019, 161966,  195020, 162150,  195021, 18110,   195022, 18119,   195023,     35488,   195024, 35565,
    195025, 35722,   195026, 35925,   195027, 162984,  195028, 36011,   195029,     36033,   195030, 36123,
    195031, 36215,   195032, 163631,  195033, 133124,  195034, 36299,   195035,     36284,   195036, 36336,
    195037, 133342,  195038, 36564,   195039, 36664,   195040, 165330,  195041,     165357,  195042, 37012,
    195043, 37105,   195044, 37137,   195045, 165678,  195046, 37147,   195047,     37432,   195048, -37592,
    195050, 37500,   195051, 37881,   195052, 37909,   195053, 166906,  195054,     38283,   195055, 18837,
    195056, 38327,   195057, 167287,  195058, 18918,   195059, 38595,   195060,     23986,   195061, 38691,
    195062, 168261,  195063, 168474,  195064, 19054,   195065, 19062,   195066,     38880,   195067, 168970,
    195068, 19122,   195069, 169110,  195070, 38923,   195072, 38953,   195073,     169398,  195074, 39138,
    195075, 19251,   195076, 39209,   195077, 39335,   195078, 39362,   195079,     39422,   195080, 19406,
    195081, 170800,  195082, 39698,   195083, 40000,   195084, 40189,   195085,     19662,   195086, 19693,
    195087, 40295,   195088, 172238,  195089, 19704,   195090, 172293,  195091,     172558,  195092, 172689,
    195093, 40635,   195094, 19798,   195095, 40697,   195096, 40702,   195097,     40709,   195098, 40719,
    195099, 40726,   195100, 40763,   195101, 173568,  195102, -195103, 917505,     0,       917506, -917507,
    917536, 0,       917632, -917633, 917760, 0,       918000, -918001, 2147483647, 0};

UnicodeSimpleCategory get_unicode_simple_category(uint32 code) {
  if (code < 128) {
    return static_cast<UnicodeSimpleCategory>(unicode_simple_category_table[code]);
  }
  auto jump_pos_index = code <= 0x20000 ? code >> 7 : (0x20000 >> 7) - (0x20000 >> 16) + (code >> 16);
  // CHECK(jump_pos_index < sizeof(unicode_simple_category_ranges) / sizeof(unicode_simple_category_ranges[0]));
  auto it = unicode_simple_category_ranges + unicode_simple_category_jump_pos[jump_pos_index];
  code = (code << 5) + 30;
  // CHECK(unicode_simple_category_ranges[unicode_simple_category_jump_pos[jump_pos_index + 1]] > code);
  while (*it <= code) {
    ++it;
  }
  return static_cast<UnicodeSimpleCategory>(*(it - 1) & 31);
}

/**
 * Search pregenerated ranges of pairs for the replacement of specified character
 */
template <size_t N>
static uint32 binary_search_ranges(const int32 (&ranges)[N], uint32 code) {
  if (code > 0x10ffff) {
    return 0;
  }

  auto code_int = static_cast<int32>(code);
  size_t l = 0;
  size_t r = N;
  while (l < r) {
    size_t m = ((l + r + 2) >> 2) << 1;
    if (ranges[m] <= code_int) {
      l = m;
    } else {
      r = m - 2;
    }
  }

  int32 t = ranges[l + 1];
  if (t < 0) {
    return code - ranges[l] + (~t);
  }
  if (t <= 0x10ffff) {
    return t;
  }
  switch (t - 0x200000) {
    case 0:
      return (code & -2);
    case 1:
      return (code | 1);
    case 2:
      return ((code - 1) | 1);
    default:
      LOG(FATAL) << code << " " << l << " " << r << " " << t;
      return 0;
  }
}

uint32 prepare_search_character(uint32 code) {
  if (code < TABLE_SIZE) {
    return prepare_search_character_table[code];
  } else {
    return binary_search_ranges(prepare_search_character_ranges, code);
  }
}

uint32 unicode_to_lower(uint32 code) {
  if (code < TABLE_SIZE) {
    return to_lower_table[code];
  } else {
    return binary_search_ranges(to_lower_ranges, code);
  }
}

uint32 remove_diacritics(uint32 code) {
  if (code < TABLE_SIZE) {
    return without_diacritics_table[code];
  } else {
    return binary_search_ranges(without_diacritics_ranges, code);
  }
}

}  // namespace td