Author Archives: bunyk

Як написати собі маленький Google Translate на Grammatical Framework за 15 хв

Posted by on 02.02.2020 Коментарі Вимкнено до Як написати собі маленький Google Translate на Grammatical Framework за 15 хв

І з якістю трохи кращою ніж в Google Translate, але з обсягом можливих перекладів набагато меншим.

Що я роблю на роботі

Зараз я працюю в Zalando – компанії яка продає різний крам в купу країн Європи. Відповідно, треба підтримувати сайт для багатьох країн. Я працюю у відділі який займається інструментами що допомагають створювати наповнення сайту. Процес додавання нового вмісту на сайт дуже трудомісткий, бо потрібно сфотографувати продукт, на столі, на моделі, перевірити розміри, матеріали і інструкції з догляду, написати опис, заголовок і т.п.. А потім ще перекласти це на 8 мов і кілька локалей, бо деякі країни DACH (німецькомовний простір) не входять до єврозони і використовують швейцарські франки наприклад. Це велика купа часу, і великий простір для автоматизації.

Google Translate не підходить, тому що наприклад ми продаємо скатертини, і німецький менеджер пише “Tischdecken” (множина від Tischdecke), Google Translate думає що це дієслово (бо є таке дієслово), і перекладає “Set the table” (накривайте столи!).

Насправді задача стоїть простіша ніж повний машинний переклад, бо дані отримуються не якоюсь конкретною мовою, а набором параметрів – “що”, “коли”, “яке”, “для кого”, “по чому” і т.п.. Тобто якщо я отримую що=взуття, яке=класичне коли=зима для кого=хлопчики, по чому=<100 € то я (в сенсі моя програма), пише:

'de_CH': 'Klassische Winterschuhe für Jungs - unter CHF 107',
'de_DE': 'Klassische Winterschuhe für Jungs - unter 100 €',
'en_GB': 'Classic Winter Shoes for Boys - under £85',

Все просто – перекладаємо слова за словником і підставляємо в шаблон для конкретного набору компонентів. З німецькою лише один виклик – з’єднання слів. Тобто якщо я з’єдную Winter з чимось – просто конкатеную, а от коли Fruhling – додаю між Fruhling і тим словом яке приєдную ще “s”. Є ще інші правила.

Складність з’являється в слов’янських мовах. Там є відмінювання прикметників у множині.

На роботі я багато думаю як би то не робити роботу яку вже хтось зробив за мене

Програмісти ліниві створіння. Нащо писати код якщо код вже є написаний на StackOverflow і Github? Треба лише знати де той код лежить. І я почав собі шукати як інші люди це робили. До того як з’явилось машинне навчання і статистичні методи, всі пробували підхід на основі правил. І проміжної мови.

З проміжною мовою процес розбивався на дві частини – спершу проводився синтаксичний аналіз тексту на мові джерела, тоді з побудованого представлення тексту на проміжній мові (зазвичай дерево) будувався текст іншою мовою.

Моя задача вже простіша, бо ніякого синтаксичного аналізу робити не треба, треба просто згенерувати текст 8-ма мовами на основі структури даних. Це як два пальці відрендерити контекст за допомогою шаблону, ми веб-деви тільки таке й робимо.

Тільки виявляється що шаблон для генерації простого заголовку на зразок: “Mindestens 500 € sparen – Premium Herbstmode” або “Premium Herbstmode unter 999 €” займає мало не ввесь екран.

Я подумав що може нарешті настав той момент коли я на Кубику не даремно вчився, пам’ятаю Opa Chomsky Style, і треба застосувати якусь контекстно-вільну граматику, чи яка там наступна за потужністю, бо контекстно-вільна здається не потягне слов’янську морфологію.

І раптом в своїх пошуках надибав Grammatical Framework. Це штука яку вже більше ніж 20 років пишуть на Хаскелі, значить люди вміють точно більше ніж я. І автор приходить з доповіддю в Google, в якій кілька слайдів на початку – суцільний тролінг команди Google Translate:

Але мене підкупило речення з їх сайту, http://www.grammaticalframework.org/

GF is easy to learn by following the tutorial. You can write your first translator in 15 minutes.

До роботи!

Ну що ж, заводимо таймер, і спробуємо наприклад написати перекладач, що може перекласти набір шахматних словосполучень /(black|white) (queen|king)/ з англійської на українську. Шахмати, тому що одягом я й на роботі можу зайнятись, а блог я пишу вдома і хочеться трохи змінити контекст.

Для початку варто встановити компілятор/інтерпретатор gf. На сторінці завантаження є пакети для різних ОС, з інструкцією про те як їх поставити. Ще можна поставити плагін підсвітки синтаксису для вашого редактора, перелік є на цій сторінці.

Hello, world!

Тепер, в файлі Chess.gf пишемо таку граматику:

-- це, до речі, коментар
abstract Chess = {

  flags startcat = Piece ;

  cat PieceType ; Color ; Piece;

  fun
    piece : Color -> PieceType -> Piece ;
    Black, White : Color;
    Queen, King: PieceType;
}

abstract означає що ми описуємо граматику проміжної мови, тобто не якоїсь конкретної людської, а мови якою ми описуватимемо сенс тексту.

flags startcat = Piece ; означає що початковою категорією (коренем дерева) буде фігура.

cat перелічує можливі категорії (типи вузлів дерева).

Секція fun описує функції. Функції описують як будується дерево, і можуть бути будь-якої арності, в тому числі нулярні. Наприклад тут функції Black та White не приймають аргументів але повертають колір. (По суті – константи). Зате функція piece приймає дві категорії і повертає категорію для фігури.

Тепер про те як перетворити дерево на послідовність токенів якоюсь мовою. Це називається лінеаризацією, і описується конкретною граматикою:

concrete ChessEng of Chess = {

  lincat Piece, Color, PieceType = {s : Str} ;

  lin
    piece color type = {s = color.s ++ type.s} ;
    Black = {s = "black"} ;
    White = {s = "white"} ;
    Queen = {s = "queen"} ;
    King = {s = "king"} ;
}

Зберігаємо її в файлі ChessEng.gf. Для GF важливо щоб кожна граматика була в своєму файлі і щоб він називався так само як називається граматика, інакше він дає помилки.

lincat описує які типи токенів будуть відповідати категоріям абстрактної категорії. В нашому випадку це структура з одним полем типу Str, тому що пізніше нам знадобляться інші поля.

lin описує функції лінеаризації типи яких були описані в абстрактній граматиці. Для унарних функцій – як власне пишеться слово, для інших – як скомбінувати інші лінеаризації.

Щоб потестувати як все працює, запускаємо команду gf Chess*, яка завантажує обидві граматики і починає інтерактивну сесію.

Тут ми можемо наприклад перевіряти наші речення на правильність:

Chess> parse "black queen"
piece Black Queen

Chess> parse "snow queen"
The parser failed at token 1: "snow"

Правильно, ми тут пишемо граматику для шахмат а не для казок. Ще можна попросити згенерувати випадкове дерево:

Chess> generate_random
piece White Queen

Або його лінеаризацію:

Chess> generate_random | linearize
black queen

Або всі можливі речення:

Chess> generate_trees | l
black king
black queen
white king
white queen

Морфологія

Тепер давайте зробимо переклад на українську! Для цього треба описати граматику української. Додаємо переклад з англійської в файл ChessUkr.gf:

concrete ChessUkr of Chess = {

  lincat Piece, Color, PieceType = {s : Str} ;

  lin
    piece color type = {s = color.s ++ type.s} ;
    Black = {s = "чорний"} ;
    White = {s = "білий"} ;
    Queen = {s = "королева"} ;
    King = {s = "король"} ;
}

Завантажуємо і тестуємо перекладач в консолі:

Chess> parse -lang=ChessEng "black king" | linearize -lang=ChessUkr
чорний король

Дуже добре!

Chess> parse -lang=ChessEng "white queen" | linearize -lang=ChessUkr
білий королева

От засада! Навіть Google Translate вміє краще. Треба ввести в українську граматику поняття роду. Для цього до іменників треба додати інформацію про те якого вони роду, а кольори мають описувати як вони відмінюються залежно від роду:

concrete ChessUkr of Chess = {

  param Gender = Masc | Fem ;
  lincat Piece, PieceType = {s : Str; gender : Gender} ;
  lincat Color = {s : Gender => Str} ;

  lin
    piece color type = {s = color.s ! type.gender ++ type.s; gender=type.gender} ;
    Black = {s = table {
        Masc => "чорний";
        Fem => "чорна"
    } };
    White = {s = table {
        Masc => "білий";
        Fem => "біла"
    } };
    Queen = {s = "королева"; gender=Fem} ;
    King = {s = "король"; gender=Masc} ;
}

Тут нам і стало в нагоді те що наші категорії – це структури, а не просто рядки. Чіпляємо до кожної фігури інформацію про стать.

Gender => Str задає тип таблиці (це майже як функція, тільки описується чимось типу хеша). Кожен колір тепер – це таблиця. Операція “!” – це вибір значення з таблиці.

Тестуємо нову граматику української:

Chess> generate_trees | l
black king
чорний король
black queen
чорна королева
white king
білий король
white queen
біла королева


Chess> parse -lang=ChessUkr "білий король"
piece White King

Chess> parse -lang=ChessUkr "біла король"
The parser failed at token 2: "\1082\1086\1088\1086\1083\1100"

Хаха, він думає що ми неправильно вжили слово король, бо після біла може стояти лише королева. Але помилку знайшов!

Рефакторинг

Накодили, потестували, тепер пора зробити код гарнішим.

Писати словник в форматі:

    White = {s = table {
        Masc => "білий";
        Fem => "біла"
    } };

Коли ми можливо захочемо додати ще слів які можливо матимуть ще середній рід і множину – доволі трудозатратно. Але ми можемо написати функцію. Точніше оператор, бо в GF функцією ми вже назвали штуку яка будує дерево.

Ще нам знадобиться згадати школу, в якій нам казали що прикметники твердої групи в чоловічому роді завжди закінчуються на -ий, а в жіночому на -а.

Тоді ми можемо додати в українську граматику такий оператор:

  -- hard adjective
  oper ha: Str -> {s: Gender => Str} = \stem -> {
      s = table {
          Masc => stem+"ий";
          Fem => stem+"а"
      }
  };

Він приймає рядок і повертає токен в якого s – це таблиця що відображає рід на написання.

І тепер ми можемо швидко додавати багато прикметників:

    Black = ha "чорн";
    White = ha "біл";
    Fast = ha "швидк";
    Defenceless = ha "беззахисн";

і навіть швидко додати множину для всіх якщо додамо закінчення рід. Правда колір певне варто перейменувати в прикметник, а рід – в граматичну категорію. Але іменування – це вже складніша проблема програмування.

Тепер додайте решту слів і маєте свій перекладач!

Hunspell

Posted by on 13.01.2020 Коментарі Вимкнено до Hunspell

Hunspell розшифровується як “угорський правопис”, і це найбільш просунута програма перевірки правопису якщо не враховувати Grammarly. А все тому що угорська мова – найбільш скажена в плані морфології. Тому якщо щось підходить для угорської – для інших європейських мов точно підійде. 

sudo apt install hunspell hunspell-uk hunspell-de-de libhunspell-dev
sudo pip install hunspell

hunspell має доволі простий інтерфейс для використання в мовах програмування (хоча й складні словники (читати man hunspell.5)):

>>> import hunspell
>>> spellchecker = hunspell.HunSpell('/usr/share/hunspell/uk_UA.dic', '/usr/share/hunspell/uk_UA.aff')
>>> spellchecker.spell('ласка')
True
>>> spellchecker.spell('ласкає')
False
>>> spellchecker.suggest('ласкає')
['ласка', 'ласкам', 'лускає', 'ласках', 'ляскає', 'ласка є', 'скалатає']

І враховуючи що метод spell по суті просто визначає чи належить слово до множини правильних слів мови, ми можемо побудувати наприклад функцію для розкладу слів на прості. 

import hunspell

EXAMPLES = '''
Landtagsabgeordneter,30039
Nationalsozialistischen,25081
Rechtswissenschaften,24718
Auseinandersetzungen,23109
Bundesverdienstkreuzes,22208
Rechtswissenschaftler,21113
Einwohnerentwicklung,20432
Landwirtschaftlichen,19085
Fußballnationalmannschaft,16235
Landschaftsschutzgebiet,13565
Bundesverdienstkreuz,12084
Reichsdeputationshauptschlusses,698
Sehnsuchtsland,13
'''

def test():
    for line in EXAMPLES.splitlines():
        if not line:
            continue
        word = line.split(',')[0].strip()
        print(word, '=', decompound(word))

spellchecker = hunspell.HunSpell('/usr/share/hunspell/de_DE.dic', '/usr/share/hunspell/de_DE.aff')

def decompound(word):
    variants = list(decompound_(word))
    variants.sort(key=lambda w: w.count('+'))
    return variants[-1]

def decompound_(word):
    '''yield decompositions of word or if not found whole word if spelled correctly or None if spelled incorreclty'''
    word = word.capitalize()
    if len(word) < 6:
        if spellchecker.spell(word):
            yield word
        return
    for i in range(3,len(word) - 3):
        p1, p2 = word[:i], word[i:]
        ok1 = spellchecker.spell(p1) or (
            p1.endswith('s') and spellchecker.spell(p1[:-1])
        )
        if ok1:
            for dp2 in decompound_(p2):
                yield p1 + '+' + dp2

    if spellchecker.spell(word):
        yield word


if __name__ == '__main__':
    test()

Sehnsuchtsland нема в словниках hunspell, бо воно у вікіпедії згадується лише 13 разів, зате Sehnsuchts (і очевидно Land) – є:

Landtagsabgeordneter = Land+Tags+Abgeordneter
Nationalsozialistischen = National+Sozialistischen
Rechtswissenschaften = Rechts+Wissen+Schaften
Auseinandersetzungen = Aus+Einander+Set+Zungen
Bundesverdienstkreuzes = Bundes+Verdienst+Kreuzes
Rechtswissenschaftler = Rechts+Wissenschaftler
Einwohnerentwicklung = Einwohner+Entwicklung
Landwirtschaftlichen = Land+Wirtschaftlichen
Fußballnationalmannschaft = Fuß+Ball+National+Mann+Schaft
Landschaftsschutzgebiet = Land+Schafts+Schutz+Gebiet
Bundesverdienstkreuz = Bundes+Verdienst+Kreuz
Reichsdeputationshauptschlusses = Reichs+Deputat+Ions+Haupt+Schlusses
Sehnsuchtsland = Sehnsuchts+Land

Ще воно неправильно розклало Deputat+Ions, але побачило можливість – розклало. Може іони мають бути виняток, бо вони часто трапляються як суфікс.

Як збудувати геодезичний купол?

Posted by on 21.12.2019 Коментарі Вимкнено до Як збудувати геодезичний купол?

Я простий програміст, але іноді свербить побути архітектором. Всякий ентерпрайз проектувати ще не пускають, але тут випала нагода зпроектувати проект іграшкової хатинки для донечки. Тому що після покупки меблів в порожню квартиру в нас все ще залишається вільна кімната і в ній куууупа картону.

Картон в меблевій майстерні

Я погуглив які можна робити хатинки і знайшов таке на instructables. Але там виміри подані все ще в імперській системі і я вирішив перерахувати. І взагалі зробити проект правильною водоспадною методологією – поетапно.

3d модель

Перший етап – змоделювати все на комп’ютері.

  1. Запускаємо Blender, вибираємо куб який там за замовчуванням, натискаємо Delete.
  2. Shift+A (додати об’єкт) -> Icosphere, Subdivision: 2, Size: 1.0 location: (0.0, 0.0, 0.0).
  3. Переключаємось на вид з переду, тиснемо Tab і переходимо в Edit mode.
  4. Тиснемо правою кнопкою на якусь вершину аби вибрати лише її. Тиснемо b, аби вибрати вершини рамкою, і вибираємо ті що нижче 0 по осі Z.
  5. Натискаємо Delete і видалаємо половину вершин знизу.

Має вийти щось таке:

Купол в Blender

Це можна експортувати в розгортку для паперової моделі, якщо зробити наступне:

  1. Зайти в меню File -> User preferences, вкладка Add-ons, категорія Import-Export.
  2. Поставити галочку біля Export Paper Model, і натиснути “Save User Settings”.
  3. File -> Export -> Paper Model експортує модель в файл pdf (хоча пише що svg).

Отримаємо таке:

Розгортка

Для деяких розрахунків більшої моделі ще корисно експортувати в .obj файл.

Паперова модель

В паперовій моделі головне акуратно вирізати розгортку по чорних суцільних лініях, зігнути по пунктирних і склеїти сіренькі краї.

Склеєна паперова модель

Паперова модель дає краще уявлення про те скільки трикутників доведеться вирізати, але як різати картон все ще не ясно. Якщо я хочу купол радіусом 1 метр, то якого розміру мають бути трикутники?

Вони здаються правильними, але насправді лише здаються, тому що з правильних трикутників вийде хіба що площина або дельтаедр. Щоб обчислити розміри трикутників, можна використати obj файл.

Розміри

Наступний скрипт якщо йому згодувати наш obj файл зробить дві речі:

import sys
import math
from collections import Counter

# Distance between two vectors (iterables) rounded to 3 digits after comma
def distance(A, B):
    return round(math.sqrt(sum((a - b)**2 for a, b in zip(A,B))), 3)

def obj_fline_to_edges(line, vertices):
    # get indexes of vertices
    face = [int(e.split('/')[0]) - 1 for e in line[2:].split(' ')]

    # compute edge length's
    edges = sorted([
        distance(vertices[face[0]], vertices[face[1]]),
        distance(vertices[face[2]], vertices[face[1]]),
        distance(vertices[face[2]], vertices[face[0]]),
    ])
    return tuple(edges)

def main(filename):
    vertices = []
    faces = []
    face_lines = []
    with open(filename) as f:
        for line in f:
            if line.startswith('v '): # add line to list of vertices
                coords = [float(e) for e in line[2:].split(' ')]
                vertices.append(coords)

            if line.startswith('f '): # it's a face
                face_lines.append(line.strip())
                edges = obj_fline_to_edges(line, vertices)
                faces.append(edges)

    stats = Counter(faces).most_common()
    for i, (edges, count) in enumerate(stats, 1):
        print(f'{i}) {edges} - {count}')

    materials = [
        'redMtl',
        'blueMtl',
    ]
    for i, (edges_type, count) in enumerate(stats):
        print("usemtl", materials[i])
        for line in face_lines:
            edges = obj_fline_to_edges(line, vertices)
            if edges == edges_type:
                print(line)

if __name__ == "__main__":
    main(sys.argv[1])

Напише статистику по трикутнихах, і скаже що в нас їх є два види, 30 рівнобедрених і 10 рівносторонніх. Розміри в міліметрах, якщо купол метровий:
1) (0.547, 0.547, 0.618) – 30
2) (0.618, 0.618, 0.618) – 10

А крім того, додасть матеріали, які в позначать в моделі трикутники різного типу різними кольорами. Кожен рядок що починається на f, в об’єктному файлі треба замінити на той який виводиться нашим скриптом. (Разом з usemtl, вони позначають кольори). В файл *.mtl який Blender експортує поряд з об’єктним, треба додати наприклад такі матеріали:

newmtl redMtl
Ns 18
Ka 0.000000 0.000000 0.000000
Kd 1.0 0.5 0.5
Ks 0.8 0.8 0.8
d 1
illum 2

newmtl blueMtl
Ns 1
Ka 0.000000 0.000000 0.000000
Kd 0.5 0.5 1.0
Ks 0.8 0.8 0.8
d 1
illum 2

Kd означає колір дифузного відбиття за Фонгом.

Тепер, якщо ми експортуємо те що відредагували в текстовому редакторі назад в Blender – отримаємо таке:

Бачимо що рівнобедрені трикутники треба з’єднати по 5 штук коротшими сторонами в п’ятикутні піраміди, тоді до країв піраміди причепити ще 5 рівносторонніх трикутників, тоді поміж кожні два трикутники вліпити ще по 5 п’ятикутних пірамід і між ними вліпити решту рівносторонніх трикутників. Або іншим способом. Якщо тепер експортувати розгортку, і при експорті вибрати в налаштуваннях документа “Textures: From materials”, то розгортка теж буде кольоровою:

Кольорова розгортка геокупола

Картонна модель

Тепер, головне аби картону вистачило. Виявилось що вирізати трикутник зі стороною майже 62 см я не можу, бо той картон що я маю вужчий. (Насправді головне висота, але я хотів вмістити більше трикутників, тому вирішив що довша сторона буде 38 см, помножив всі розміри на 380/618, і загалом вийшло таке:

1) (0.336, 0.336, 0.380) – 30
2) (0.380, 0.380, 0.380) – 10

І добре, бо діаметр оригінального купола – 2 метри, того що в мене 1.23м, і він набагато краще вміщується в кімнаті. Для того щоб під купол було легше заходити, я зробив лише 9 рівносторонніх трикутників, таким чином що один в основі відсутній, і поставив купол на стіну висотою 50 см з 9 прямокутних секцій шириною по 38 см. Загалом зі стіною висота в центрі складає 1.11м.

Найбільша технічна складність – як побудувати трикутник без велетенського циркуля. Але виявляється циркуль легко робиться за допомогою вимірювальної рулетки, смужки картону і викрутки. Пробиваємо в смужці викруткою дірку, тоді на відстанях які нам потрібно ще дірки. Фіксуємо центр кола викруткою, і вставляючи ручку в дірку на потрібній відстані малюємо коло потрібного радіусу.

Краї для склеювання клеєм я вирішив не креслити аби зекономити картон і поклався на скотч.

Картонний циркуль і креслення зроблені ним

Далі можна не морочитись і використати перші трикутники як шаблони для креслення решти. Далі процес тривіальний.

Натисніть, щоби переглянути слайдшоу.

Враховуючи те що трикутники я вирізав криво, вони прилягають не щільно і в хатинку потрапляє світло через те що скотч прозорий.

Чи сподобалась дитині хатинка? Ніби так, вона туди пару раз лазила грати “ку-ку”, але здається не настільки як мені. 🙂

Тому що нові іграшки – то тимчасове задоволення, а вміння робити 3d штуки без 3d принтера – то назавжди. 😉

Корисні налаштування Git

Posted by on 12.11.2019 Коментарі Вимкнено до Корисні налаштування Git

Перше. Як не задовбувати всіх сміттям яке створює ваше IDE, і за замовчуванням мати gitignore для всіх репозиторіїв. 

git config --global core.excludesfile ~/.gitignore

Ця команда відредагує файл ~/.gitconfig і в ~/.gitignore можна буде перелічити всякі там *.swp, чи що там ваш редактор створює.

Друге. Якщо Go не хоче встановлювати модулі з помилкою “fatal: could not read Username for ‘https://github.com&#8217;: terminal prompts disabled”, бо залежності прописані через https, а ви використовєуте SSH, це можна виправити таким налаштуванням:

git config --global url."git@github.com:".insteadOf "https://github.com/"

На цьому поки що все, дякую за увагу. 🙂

Скільки слів треба щоб написати вікіпедію? І які зустрічаються частіше?

Posted by on 31.07.2019 Коментарі Вимкнено до Скільки слів треба щоб написати вікіпедію? І які зустрічаються частіше?

Виявляється відтоді як я рахував символи вікіпедії пройшло вже більше року. Рахував я їх за допомогою Go, хоча можна було сильно спростити собі життя і рахувати їх за допомогою Python і pywikipediabot. Сьогодні розкажу як, і як можна побачити з назви – рахуватимемо слова.

Я чомусь боявся що щоб порахувати слова пам’яті не вистачить, тому треба якусь базу даних. Або пробувати все в пам’яті, але аби комп’ютеру не стало погано якось обмежити доступну пам’ять. Але мої 4Gb використовувались лише щось трохи більше ніж на 40% для підрахунку всіх слів включно зі сторінками обговорень, категорій, шаблонів, сторінок опису файлів, і т.п. німецької вікіпедії.

В модулі pywikibot.pagegenerators є об’єкти XMLDumpOldPageGenerator і XMLDumpPageGenerator. Вони приймають назву архіву з XML дампом в конструкторі, а після створення по них можна ітеруватися отримуючи об’єкти сторінки. Не ведіться на слово “Old” в назві першого об’єкта, це означає не депрекацію, а те що текст сторінки буде братись з дампа, а в другому випадку з дампа буде братись лише заголовки, а за свіжим текстом зроблять запит, що сповільнить обробку разів в 500. Тобто замість кількох годин ви будете чекати рік. 🙂

Я спробував проаналізувати німецьку вікіпедію (код буде пізніше), на це пішло 694 хв (трохи менше ніж 12 годин) і вийшло що в ній на 6,425,028 сторінках використовується 2,381,457,397 слів (приблизно 371 на сторінку), з них різних слів 18,349,393. В кінцевому результаті CSV з частотним словничком виходить на 300MB.

Серед тих що зустрічаються лише раз є слова типу PikettdienstPikettdienst (помилка парсера який видаляв розмітку), слово – це юридичний термін швейцарської німецької і перекладається як “служба за викликом”. І є слова на зразок Werkshöfe – подвір’я фабрик.

Топ 50 слів виглядає так, і складає 28% всіх слів загалом:

der 58761447 sich 9169933
und 49084873 wurde 9114619
die 44536463 CET 8614461
in 35684744 an 8385637
von 24448221 er 7835324
ist 20614114 dass 7550955
den 19454023 du 7435099
nicht 17519638 bei 7420172
das 17302844 Diskussion 7237855
zu 16167971 aus 7065523
mit 15906145 Artikel 6967243
im 15167140 oder 6824420
des 14661593 werden 6508092
für 14016308 war 6449858
auf 13957013 nach 6426826
auch 12849476 wird 6117566
eine 11903977 aber 6052645
ein 11780352 am 6017703
Kategorie 11369651 sind 5953632
als 11167157 Der 5623930
dem 11124726 Das 5545595
CEST 11104741 einen 5465687
ich 10886406 noch 5409154
Die 10761776 wie 5293658
es 10204681 einer 5228368

До списку потрапили такі вікіпедійно специфічні слова як Kategorie (сторінки без категорій вважаються не комільфо), CEST і CET (центральноєвропейський літній час і центральноєвропейський час, в підписах в обговореннях).

Ну а що без сторінок обговорень? Проблемав тому, що при створенні об’єкту сторінки XMLDumpOldPageGenerator бере з дампа лише текст і заголовок, простір імен залишається не заповненим і за замовчуванням 0 (основний). Є ще поле isredirect так при спробі доступу до нього знову здійснюється запит. Тому, краще перейти на рівень нижче і використати XmlDump з pywikibot.xmlreader, він використовується так само, просто дає об’єкти не Page, а попростіші, які не вміють робити запити до вікіпедії і не мають методу save. Але нам його й не треба, правда?

Ось код який ігнорує перенаправлення і всі сторінки крім статтей:

"""Count word frequencies in wikipedia dump"""
import csv
from collections import Counter
from itertools import islice
import re
import sys

import mwparserfromhell
from pywikibot.xmlreader import XmlDump

def main():
    """Iterate over pages and count words"""
    if len(sys.argv) < 2:
        print('Please give file name of dump')
        return
    filename = sys.argv[1]

    pages = 0
    words = 0
    words_counts = Counter()
    print('Processing dump')

    for page in XmlDump(filename).parse():
        if (page.ns != '0') or page.isredirect:
            continue
        try:
            text = mwparserfromhell.parse(page.text).strip_code()
        except Exception as e:
            print(page.title, e)
            continue

        text = text.replace('\u0301', '') # remove accents
        # Ukrainian: 

        # page_words = re.findall(
        #     r'[абвгґдеєжзиіїйклмнопрстуфхцчшщьюя'
        #     r'АБВГҐДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ’\'-]+',
        #     text
        # )
        
        # Any language:
        page_words = re.findall(r'\b[^\W\d]+\b', text)

        pages += 1
        words += len(page_words)
        words_counts.update(page_words)
        if pages % 123 == 0:
            print('\rPages: %d. Words: %d. Unique: %d. Processing: %s' % (
                pages, words, len(words_counts), (page.title + ' ' * 70)[:70],
            ), end='')

    print('Done. Writing csv')
    with open('common_words.csv', 'w', newline='') as csvfile:
        csvwriter = csv.writer(csvfile)
        for item in words_counts.most_common():
            csvwriter.writerow(item)

if __name__ == '__main__':
    main()

Він працює майже вдвічі швидше, 381 хвилину, бо обробляє лише 2,295,426 сторінок (обсяг німецької вікіпедії цього року). На цих сторінках є 1,074,446,116 слів (в середньому 468 на сторінку), з них різних – 12,002,417. (Виявляється є аж 6 мільйонів всяких слів які вживаються на всіляких службових сторінках німецької вікіпедії, і яких нема в статтях).

Якщо ж взяти українські статті, то на них треба ще менше часу – 131 хвилину (забув уточнити що в мене SSD), їх є 923238 (скоро мільйон!), слів 238263126 (в середньому 258 на сторінку, треба доповнювати 😉 ). З них різних – 4,571,418. Отак, в мене тепер є частотний словник української на 4.5 мільйони слів. І німецької на 12 мільйонів.

Хоча не спішіть з висновками що українська мова бідніша, бо мої методи потребують вдосконалення. По перше, так як Morgen (ранок) і morgen (завтра) – різні слова, то я не приводив букви в німецькій до одного регістру. (Правда й в українській забув це зробити).

По друге, в німецькому словнику 350590 разів зустрічається слово “www”, бо я вважав словом будь-яку послідовність літер латинки, а в українській відфільтрував кирилицю. Слово youtube зустрічається 8375 разів, а значить є ризик знайти якесь рідкісне слово на зразок “fCn8zs912OE”. 🙂

На WordPress глючить додавання картинок, тому нате вам відео:

А, і ось топ-10 української вікіпедії:

в,4551982
на,3730686
і,3475086
у,3353796
з,3053407
-,2695783
Категорія,2417267
та,2350573
до,1815429
року,1553492

Частота “року” наводить на думку що в українській вікіпедії якийсь перекос на історичні методи викладу. 🙂

Kubernetes з microk8s

Posted by on 07.04.2019 Коментарі Вимкнено до Kubernetes з microk8s

Kubernetes – це такий docker-compose на стероїдах, що дозволяє керувати кластером машин на яких запускаються контейнери. Infrastructure as a code, і всяке таке. Дивно що в цьому кібернетичному блозі про кібернетіс ще жодного разу не згадувалось, тому варто цю ситуацію виправити.

Інсталяція

Є різні способи поставити локально однонодовий кластер, minikube (з яким в мене не дуже вийшло), і microk8s, який на Ubuntu, і лінукси в яких є менеджер пакетів Snappy, ставиться так:

sudo snap install microk8s --classic

Це встановить кластер і CLI для керування кластером kubectl. Правда вона називатиметься microk8s.kubectl. Якщо ви не ставили kubectl окремо (можна через той же snap install) для керування кластером десь в хмарах, то можна зробити аліас, а якщо ставили – так можна переконфігурити її для роботи з локальним кластером:

microk8s.kubectl config view --raw > ~/.kube/config

Тоді можна наприклад отримати список нодів кластера:

$ kubectl get nodes
NAME                   STATUS    ROLES     AGE       VERSION
bunyk-latitude-e5470   Ready     <none>    3h        v1.14.0

Логічно що у випадку локальної інсталяції це буде лише один комп’ютер.

Щоб перемкнути kubectl на керування наприклад якимось кластером в хмарах Google, за умови що у вас встановлений gcloud, треба виконати:

gcloud container clusters get-credentials [CLUSTER_NAME]

Аддони й панель керування

Ще microk8s має команди для вмикання (enable) і вимикання (disable) аддонів:

microk8s.enable dns dashboard

dns потрібний для багатьох речей, тому його радять вмикати. dashboard – web UI, і InfluxDB з Grafana для моніторингу ресурсів. Щоб його побачити, треба викликати kubectl proxy і перейти за адресою: http://localhost:8001/api/v1/namespaces/kube-system/services/https:kubernetes-dashboard:/proxy/#!/login

Сторінка логіну

Там попросять залогінитись, щоб отримати JWT токен для логіну, треба виконати

kubectl -n kube-system get secret
# тоді в списку знайти ім'я що починається з kubernetes-dashboard-token-
# а тоді:
kubectl -n kube-system describe secret kubernetes-dashboard-token-c4bmp

Параметр -n означає простір імен, це щось на зразок директорії де лежать всі об’єкти кластера, наприклад секрети. Це також відображається в шляхах до API, як от /api/v1/namespaces/kube-system/services/https:kubernetes-dashboard:/proxy/ для доступу до сервісу https:kubernetes-dashboard. За замовчуванням kubectl працює з простором імен default, але у випадку вище, нам треба kube-system.

Запуск контейнерів в Kubernetes

Тепер може спробуємо щось запустити? Для цього треба створити под (pod – англійське слово що позначає групу китів. Вони взагалі дивні слова мають для цього. Зграя сов – це parliament, круків – murder). Под – це група контейнерів зі спільною IP адресою, які запускаються а ноді.

Найпростіший спосіб створити под – майже такий самий як запустити контейнер:

kubectl run nginx --image=nginx
# kubectl run --generator=deployment/apps.v1 is DEPRECATED and will be removed in a future version. Use kubectl run --generator=run-pod/v1 or kubectl create instead.
# deployment.apps/nginx created

Це говорить нам що команда створила deployment, але в майбутньому створюватиме лише поди, якщо не передати параметр --generator=run-pod/v1. Чому так пояснюють тут.

Що таке деплоймент? Нуууу, це важко пояснити, і це мене найбільше в Кубернетісі вибішує. Под – це набір конейнерів зі спільною IP адресою, набором портів, диском, і т.д. Под сам по собі запускати в kubernetes не рекомендують, бо після того як в нього трапиться якась аварія наприклад через закінчення пам’яті, його ніхто не перезапустить. Подом керує контролер, одним з яких є контролер що називається ReplicaSet, який задає кількість копій пода що мають бути запущені. І якщо одна з них з якихось причин здихає – запускається нова, щоб кількість завжди відповідала потрібній. Deployment – об’єкт що містить контролер ReplicaSet, і керує версіями імеджів контейнерів в подах цього контролера. Абстракцій як в TCP/IP…

Тим не менш, ми побачимо под в списку:

$ kubectl get pods
NAME                     READY   STATUS    RESTARTS   AGE
nginx-7db9fccd9b-w6468   1/1     Running   1          44h

Щоб видалити деплоймент разом з подами дають команду:

kubectl delete deployments/nginx

Трохи складніший спосіб створити под – написати маніфест:

apiVersion: v1 
kind: Pod
metadata:
  name: nginx
spec:
  containers:
    - image: nginx
      name: nginx
      ports:
        - containerPort: 80
          name: http
          protocol: TCP

Якщо його записати в файл, наприклад nginx.yaml, то щоб запустити:

kubectl apply -f nginx.yaml

Як подивитись що всередині пода? Можна прокинути порт, і тоді те що контейнери в поді віддають на якомусь порті буде доступно на порті localhost:

kubectl port-forward nginx 8088:80

Загальне правило для портів в Kubernetes (бо такі пари порт:порт зустрічаються часто) – зліва порти ззовні, справа – всередині. Якщо все працює, на http://localhost:8088 ви маєте побачити сторінку де пише “If you see this page, the nginx web server is successfully installed and working.”

Можна подивитись логи:

$ kubectl logs -f nginx
127.0.0.1 - - [31/Mar/2019:17:00:53 +0000] "GET /favicon.ico HTTP/1.1" 404 154 "-" "Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:66.0) Gecko/20100101 Firefox/66.0" "-"
127.0.0.1 - - [31/Mar/2019:17:01:56 +0000] "GET / HTTP/1.1" 304 0 "-" "Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:66.0) Gecko/20100101 Firefox/66.0" "-"

Як змінити те що под показує на головній? Створити якийсь html файл і закинути його командою:

kubectl cp index.html nginx:/usr/share/nginx/html/index.html

Хоча так не прийнято робити, і можна хіба що під час розробки. Краще додати файли в імедж за допомогою Dockerfile.

Запуск сайту

Але давайте вже зробимо щось серйозне на кілька контейнерів. Наприклад як в цій публікації було за допомогою docker compose, тільки за допомогою kubernetes: два контейнери, один з них nginx веб-сервер що віддає статичні файли для фронт-енду, інший – API на python що віддає дані графіків.

Таким чином файли backend.docker, dashboard.html і server.py можна скопіювати собі в проект без змін (звідси). nginx.docker напевне краще називати frontend.docker, і помістити туди лише файли фронт-енду:

FROM nginx

COPY dashboard.html /usr/share/nginx/html/index.html

Конфігурацію nginx ми змінювати не будемо, бо відповідальним за диспетчеризацію запитів між фронт-ендом і бекендом в нас буде штука що називається Ingress.

Тут, на відміну від docker-compose який сам наші контейнери може зібрати, їх треба створити вручну:

docker build -t frontend -f frontend.docker .
docker build -t backend -f backend.docker .

Покладемо конфіг для двох деплойментів у файл site.yaml і скажемо кластеру оновитись (kubectl apply -f site.yaml):

apiVersion: apps/v1
kind: Deployment
metadata:
  name: frontend-deployment
spec:
  selector:
    matchLabels:
      tier: frontend
  replicas: 1
  template:
    metadata:
      labels:
        tier: frontend
    spec:
      containers:
      - name: frontend
        image: frontend
        ports:
        - containerPort: 80
---
apiVersion: apps/v1
kind: Deployment
metadata:
  name: backend-deployment
spec:
  selector:
    matchLabels:
      tier: backend
  replicas: 2 # більше подів для бекенду, бо йому самому може важко.
  template:
    metadata:
      labels:
        tier: backend
    spec:
      containers:
      - name: backend
        image: backend
        ports:
        - containerPort: 80

Один файл в Kubernetes може містити описи багатьох об’єктів, розділені рядком що містить “—“. Так простіше працювати, бо треба менше команд kubectl apply, чи kubectl delete.

Якщо kubectl get pods показує що наші поди мають статус ErrImagePull або ImagePullBackOff, це означає що kubernetes намагається взяти імеджі не з нашого комп’ютера, а з докерхабу.

Виявляється треба ще додати їх в реєстр microk8s. Для цього:

microk8s.enable registry

docker tag backend localhost:32000/backend
docker push localhost:32000/backend
docker tag frontend localhost:32000/frontend
docker push localhost:32000/frontend

Підозрюю що це можна було зробити простіше і швидше якщо зразу називати імеджі правильним тегом. Але майстерність приходить з досвідом. 🙂 В кінцевому результаті ви маєте мати три запущені поди, в двох деплойментах.

І що з того? Поки нічого, бо IP адреси цих подів динамічно міняються (коли їх перезапускають). Для того щоб мати постійний доступ потрібен сервіс, який проксює доступ до подів заданих мітками (labels). Мітки це пари ключ-значення які чіпляються до об’єктів в Kubernetes. Коли ми в описі пода писали:

labels: 
  tier: backend

То це ми йому якраз задавали мітки. Тепер по мітках ми можемо ці об’єкти отримувати:

bunyk@bunyk-thinkpad:~/projects/dockerizing$ kubectl get pods -l tier=frontend
NAME                                   READY   STATUS    RESTARTS   AGE
frontend-deployment-695cfcc94c-jl5hg   1/1     Running   0          3h6m
bunyk@bunyk-thinkpad:~/projects/dockerizing$ kubectl get pods -l tier=backend
NAME                                  READY   STATUS    RESTARTS   AGE
backend-deployment-669d885465-cfbrc   1/1     Running   0          3h6m
backend-deployment-669d885465-nh8lg   1/1     Running   0          3h6m

Так само сервіс має надає доступ з постійним IP до набору подів заданого мітками. Сервіси створюються так:

apiVersion: v1
kind: Service
metadata:
  name: backend
spec:
  selector:
    tier: backend
  ports:
  - protocol: TCP
    port: 80
    targetPort: 8080
---
apiVersion: v1
kind: Service
metadata:
  name: frontend
spec:
  selector:
    tier: frontend
  ports:
  - protocol: TCP
    port: 80
    targetPort: 80

Сервіс має селектор що визначає за якими подами стежити, і відкриває порти. port – це який порт відкрити, targetPort – це до якого порта в поді приєднатись. За цим треба слідкувати, бо якщо не виконається одна з умов: порт на якому слухає сервер в контейнері == containerPort, containerPort == targetPort сервіса, port сервіса == порт до якого приєднується клієнт, то отримаємо помилку “Connection refused” чи подібну.

Після чергового kubectl apply -f site.yaml можна подивитись які сервіси отримуємо:

$ kubectl get services
NAME         TYPE        CLUSTER-IP      EXTERNAL-IP   PORT(S)   AGE
backend      ClusterIP   10.152.183.69   <none>        80/TCP    110m
frontend     ClusterIP   10.152.183.63   <none>        80/TCP    30m
kubernetes   ClusterIP   10.152.183.1    <none>        443/TCP   8d
$ curl 10.152.183.69/data/1
[1.0997977838,0.6222197737,0.7265324166,1.0475918458,0.8271129655,0.6489646475,0.3625859258,0.7692987393,1.1331619921,1.4889188394]

Бачимо що сервіси які ми створюємо мають тип ClusterIP. Це тип за замовчуванням, і означає що він буде доступний лише з середини кластера. Нам доступний, бо ми ж сидимо на одній єдиній ноді кластера. Крім нього є ще NodePort, LoadBalancer і ExternalName, але розбиратись що це – ми не будемо, бо й без того голова вже пухне (чи у вас ні?).

Залишився ще Ingress. Це штука що дає доступ до сервісів кластера ззовні кластера. Конфігурується так:

apiVersion: extensions/v1beta1
kind: Ingress
metadata:
  name: entrypoint
  annotations:
    nginx.ingress.kubernetes.io/rewrite-target: /$1
    kubernetes.io/ingress.class: "nginx"
spec:
  rules:
  - http:
      paths:
      - path: /api/(.*)
        backend:
          serviceName: backend
          servicePort: 80
      - path: /(.*)
        backend:
          serviceName: frontend
          servicePort: 80

Тут важливий параметр nginx.ingress.kubernetes.io/rewrite-target, який означає “передавати сервісу запит замінивши URL на той що вказано, підставивши групи з регулярного виразу в path“.

Після застосування цієї конфігурації, на localhost в нас завантажиться фронтенд, пошле через ingress запити до бекенду, і все навіть буде через HTTP 2.0.

Питайтесь якщо що не виходить чи не доходить, в мене теж багато з того що тут написано не виходило зразу, може я вже стикався з тими проблемами що у вас.

Хакери викрали базу даних пін-кодів!

Posted by on 01.04.2019 Коментарі Вимкнено до Хакери викрали базу даних пін-кодів!

Важлива інформація для власників банківських карток Visa і MasterCard, поділіться з друзями і знайомими щоб вони теж були попереджені.

Нижче викладаю копію бази даних з вкраденими пін-кодами. Перевірте чи ваш є серед них, і якщо є – рекомендую змінити на якийсь інший, якого нема серед списку зламаних.

3864, 0740, 1724, 9477, 9692, 0719, 9169, 7695, 0644, 9025,
8757, 1786, 7152, 8782, 7398, 3383, 2913, 8104, 0866, 1565,
0681, 2833, 1579, 9987, 5713, 8111, 1622, 4579, 7689, 4810,
3623, 6284, 7983, 8595, 8173, 8573, 6799, 1255, 2463, 9717,
6872, 6921, 5439, 5168, 6978, 8333, 5302, 6371, 7676, 4062,
1911, 8599, 4640, 0750, 0971, 8859, 4114, 9969, 9102, 2052,
3787, 7656, 5297, 1187, 0656, 4274, 0369, 5718, 0226, 2875,
3113, 9382, 1763, 2470, 0084, 9767, 0449, 9948, 2577, 0557,
7480, 6452, 7142, 8311, 8879, 3620, 2700, 7410, 8362, 5169,
9765, 4037, 0641, 0501, 4175, 6569, 8188, 0221, 9017, 2527,
7282, 0956, 7596, 5308, 7536, 7226, 8946, 0156, 2002, 8137,
4896, 0571, 6581, 1014, 6985, 4279, 3079, 2270, 0095, 3056,
4090, 9769, 3563, 5806, 8747, 3266, 6158, 6053, 7595, 5516,
1178, 3140, 3512, 7198, 9561, 6281, 1118, 5999, 1280, 0192,
1207, 0566, 2968, 7170, 2244, 0859, 2125, 1091, 1878, 1361,
0581, 1639, 9811, 0132, 5290, 0870, 2274, 8950, 4281, 4831,
6947, 9739, 3131, 9534, 4259, 9395, 4193, 7989, 5097, 2706,
2630, 7653, 3012, 7047, 3493, 6967, 2994, 0171, 1013, 4742,
5684, 7926, 3730, 8013, 7835, 3389, 8477, 0417, 9402, 4595,
2893, 4408, 2775, 3927, 8874, 8180, 2799, 2213, 0808, 6865,
7563, 9537, 1415, 0535, 8742, 5078, 9617, 7916, 2538, 2970,
4665, 0973, 7383, 8185, 1168, 4111, 3324, 4079, 5648, 6547,
2627, 6477, 8804, 6897, 9110, 0622, 5747, 9593, 7373, 8016,
4733, 4685, 4480, 6102, 0105, 1259, 5916, 5140, 0203, 6537,
3284, 6859, 4723, 6948, 0058, 9761, 0450, 7324, 7864, 2878,
7601, 8624, 6287, 6654, 4459, 3696, 1314, 7350, 9774, 9676,
5859, 1278, 2942, 9356, 8484, 0585, 3216, 2543, 0359, 3406,
9173, 5397, 3566, 9039, 5832, 2603, 9194, 1437, 5312, 5923,
6339, 1950, 4659, 5430, 1700, 5532, 4383, 5549, 2039, 4146,
2948, 1919, 9283, 2363, 3031, 2446, 9837, 8302, 4784, 7088,
8737, 2098, 6783, 9803, 1931, 0605, 7106, 1395, 9580, 6964,
4081, 7443, 8714, 8373, 2599, 6734, 6631, 5772, 2456, 6078,
5614, 2823, 4512, 1506, 6469, 4444, 1533, 6694, 0135, 4177,
8177, 3960, 2136, 6636, 5218, 7268, 9478, 6989, 4481, 4704,
1748, 3448, 4123, 1970, 0107, 5646, 2138, 0302, 0508, 3669,
3248, 5537, 4457, 6900, 7834, 1003, 8592, 2848, 0630, 2835,
5650, 6313, 9176, 0224, 1578, 2018, 8244, 3336, 3293, 2703,
1617, 9213, 2330, 2810, 4338, 3789, 4181, 2150, 6582, 4241,
4971, 9514, 1534, 1709, 8055, 1281, 2028, 1910, 8360, 8376,
8844, 5584, 1905, 3384, 0497, 7527, 1421, 7978, 4922, 1751,
3451, 8542, 6915, 9589, 6198, 8893, 1159, 8621, 3124, 5323,
5130, 2663, 4606, 0029, 1140, 6562, 7169, 6496, 5210, 9683,
4106, 1463, 4245, 3442, 9555, 3617, 0057, 1319, 1459, 9442,
2648, 4581, 1083, 6265, 2637, 6120, 8891, 9367, 8666, 8383,
7505, 4051, 7448, 0368, 2406, 6898, 7547, 2934, 4505, 2029,
3203, 9016, 0175, 6357, 9192, 0722, 6927, 5185, 0910, 9677,
2884, 4791, 6068, 9480, 8701, 0659, 3633, 3444, 9918, 9518,
4029, 8722, 8237, 1033, 3545, 0218, 7077, 6655, 1796, 7129,
0793, 8262, 3677, 6319, 1254, 2536, 1667, 6311, 1651, 5239,
8529, 4300, 1327, 7165, 0305, 4005, 5906, 5172, 6170, 1222,
3661, 5628, 2315, 5194, 6369, 4525, 4441, 1338, 3338, 2295,
6196, 6676, 8106, 6308, 2242, 8943, 4275, 2972, 4312, 3842,
6572, 6223, 5246, 2044, 6290, 7305, 6980, 4541, 3341, 0577,
2982, 5432, 5847, 5900, 2817, 1416, 6168, 9200, 4061, 0608,
3096, 7900, 8141, 3682, 6760, 3945, 5444, 7207, 1233, 4612,
8221, 9335, 0683, 7313, 4930, 2302, 0758, 5322, 4218, 3117,
1560, 5217, 9116, 4575, 8037, 5616, 9154, 4095, 7614, 2217,
3808, 2558, 7590, 3837, 3953, 2212, 8814, 0055, 4486, 2766,
5519, 3773, 7725, 8327, 5227, 7773, 3564, 8507, 2572, 3147,
0045, 0012, 8734, 4040, 0406, 8089, 4045, 2384, 9922, 0906,
3987, 6279, 3656, 9427, 2801, 8517, 5402, 3485, 7707, 0926,
2355, 7925, 7830, 2267, 5680, 3121, 4901, 8020, 7086, 8287,
7075, 4298, 5336, 1098, 6450, 3008, 4100, 1038, 0002, 8133,
3465, 7585, 5542, 5085, 5113, 8393, 6662, 7785, 6101, 0377,
6901, 9094, 1402, 4940, 0204, 2530, 3159, 5479, 6837, 1965,
9566, 9180, 6394, 6204, 9626, 0485, 6622, 4327, 0286, 2619,
0927, 7476, 7817, 1080, 7583, 3285, 2402, 7173, 7074, 0903,
8956, 6262, 8215, 3781, 7661, 0921, 9361, 0546, 8099, 9935,
7250, 0934, 6163, 3723, 6471, 4891, 0781, 2444, 1856, 4652,
7561, 5655, 6798, 0053, 0200, 2915, 5736, 9545, 8466, 0896,
1714, 2834, 1239, 8947, 0350, 6924, 7843, 6334, 0580, 2190,
2126, 6485, 7894, 0770, 4771, 8839, 9616, 6138, 7886, 7258,
8985, 4778, 0661, 6309, 6959, 1339, 7683, 3354, 9179, 9129,
8555, 5459, 2748, 3177, 2753, 4421, 2474, 0728, 3874, 2759,
4404, 3852, 2373, 7950, 7504, 1587, 3297, 6506, 0734, 7703,
1876, 6766, 8550, 6748, 7699, 5848, 2714, 0332, 3556, 1861,
5343, 9410, 9222, 3818, 6351, 8172, 7130, 7848, 0930, 1584,
7049, 3339, 5467, 4836, 1483, 4398, 8828, 4998, 3719, 1630,
5033, 1161, 8129, 7454, 3839, 3796, 0673, 8538, 5405, 7417,
7850, 7180, 8449, 6318, 0478, 3849, 4591, 9818, 0802, 7220,
0001, 2618, 4775, 2571, 3394, 2060, 7858, 6730, 7185, 6998,
0774, 5845, 2058, 9806, 1262, 5386, 4240, 4638, 7871, 0714,
7507, 1400, 4463, 4164, 2185, 5786, 9550, 9340, 6956, 9982,
2401, 0594, 9747, 1518, 6552, 6958, 8924, 4994, 0589, 1124,
9559, 9265, 9598, 4617, 3923, 1864, 7914, 1503, 4409, 4424,
3668, 7177, 4488, 2062, 0679, 5705, 2698, 9791, 4780, 5337,
1283, 6727, 2642, 6345, 3710, 4788, 4961, 2563, 8155, 5536,
9907, 6040, 3883, 8211, 9758, 3334, 1330, 1441, 9888, 8260,
8535, 7660, 4564, 5810, 1827, 4538, 5488, 0678, 0847, 4635,
6036, 4115, 1436, 3473, 8496, 8219, 1186, 2846, 8464, 7801,
2768, 4487, 1740, 9088, 7751, 2568, 7667, 7014, 3274, 8543,
4958, 2855, 3078, 0036, 0599, 9796, 0459, 0471, 9865, 7933,
8028, 1853, 5796, 6015, 5686, 4350, 6789, 6228, 6651, 4761,
4852, 7760, 8851, 5055, 3435, 7141, 9019, 7315, 0845, 4418,
1169, 1887, 6151, 1753, 3430, 8307, 5213, 9127, 2657, 1042,
4180, 4392, 4176, 7842, 7414, 0371, 8108, 6935, 3912, 0479,
7138, 9103, 6514, 5309, 2146, 3901, 3158, 8179, 3732, 5494,
5099, 2078, 7515, 6248, 6263, 7792, 5087, 2194, 2844, 9332,
3974, 3930, 1604, 3827, 5964, 0744, 1144, 3092, 3658, 5534,
1109, 4602, 4965, 2148, 8526, 2583, 5971, 6073, 3878, 4967,
6690, 1964, 5139, 4859, 7037, 2225, 0806, 8664, 1993, 0024,
8606, 0065, 8421, 0709, 0270, 7593, 5716, 8422, 6277, 2240,
4904, 2475, 9781, 6673, 6518, 8334, 8512, 9726, 5627, 2390,
6819, 7110, 3745, 7459, 5769, 5568, 5603, 5849, 2631, 6379,
6304, 0550, 7643, 7010, 6236, 9123, 4454, 8723, 8007, 9938,
7974, 9602, 6642, 5346, 0682, 2927, 5706, 7356, 5049, 2032,
7061, 9429, 3618, 7705, 9351, 0849, 3725, 5195, 0010, 5120,
2323, 2485, 2491, 5996, 2533, 6672, 4772, 8495, 0405, 5105,
6814, 3360, 9928, 3445, 2828, 4108, 4048, 1992, 9331, 8143,
5410, 4013, 7294, 1266, 5320, 2842, 1089, 0510, 1375, 2460,
7007, 7377, 6891, 4862, 6637, 5870, 7651, 7070, 8184, 6728,
9280, 7151, 0708, 0180, 1528, 5780, 1412, 2450, 7627, 1536,
5581, 0841, 2051, 9115, 1363, 5854, 1300, 8981, 1793, 4705,
9836, 3798, 5329, 9930, 7063, 8336, 1713, 3461, 9754, 1727,
4795, 2862, 7486, 7379, 1360, 0592, 9021, 1066, 5393, 0173,
5269, 2550, 0223, 1803, 7669, 6330, 3522, 2981, 9329, 7140,
3834, 7238, 4417, 0185, 7692, 3179, 6361, 7604, 5412, 3704,
5585, 8767, 4543, 9375, 0799, 8746, 9587, 4523, 9633, 6902,
0555, 7615, 0470, 0898, 8486, 9435, 1062, 6146, 1581, 3090,
5869, 5509, 6289, 4578, 7255, 2208, 3443, 2763, 3794, 0303,
8522, 4145, 7499, 6189, 3977, 4949, 7594, 3486, 3739, 4058,
8006, 6439, 0826, 6466, 5359, 5328, 8241, 2622, 4552, 8440,
7247, 6903, 7898, 8416, 5276, 7360, 8934, 6039, 7956, 3811,
5026, 6739, 7158, 4741, 5556, 0760, 0846, 2928, 2234, 1461,
6037, 2963, 7889, 1738, 8911, 1721, 6090, 1410, 9236, 8744,
6275, 2929, 6983, 5707, 1800, 0074, 3112, 2197, 7501, 3000,
6250, 5899, 5790, 7880, 8781, 8793, 0692, 7684, 8035, 4739,
7597, 6781, 2164, 8634, 4049, 3242, 1945, 8581, 0619, 6406,
0446, 9897, 3984, 5478, 4601, 5700, 5755, 3091, 2783, 9206,
3872, 0618, 8222, 0712, 1755, 5812, 6020, 1341, 8337, 4490,
3928, 0165, 3508, 0604, 4577, 3496, 2764, 6849, 9698, 9106,
6885, 1947, 2582, 7011, 4945, 1619, 3913, 1670, 4030, 2868,
7386, 7639, 5697, 9457, 0680, 0050, 4113, 3491, 2025, 9573,
4229, 4509, 9533, 3490, 8561, 5001, 6839, 2777, 4353, 4011,
8867, 8504, 3025, 5504, 7608, 2725, 2781, 4002, 7237, 0919,
3005, 6848, 9249, 3361, 6117, 0631, 5985, 2145, 2705, 9569,
3502, 2054, 4410, 4162, 8686, 4574, 4550, 7944, 3628, 3549,
3881, 2055, 9908, 9789, 9619, 0395, 9916, 6811, 3514, 3188,
6110, 9630, 4380, 4047, 6663, 4135, 6197, 7146, 8202, 1808,
8966, 0463, 1078, 5436, 1521, 9586, 7573, 3365, 8511, 6123,
5611, 1448, 2830, 2798, 8046, 5608, 0703, 0083, 3528, 7036,
5975, 8560, 5485, 5373, 5414, 8240, 0603, 5464, 8491, 9656,
8413, 6567, 9735, 5801, 9842, 5275, 1798, 5282, 6738, 0275,
5757, 4985, 4264, 6752, 3097, 6388, 2459, 4309, 4700, 6105,
4092, 0584, 5262, 7550, 1424, 1673, 6002, 1966, 2412, 7824,
8622, 9503, 2299, 0202, 5620, 2329, 3998, 3143, 7111, 6402,
6668, 7805, 8698, 5761, 8341, 8697, 4139, 1444, 9575, 6986,
4465, 9637, 5468, 6793, 1231, 1882, 9282, 8688, 3357, 0283,
9065, 1121, 8679, 8715, 0848, 5884, 2151, 8431, 7378, 5918,
0241, 9376, 2129, 2825, 4800, 3413, 2887, 4783, 5100, 2324,
9662, 2815, 7574, 9614, 9687, 2065, 8575, 2484, 1875, 6788,
6306, 3886, 9731, 1193, 3503, 9931, 6926, 5559, 4802, 8293,
0726, 2339, 6292, 5122, 1116, 1468, 1754, 6666, 3625, 4589,
0989, 4702, 1246, 7164, 4396, 7104, 7682, 7712, 5885, 5002,
3082, 3866, 0638, 3516, 2079, 4560, 9168, 4611, 2720, 5897,
0014, 8724, 5424, 1473, 6623, 8764, 1593, 5433, 9519, 7882,
7758, 6178, 0974, 5607, 5926, 4572, 3724, 0481, 0148, 6714,
8868, 4390, 7449, 7954, 5606, 7302, 7551, 5866, 8975, 1934,
8331, 4927, 7610, 5800, 3973, 5431, 4708, 9126, 8965, 8898,
7076, 6004, 8989, 3965, 3650, 4838, 0789, 4001, 2312, 8290,
5924, 3006, 0287, 8051, 9590, 3237, 8577, 2641, 6586, 0913,
1583, 4271, 9621, 6740, 2119, 1814, 0062, 0136, 0364, 0217,
2930, 7645, 5820, 1516, 3042, 6977, 3320, 4963, 6274, 4262,
4349, 1897, 6553, 6392, 7053, 9620, 7804, 8380, 9202, 0169,
4249, 3565, 8770, 1488, 2897, 4661, 9994, 6399, 9582, 2340,
6608, 0489, 4434, 8206, 9319, 7538, 4293, 2564, 4310, 5797,
8865, 4988, 6192, 9069, 1862, 6930, 9431, 1799, 1869, 6652,
8073, 3517, 2755, 1904, 7921, 3815, 6372, 6283, 3434, 0706,
1467, 4420, 3220, 1635, 3185, 0876, 7374, 4291, 4916, 9091,
9622, 0206, 9946, 9507, 1315, 8559, 2130, 5936, 7102, 0916,
1618, 7840, 6257, 0273, 2100, 0109, 7307, 7784, 1053, 6671,
7814, 0784, 9755, 2849, 8524, 2247, 8116, 4766, 6431, 1981,
6129, 8813, 4567, 9001, 5836, 0499, 9889, 4280, 4054, 7548,
6224, 8952, 2988, 9311, 2448, 1508, 8820, 5234, 7958, 9306,
3637, 4121, 4296, 9406, 9303, 3645, 0457, 6087, 8195, 8052,
6960, 4828, 7498, 2722, 4402, 0477, 9965, 3657, 0043, 2027,
2265, 8902, 1210, 7068, 1149, 3302, 2076, 1780, 0429, 7280,
2420, 1757, 3481, 3271, 0560, 6210, 8100, 4254, 6744, 9663,
6831, 6436, 4499, 2900, 3457, 8794, 2980, 3116, 8248, 3554,
7654, 8986, 3700, 0131, 0843, 5922, 8808, 8261, 4983, 3483,
2811, 4484, 1728, 6806, 3368, 2219, 4990, 5995, 4071, 5910,
5639, 9830, 9768, 2610, 7631, 3303, 4494, 3624, 3396, 2911,
1985, 3207, 2468, 5295, 9847, 8268, 2399, 8056, 9484, 4342,
9937, 4951, 5644, 6875, 2426, 6317, 9368, 0657, 5751, 6944,
4214, 3941, 7473, 4805, 5704, 0070, 8665, 4248, 2307, 5991,
4143, 8374, 8493, 1571, 8395, 1885, 5261, 2180, 7055, 7714,
9472, 9262, 9821, 2015, 2084, 7906, 6412, 6866, 2179, 7815,
6937, 6396, 6270, 7671, 9250, 2255, 9006, 7124, 4619, 8662,
1279, 3687, 0640, 0178, 8645, 4445, 0101, 4917, 0415, 2154,
7062, 0028, 0087, 6316, 1423, 2634, 0181, 4514, 0886, 2511,
2251, 0732, 0504, 6136, 8569, 4423, 8320, 4221, 6882, 2520,
4648, 4626, 1990, 5660, 8537, 1519, 7788, 4754, 7460, 3166,
6682, 3572, 0151, 6656, 6702, 9817, 1685, 0149, 4627, 0606,
6871, 1588, 1455, 7017, 4566, 5589, 0404, 1918, 2813, 2754,
8095, 5495, 5889, 0905, 8372, 6449, 3162, 0655, 6172, 8003,
9659, 3532, 2316, 0923, 6344, 0700, 6384, 6940, 1580, 5933,
1690, 2380, 1209, 2903, 2841, 5237, 4670, 9226, 6080, 1499,
1223, 9872, 4260, 3751, 7971, 3337, 8572, 9744, 2041, 5107,
2654, 8130, 7286, 5522, 0649, 4743, 4147, 2924, 4124, 9455,
4483, 8405, 8999, 4546, 7786, 6305, 2733, 4528, 6713, 0790,
0554, 4394, 4122, 7288, 5266, 5031, 1044, 3098, 5472, 4453,
0851, 2638, 3534, 7687, 6880, 9841, 3244, 9352, 0925, 0575,
1566, 8806, 0626, 2261, 9076, 9295, 7069, 2121, 3484, 8377,
9174, 1741, 1347, 7197, 0064, 3494, 6064, 4059, 1139, 2843,
1127, 7087, 7532, 4238, 8980, 9144, 1929, 4680, 4982, 0126,
7940, 9762, 6796, 7718, 4508, 4752, 3648, 1369, 7284, 5365,
5632, 8935, 4746, 0742, 6298, 8583, 4035, 5164, 5220, 6840,
8936, 0091, 4948, 6733, 4864, 1196, 1792, 0194, 3996, 5404,
2405, 2925, 0811, 1203, 7934, 3937, 0561, 0725, 5533, 0365,
3816, 7500, 2220, 9815, 5156, 7721, 0069, 5191, 8216, 5370,
4542, 0296, 7920, 3353, 1956, 9856, 7234, 9652, 2199, 4727,
0816, 5540, 8426, 7865, 5277, 1305, 4473, 7572, 7400, 4346,
8256, 6232, 9795, 1236, 0140, 0130, 5914, 7947, 7340, 0396,
3952, 4331, 4334, 1440, 7428, 4888, 0582, 9625, 6285, 6593,
6688, 2209, 5199, 4834, 8481, 4556, 6483, 0791, 5006, 9711,
9909, 4110, 9235, 8892, 6378, 5956, 5852, 9274, 3575, 8030,
4776, 0000, 9880, 0780, 3797, 6580, 6108, 8881, 2605, 6033,
0620, 3601, 2851, 3597, 5930, 9018, 4504, 7121, 3075, 5442,
5586, 9121, 8596, 8766, 3015, 5017, 1150, 7366, 4131, 9512,
4587, 8264, 7182, 2435, 1871, 3466, 3135, 5251, 2278, 4169,
2441, 2374, 8409, 5615, 1908, 3254, 1646, 7577, 7496, 9086,
6767, 8445, 1466, 3888, 3193, 7174, 7045, 3452, 0161, 2181,
6777, 5048, 2228, 8921, 2354, 2523, 5021, 8453, 4530, 1711,
0420, 5137, 7368, 4397, 9618, 8834, 9708, 3144, 5250, 1208,
1954, 1119, 8907, 1336, 2085, 7031, 8882, 6749, 6769, 5604,
3542, 3529, 6556, 0021, 2017, 6782, 5077, 7673, 5583, 1225,
0439, 4605, 8403, 6693, 9672, 9119, 0133, 7735, 6411, 6532,
1683, 2030, 3447, 3767, 1899, 3743, 2277, 0563, 9277, 3922,
3373, 6869, 4157, 6245, 4442, 0509, 0990, 7396, 6195, 2457,
0516, 9802, 9562, 3346, 4360, 8295, 9814, 0825, 3896, 7808,
5171, 4999, 4847, 6144, 8407, 6610, 6488, 7798, 4809, 9393,
4154, 2043, 4088, 9238, 2088, 0338, 4347, 5988, 5808, 7336,
3791, 0018, 7442, 4460, 8590, 3612, 9822, 7779, 7528, 5236,
8183, 0871, 0430, 2551, 9398, 2254, 0387, 4026, 5829, 2954,
2472, 8385, 9995, 5425, 9163, 2492, 1485, 1312, 9991, 8047,
6258, 8983, 1620, 4586, 6854, 4933, 3214, 6516, 1539, 4469,
6946, 7904, 4962, 3702, 8765, 2788, 8454, 0858, 7201, 8470,
4493, 2547, 6301, 1232, 0972, 6987, 3956, 8546, 2504, 3537,
1469, 0995, 1623, 1460, 8909, 3149, 3943, 3875, 7490, 0597,
4078, 4448, 0079, 5383, 7485, 3510, 2907, 0850, 5500, 6614,
3010, 3137, 4534, 9642, 1308, 3148, 1545, 5163, 3123, 2337,
4458, 9902, 9599, 1113, 9464, 2050, 5453, 2010, 5376, 7862,
3152, 4779, 0327, 8492, 7002, 7633, 3546, 9910, 2743, 0665,
7516, 2352, 0949, 4696, 7566, 9132, 0602, 3414, 1435, 0531,
7616, 5144, 6322, 3472, 6419, 6609, 3201, 3540, 0600, 8852,
5677, 5908, 9945, 4853, 5173, 7034, 7530, 8113, 4747, 0889,
2860, 5283, 3412, 7406, 5079, 1006, 7833, 2726, 9309, 7224,
1917, 5837, 5197, 4055, 1705, 3057, 9143, 6808, 6175, 3480,
2131, 6423, 4837, 7477, 4009, 6487, 4887, 7134, 0807, 0214,
3080, 4211, 7825, 0737, 6029, 5574, 2883, 6239, 6577, 6227,
2465, 1470, 7192, 4225, 1111, 1880, 5787, 5093, 0228, 5548,
0735, 0271, 6949, 1275, 9438, 0379, 6205, 2609, 1973, 0280,
3427, 9278, 1332, 3523, 1035, 8072, 6147, 0436, 7762, 3576,
6440, 5267, 6615, 4819, 3047, 3145, 7755, 3642, 7445, 3726,
7521, 9612, 5317, 0578, 3364, 7016, 2670, 9373, 2366, 4529,
5258, 8146, 0730, 8427, 0621, 1672, 4669, 7153, 3232, 9704,
9860, 2896, 5029, 8925, 0539, 2746, 6349, 0004, 3602, 8750,
3990, 3476, 0150, 9139, 1695, 5358, 2852, 2007, 5841, 5934,
0265, 7278, 5635, 0157, 8153, 5683, 2744, 9259, 3526, 1260,
6076, 3178, 0966, 0819, 7984, 2546, 6890, 3558, 1572, 8597,
6093, 5005, 9160, 6159, 2836, 9716, 8919, 0176, 3366, 0517,
9675, 6167, 6936, 1844, 3380, 4526, 1843, 4148, 5157, 0299,
3711, 0086, 7724, 1860, 0020, 6953, 6100, 3843, 2490, 1472,
9408, 9912, 2046, 4373, 2590, 6768, 2003, 3153, 2281, 3175,
1155, 0023, 8610, 0899, 3790, 7210, 1735, 8661, 4511, 5843,
9330, 6075, 3639, 1434, 2923, 9416, 2771, 2210, 2250, 6478,
3632, 1271, 4703, 9254, 8075, 4594, 0085, 9788, 5658, 8398,
7149, 6994, 9165, 8796, 5682, 7803, 8970, 7980, 5245, 5782,
8402, 3997, 5860, 5111, 1564, 2389, 6934, 3468, 6203, 4257,
8974, 6164, 7875, 7229, 8384, 8370, 6446, 7329, 6288, 4628,
9448, 0372, 9162, 2137, 8489, 4039, 6523, 8014, 2673, 7239,
3238, 9886, 8967, 2009, 7289, 8716, 9996, 6504, 0766, 0076,
1652, 5795, 6348, 5625, 1112, 0503, 7759, 0155, 2600, 7194,
6757, 3821, 5496, 6750, 0540, 9695, 6823, 6852, 5043, 3115,
7079, 6030, 1643, 1394, 3231, 0912, 1998, 2292, 9474, 5567,
5984, 2606, 4414, 2690, 7912, 5117, 3498, 9260, 8008, 8263,
5324, 9027, 1625, 9824, 3322, 0162, 5123, 7598, 0761, 8756,
1609, 9591, 8226, 1951, 0264, 7276, 8438, 9152, 2540, 4959,
7318, 8721, 4097, 5932, 0462, 8995, 5118, 3660, 2361, 9964,
9137, 4984, 5473, 7932, 7578, 5062, 2249, 5973, 0201, 8783,
4921, 9420, 8728, 4519, 8323, 7420, 3183, 3058, 8459, 3067,
6307, 5892, 8900, 9058, 9028, 3895, 4683, 5415, 9199, 5873,
4149, 5009, 6337, 7004, 8408, 0860, 2192, 9108, 5838, 3980,
5223, 1636, 1863, 6709, 9149, 1163, 9868, 3068, 5440, 3903,
1184, 6413, 2453, 2898, 5247, 4716, 5944, 8628, 6536, 0552,
0389, 2707, 7589, 4242, 5774, 6060, 2667, 3698, 0112, 1857,
5618, 5146, 2804, 1867, 3567, 2072, 7051, 2909, 9100, 8346,
8478, 4996, 0444, 7433, 4634, 5828, 6763, 0191, 0052, 7999,
4395, 6813, 9211, 6458, 5826, 7931, 4223, 8210, 7352, 0945,
1744, 3141, 4192, 1542, 2552, 9007, 5633, 1489, 0512, 3352,
1884, 6551, 4070, 2489, 7893, 9449, 8643, 6206, 6703, 9272,
0329, 1354, 7330, 1839, 1913, 0351, 6461, 3102, 3146, 3684,
0262, 0915, 6566, 0521, 3294, 1450, 4816, 2407, 8321, 0534,
7763, 9543, 5480, 6607, 8745, 5876, 3241, 3393, 7713, 3251,
2149, 6981, 7081, 5147, 3538, 9389, 3167, 1986, 5114, 0731,
4884, 6653, 4804, 5012, 9246, 9516, 8582, 9318, 4811, 4824,
9440, 7731, 6600, 3871, 8680, 9952, 7463, 7857, 9022, 2776,
7331, 5510, 4027, 0413, 2350, 1840, 8423, 6877, 7172, 8271,
3482, 8675, 1944, 8992, 8077, 9772, 8639, 6114, 3775, 7975,
1562, 8068, 4794, 0588, 5115, 6550, 7923, 1306, 6145, 9348,
9463, 2230, 3038, 9245, 7093, 7670, 7783, 2794, 6557, 6829,
2626, 9867, 9751, 3854, 9520, 6422, 5982, 8775, 3330, 2560,
8817, 4540, 1939, 6975, 7993, 3204, 3520, 3527, 6941, 3931,
9403, 7966, 6343, 6363, 3219, 0428, 7506, 9876, 6297, 6723,
8388, 1277, 1959, 1938, 9392, 3718, 6089, 9362, 4044, 9156,
7482, 6792, 5783, 6619, 4906, 5175, 4876, 9015, 2699, 5505,
2166, 0568, 2922, 2585, 0435, 0035, 2021, 8065, 1376, 5514,
0196, 6453, 2992, 6312, 0355, 6429, 5470, 6520, 8836, 7244,
9530, 4285, 5811, 7218, 8430, 7407, 5763, 9869, 9560, 2451,
9494, 1835, 9098, 7320, 0097, 2569, 4000, 5752, 3530, 8562,
5969, 2290, 0653, 8725, 6049, 2403, 4478, 4905, 5641, 5535,
4920, 7089, 8612, 8740, 0775, 6578, 1383, 5003, 9718, 5685,
0480, 6678, 1023, 3559, 9953, 8134, 7246, 1501, 6932, 5746,
2729, 9529, 2232, 6628, 8888, 5334, 7467, 7403, 5326, 9723,
5034, 5028, 0361, 8417, 8444, 3261, 7775, 1302, 8635, 6052,
8738, 8700, 2103, 9328, 9225, 3792, 0515, 9218, 7139, 2201,
9239, 1249, 3616, 7781, 3999, 6303, 5233, 9451, 8091, 9877,
5198, 5601, 9960, 4191, 3548, 8668, 9053, 0523, 3715, 1107,
4019, 2795, 5551, 5378, 8247, 9904, 3609, 9000, 6393, 9631,
8322, 7659, 4237, 7028, 3224, 5835, 9035, 5461, 4374, 9850,
6185, 4206, 1837, 2553, 5407, 3729, 7555, 9736, 6428, 1968,
0537, 4084, 3195, 7630, 4923, 2767, 9413, 8269, 4858, 7113,
4236, 9578, 6909, 2173, 8345, 1452, 3926, 6182, 0526, 6661,
4757, 8289, 3259, 1403, 8510, 3955, 7810, 6834, 7000, 4910,
9549, 4662, 9347, 7588, 0798, 1120, 8349, 4052, 1649, 4369,
6887, 3695, 1665, 4593, 7393, 9054, 3478, 1669, 7300, 9343,
3351, 6965, 9227, 3186, 2440, 1859, 7813, 7421, 0453, 7821,
6106, 8436, 6955, 2455, 8598, 2259, 4359, 2784, 3329, 8729,
0077, 6451, 9970, 8988, 9357, 1250, 1742, 9978, 4649, 1418,
5035, 1396, 5152, 0513, 9316, 1012, 0901, 0357, 9949, 9942,
1906, 4431, 3150, 7319, 0893, 4718, 2620, 0015, 6701, 7233,
5497, 5399, 9417, 2633, 1760, 1290, 8523, 6416, 5915, 8488,
6282, 8953, 6679, 6044, 1274, 9606, 4074, 4903, 9540, 8699,
2241, 2322, 0688, 2760, 4942, 6300, 4877, 5136, 5649, 0068,
6966, 6014, 2499, 8987, 1294, 0596, 5273, 4516, 6559, 8358,
0320, 2623, 6286, 3807, 3161, 4970, 1824, 5831, 9851, 4844,
0102, 7462, 1606, 9320, 2397, 1873, 6641, 5538, 9010, 6770,
3611, 5904, 5437, 7204, 6479, 1202, 6395, 1174, 1151, 0310,
3659, 1454, 8916, 3379, 5791, 2541, 9921, 7175, 5203, 5361,
2785, 1624, 4873, 9288, 9905, 0227, 8259, 1099, 6845, 7756,
6945, 6094, 0233, 1147, 9059, 0138, 3424, 7849, 4270, 4099,
8547, 4341, 9422, 6320, 2702, 6645, 5668, 4125, 6046, 6705,
7658, 9297, 0970, 3312, 1077, 8136, 5484, 5619, 0115, 7458,
3024, 8702, 6410, 6974, 0699, 3046, 2693, 4713, 3735, 1433,
4233, 4212, 0704, 7736, 9740, 9792, 2369, 0215, 6109, 3055,
8004, 7807, 2793, 3401, 6019, 7098, 3606, 8863, 6062, 8469,
1576, 5158, 3771, 2643, 6665, 8415, 4185, 3629, 9148, 8069,
8818, 7742, 8963, 3250, 2187, 4520, 6418, 0495, 9233, 0134,
8776, 1173, 0613, 7103, 3004, 9047, 8840, 9525, 7348, 9644,
1096, 6710, 0643, 6647, 1895, 0037, 8439, 9648, 9701, 7739,
2574, 3673, 9230, 2586, 2461, 8365, 8800, 6256, 2508, 8713,
8578, 3590, 5069, 7922, 5486, 7054, 0047, 0098, 0245, 9023,
8175, 0716, 2990, 8877, 5629, 7099, 0869, 9927, 5434, 4203,
9038, 0409, 4817, 0358, 0785, 4932, 5765, 4866, 6971, 4600,
7413, 4267, 5691, 2141, 6725, 3070, 8010, 6222, 8252, 2614,
1075, 2421, 7494, 6853, 4160, 1995, 0170, 5289, 1220, 9009,
4881, 1817, 7235, 3905, 9694, 0274, 0647, 7231, 0375, 7344,
8361, 3929, 4597, 4875, 0507, 4173, 4898, 5121, 3573, 4256,
5316, 2269, 8918, 7518, 6154, 4252, 5004, 2415, 7951, 6979,
2684, 3506, 1820, 1036, 3198, 6335, 6755, 0393, 2471, 9570,
3350, 1828, 0902, 2742, 0979, 6726, 3638, 1476, 1502, 9399,
1737, 0804, 7225, 2378, 0370, 3157, 2318, 5143, 4066, 6332,
8931, 4126, 3100, 5208, 9521, 1989, 1557, 5689, 1532, 8717,
9954, 0533, 2343, 1858, 1602, 1263, 6238, 6611, 1668, 8853,
5762, 2357, 8208, 8140, 1889, 9989, 0419, 2865, 2171, 1819,
3233, 4155, 1716, 7623, 8249, 9212, 0094, 9004, 7046, 7948,
3975, 4513, 8224, 5011, 3077, 1980, 5688, 4846, 0612, 3727,
3578, 7512, 3164, 2391, 6715, 8471, 2207, 0174, 3515, 0118,
1783, 0936, 6299, 6444, 4366, 8225, 3947, 8948, 8117, 9906,
7998, 4666, 7312, 2026, 2696, 3407, 7135, 0773, 3218, 5764,
5696, 1822, 5724, 8772, 0308, 9011, 2856, 0838, 3712, 8920,
8866, 5417, 5252, 8286, 8480, 4498, 5092, 2751, 9728, 9729,
7794, 6056, 3705, 7118, 9710, 9940, 3268, 4808, 3592, 5547,
1658, 1388, 4931, 1268, 9243, 0290, 7929, 9770, 5408, 9175,
6564, 4343, 0407, 1988, 6501, 1404, 1329, 4215, 1979, 1292,
1106, 9405, 0891, 3245, 7389, 5159, 9826, 4614, 2666, 0668,
1736, 7354, 7264, 0456, 6560, 4604, 9461, 9491, 1848, 2246,
7545, 5498, 3670, 1852, 6268, 7793, 1547, 9267, 1629, 9286,
5366, 4656, 1392, 0693, 9414, 0177, 5541, 0333, 8043, 9766,
5661, 9434, 4929, 9109, 4646, 5819, 5101, 5351, 7030, 0335,
0980, 7057, 3105, 8687, 0698, 1855, 2917, 5450, 1345, 2514,
6346, 4941, 5384, 4023, 8485, 5951, 1227, 3095, 5526, 0830,
8709, 8913, 3944, 6912, 4368, 7856, 6905, 8799, 9703, 5907,
6188, 9182, 9354, 0116, 3959, 7666, 1490, 0100, 6417, 3679,
9890, 2604, 7741, 9488, 0399, 6235, 1504, 0897, 6861, 6957,
2236, 2840, 8519, 3966, 5711, 0711, 4814, 3415, 5253, 5681,
0632, 7481, 5856, 7672, 3287, 1179, 6790, 9271, 3663, 9321,
4657, 5356, 4642, 8025, 2155, 2033, 6604, 6913, 6134, 9705,
7208, 0739, 8513, 0991, 6176, 2826, 2993, 0559, 7668, 3335,
4219, 6338, 5651, 4818, 8558, 7992, 5285, 9049, 4056, 4166,
1647, 9263, 4461, 3758, 6499, 3234, 7032, 7969, 8587, 7446,
5155, 3819, 8381, 3013, 4848, 5305, 1552, 2331, 9052, 2762,
3627, 7509, 6698, 7357, 0502, 3045, 6156, 3890, 7575, 5080,
2419, 0145, 0339, 0067, 9498, 9390, 5067, 4507, 9511, 6132,
3009, 1286, 9509, 9095, 1103, 3173, 0748, 9185, 9104, 2371,
1568, 5265, 9857, 6827, 6699, 0857, 3054, 9542, 6914, 3460,
5046, 6707, 3221, 2432, 6878, 4924, 8209, 0914, 5986, 2685,
2327, 0400, 6032, 6490, 6058, 1679, 3355, 3646, 6801, 8468,
8088, 1282, 5071, 1100, 5717, 3988, 1371, 9193, 5687, 5154,
1134, 6486, 1238, 7020, 2443, 1372, 6143, 5426, 3263, 4142,
6069, 6367, 9845, 8296, 1188, 3458, 3880, 9699, 6153, 9658,
6906, 7693, 5081, 6761, 0965, 4399, 5564, 6575, 6494, 3048,
1030, 9823, 7391, 4760, 5948, 7710, 1764, 9224, 7052, 1540,
3367, 5563, 6830, 0198, 6152, 0705, 6576, 8369, 9255, 5073,
8462, 8861, 4882, 9522, 0011, 0751, 8726, 2602, 1865, 9077,
4471, 2462, 4489, 8078, 0152, 1563, 3210, 1594, 9651, 5340,
0616, 9552, 0969, 7159, 6084, 1894, 1541, 6939, 0380, 2895,
0782, 8945, 2109, 0805, 4501, 9914, 8849, 5656, 1407, 4072,
1701, 7679, 5038, 8640, 3857, 2123, 1061, 4161, 4553, 2298,
4524, 4119, 3049, 1011, 9197, 6503, 2832, 5284, 6051, 5553,
0842, 8727, 8039, 1194, 5388, 8243, 5214, 3094, 6539, 8267,
5487, 2939, 9721, 5663, 1888, 4153, 2542, 9798, 2579, 7910,
8841, 2081, 8382, 2093, 4631, 1167, 4616, 8786, 5132, 1126,
9615, 5825, 9601, 3906, 7484, 8886, 3258, 6599, 5525, 3372,
2243, 6128, 6731, 9764, 8102, 4150, 9554, 8926, 5482, 6810,
7976, 8870, 9742, 4622, 9968, 2718, 6054, 5089, 6474, 5794,
9749, 6893, 8660, 3425, 0103, 3392, 7116, 7701, 6509, 4914,
0441, 7266, 0556, 3939, 7112, 4756, 5928, 9875, 5929, 8285,
4292, 2071, 3110, 7789, 5228, 9221, 5422, 3870, 5657, 1515,
3289, 9130, 5400, 0330, 3749, 7936, 1948, 0337, 8132, 2938,
2031, 1605, 7199, 5501, 4163, 1554, 8266, 6984, 5678, 4823,
0458, 7156, 4952, 1136, 9122, 4295, 4851, 7321, 1795, 5457,
3069, 5693, 2838, 4022, 0253, 6758, 9055, 9750, 7412, 0232,
6925, 7188, 8050, 7652, 8163, 8332, 6013, 8743, 1915, 3156,
7690, 4731, 1524, 3551, 1081, 7306, 0304, 1558, 8234, 9500,
9752, 0506, 9828, 8671, 5449, 8516, 4329, 7715, 6972, 6009,
7568, 4871, 4313, 4255, 3720, 4311, 1180, 5379, 7743, 7981,
8076, 7698, 2134, 2377, 5756, 5133, 1509, 3742, 5023, 0266,
7387, 0909, 1567, 0182, 3778, 2200, 7254, 0099, 5419, 1961,
6648, 3543, 8672, 1770, 2723, 1746, 3074, 9804, 9820, 3882,
3044, 8505, 2821, 2937, 4986, 9081, 4118, 5369, 4841, 9588,
7048, 1826, 2879, 8392, 3961, 5983, 9813, 4576, 3788, 7648,
1031, 0982, 2257, 0779, 4651, 1493, 4314, 7133, 1526, 5141,
3838, 7265, 5429, 1941, 3176, 2584, 4107, 2678, 7160, 9583,
5550, 7524, 6001, 4109, 7549, 5853, 2147, 6133, 8871, 9251,
1157, 7464, 8644, 7181, 3315, 6492, 2469, 5893, 6712, 4301,
7716, 7753, 3983, 8079, 9380, 3196, 6294, 7009, 2881, 3994,
3763, 1391, 4134, 6374, 2850, 8232, 3734, 7402, 3255, 3649,
8122, 3804, 0924, 7227, 9700, 0948, 5527, 1778, 3467, 6098,
0272, 2962, 4919, 1092, 4684, 2110, 5052, 5204, 1264, 6341,
1110, 9401, 5925, 1322, 3127, 7353, 9734, 9715, 2014, 7408,
2206, 3292, 6408, 9079, 1603, 4053, 2601, 1009, 5421, 3034,
5259, 5372, 3273, 0252, 3676, 1601, 8015, 7316, 7186, 8521,
8693, 1318, 3492, 8883, 5518, 1197, 7418, 9629, 0511, 4136,
6424, 9191, 6171, 3689, 5721, 1104, 1414, 2756, 8340, 5110,
2790, 0942, 2437, 6155, 0344, 2227, 5708, 8758, 7702, 9917,
0591, 6719, 0282, 0852, 2422, 1191, 5776, 9050, 4269, 6639,
9377, 0875, 8810, 5557, 9884, 5950, 8166, 0306, 5065, 9858,
0143, 3160, 0190, 5349, 8161, 3918, 2531, 6603, 4672, 5710,
1832, 4228, 6383, 6043, 6745, 8637, 6063, 0505, 1070, 5268,
1409, 7726, 9915, 2223, 0736, 4551, 8976, 9800, 3806, 7438,
4895, 5109, 5726, 4690, 1514, 1165, 3580, 0636, 7006, 3269,
6385, 1101, 9808, 9304, 3052, 9896, 1732, 6675, 5180, 4377,
8571, 7345, 9682, 3471, 8802, 8548, 7717, 8580, 6404, 7987,
6832, 7419, 0984, 0946, 6165, 1952, 6381, 2162, 2953, 8704,
3721, 1212, 5398, 5788, 9536, 5390, 7488, 6177, 2429, 1142,
1242, 9640, 9819, 0549, 6116, 5701, 6508, 3654, 8011, 8807,
7440, 0384, 7461, 5196, 3733, 3073, 9097, 8885, 1699, 2652,
6630, 6497, 2704, 3885, 8568, 8762, 6041, 0867, 5840, 6815,
0163, 0986, 6179, 1447, 9313, 4902, 0771, 8298, 9082, 1481,
7973, 3488, 6119, 4806, 5391, 8689, 9486, 6237, 0257, 5341,
3951, 6876, 2167, 3619, 0160, 5940, 7941, 8629, 4935, 2214,
1546, 9594, 5580, 7435, 8297, 2424, 9873, 7019, 6579, 6835,
3636, 8872, 3671, 3132, 9117, 9812, 3694, 5186, 0579, 3593,
6398, 5728, 5978, 7493, 3168, 3957, 1451, 5529, 4890, 4598,
8201, 6659, 2176, 2653, 0033, 7277, 2216, 9882, 1198, 3768,
0096, 4128, 5715, 0031, 6107, 3194, 1924, 5919, 2114, 7470,
0874, 3884, 4821, 8862, 3072, 7269, 4730, 6545, 8017, 8899,
7917, 1337, 1071, 2687, 1192, 8145, 6751, 8964, 4549, 0046,
5734, 9366, 8379, 6500, 0812, 9293, 1937, 5389, 2837, 9538,
4943, 8563, 8312, 8803, 3076, 7587, 2668, 6858, 5083, 6405,
5387, 8826, 6765, 9689, 8842, 3409, 3246, 9051, 4539, 1046,
1975, 3174, 8553, 7304, 5409, 9745, 2351, 9400, 4850, 4569,
6464, 4412, 6272, 9647, 8479, 8641, 8352, 7613, 9074, 2588,
7317, 4426, 9903, 8683, 7994, 9466, 3030, 6795, 8313, 3728,
6038, 0895, 2495, 7162, 6963, 9155, 9831, 7475, 8648, 9085,
9188, 7361, 5044, 2691, 4886, 0940, 9639, 8031, 0757, 6390,
4632, 6786, 0027, 2647, 7137, 2431, 9646, 9453, 6391, 5871,
1693, 5858, 5319, 8294, 1890, 0093, 8001, 2332, 4057, 3969,
8619, 2011, 9668, 1153, 9523, 1641, 9911, 7838, 1049, 7863,
6454, 6718, 5573, 3958, 5647, 7557, 8761, 6247, 5061, 8991,
9381, 7409, 4165, 6517, 3450, 9527, 8275, 5116, 2464, 5161,
7897, 0431, 1458, 4308, 1829, 0347, 8613, 5725, 3313, 8387,
9955, 7369, 1427, 3420, 4321, 1025, 2132, 3032, 9433, 3400,
3064, 6448, 2481, 6874, 2466, 6050, 8229, 3007, 8414, 8270,
6364, 8944, 6737, 3533, 9481, 6531, 8399, 4883, 7132, 6620,
5862, 8903, 6397, 2186, 8112, 9513, 0231, 7918, 2940, 1321,
5659, 2286, 7964, 1143, 8514, 7056, 8933, 2534, 3979, 1942,
8779, 1413, 1462, 1431, 7405, 4385, 1291, 0298, 2740, 3899,
7776, 4995, 3463, 5912, 5965, 4563, 3812, 1671, 9834, 4033,
9962, 4323, 4194, 7167, 9159, 2022, 4897, 3395, 1477, 6443,
2001, 8023, 9985, 1024, 9748, 0530, 2908, 6473, 7704, 9037,
4010, 3664, 0639, 7873, 2662, 1350, 6104, 9268, 9866, 5202,
0947, 9326, 4239, 7919, 2509, 8083, 0767, 6590, 0900, 2262,
9446, 4789, 8508, 0752, 2486, 8160, 7376, 5577, 3605, 6149,
5313, 4235, 2074, 3037, 6646, 0410, 8119, 4908, 1446, 6950,
9041, 5131, 5460, 8801, 2368, 3909, 2561, 0720, 9426, 1428,
0573, 3848, 2482, 9093, 8054, 4400, 8176, 1726, 1272, 6873,
0738, 1313, 0607, 5750, 2196, 5232, 1430, 7511, 0664, 3325,
8455, 1507, 6251, 7301, 4382, 4104, 9135, 9033, 3227, 1608,
7697, 3598, 0684, 4326, 2289, 2310, 2417, 3209, 3323, 4842,
6249, 1722, 3963, 9443, 3902, 2061, 3672, 3683, 7023, 6929,
4972, 7257, 5827, 9581, 4183, 0878, 3249, 5875, 5570, 6278,
1405, 5059, 4975, 7291, 7457, 5939, 4379, 8685, 1997, 1297,
1866, 0235, 0541, 7309, 6441, 2070, 1301, 7909, 8846, 2874,
4008, 7299, 4474, 9423, 5335, 1284, 9558, 4554, 8036, 4825,
4179, 6595, 4064, 7166, 1872, 1132, 3408, 5311, 7655, 1115,
2169, 6896, 3391, 6387, 5215, 5575, 7832, 2661, 7977, 1288,
5420, 6026, 1928, 3277, 2967, 7384, 6470, 2554, 8367, 9425,
2625, 9181, 9240, 3318, 5702, 8214, 6836, 6928, 7618, 1380,
8458, 3935, 8096, 1335, 0475, 4592, 8915, 4769, 2969, 9898,
7826, 3347, 4653, 0795, 2515, 0654, 2483, 7727, 4764, 4735,
9447, 1298, 1692, 9654, 8314, 6759, 4989, 1026, 0932, 2291,
2752, 8929, 3321, 7982, 8151, 1475, 2177, 8057, 6951, 6130,
5068, 2621, 9234, 4899, 4736, 1577, 5489, 0315, 4406, 6475,
4375, 7709, 9273, 1688, 9737, 6276, 8182, 4829, 2184, 1389,
8754, 7041, 8659, 9247, 9974, 8677, 7281, 5057, 6325, 8062,
7394, 3770, 0324, 6242, 2314, 4443, 5090, 5396, 2829, 3665,
4987, 6803, 9294, 9204, 2023, 7771, 9666, 0187, 1215, 3253,
9412, 3155, 7774, 9932, 4790, 6776, 8090, 3985, 6879, 0776,
3786, 9763, 7970, 2101, 1900, 0810, 4388, 8148, 2983, 3308,
5475, 7787, 9681, 6844, 3889, 5977, 1039, 8904, 8274, 3029,
7191, 8973, 8276, 5881, 4707, 9084, 1059, 5966, 2116, 6881,
1494, 8217, 5815, 7542, 0685, 7877, 4571, 5699, 9497, 2090,
3310, 2442, 9314, 9073, 3317, 3501, 6220, 6057, 6409, 1663,
8204, 6482, 7591, 1703, 6764, 3066, 1626, 1747, 3924, 5229,
7991, 6644, 3181, 4518, 1978, 8532, 6314, 2480, 2858, 2885,
0933, 9220, 7451, 5244, 0154, 5754, 8536, 8200, 3014, 8906,
9990, 6729, 9232, 6684, 5108, 5452, 7115, 4220, 1762, 6065,
0490, 6568, 6324, 7533, 5530, 9128, 9020, 0797, 4014, 5671,
3252, 6244, 7939, 1358, 0166, 9563, 8657, 7552, 4316, 5331,
9284, 8831, 0717, 3904, 1525, 0418, 4168, 2372, 4344, 3276,
1654, 1575, 2797, 3063, 3362, 0702, 1627, 3499, 9546, 3524,
1206, 9034, 1349, 6403, 7745, 6996, 4832, 0749, 2487, 4599,
9087, 0648, 5184, 0746, 0710, 4928, 7338, 2439, 3470, 9133,
7275, 5515, 9391, 7523, 8394, 8525, 6190, 3382, 0788, 0060,
9323, 3858, 9136, 7799, 2517, 2615, 3769, 8273, 9807, 1117,
0467, 9479, 6386, 1154, 4324, 9229, 3398, 5809, 8363, 7738,
2545, 6942, 4376, 1874, 0353, 4925, 2370, 3891, 1750, 0360,
7868, 8890, 2127, 5670, 0259, 0715, 4738, 6266, 4305, 5974,
0532, 2383, 0279, 5814, 3907, 8070, 2949, 0498, 0388, 4737,
7846, 1328, 2906, 7128, 8288, 4677, 3001, 6820, 0574, 9690,
8060, 9171, 5779, 9901, 3753, 4231, 1310, 7123, 0443, 3604,
3475, 3876, 3370, 4401, 8420, 2669, 8199, 7681, 1892, 4732,
7503, 2914, 0755, 0864, 0234, 8706, 0448, 1589, 1597, 5293,
6045, 6689, 7632, 3785, 4693, 7125, 5438, 0293, 9923, 6012,
5582, 8375, 4710, 4190, 2108, 0884, 0998, 8154, 9786, 5377,
7359, 5617, 7851, 1854, 7339, 8170, 6522, 5968, 8678, 7311,
7621, 1000, 8703, 4820, 7802, 2819, 6271, 2559, 8896, 9843,
5599, 1095, 7432, 6241, 3275, 0038, 9063, 2675, 3262, 6007,
9177, 9797, 1074, 2449, 6807, 8356, 5777, 1393, 3299, 9333,
1512, 4547, 8663, 5690, 6616, 2735, 8067, 8994, 0697, 9532,
2882, 6722, 6962, 7395, 6791, 7335, 4715, 0314, 6059, 2899,
5007, 9219, 2596, 1912, 0473, 1419, 8564, 7298, 7095, 6549,
9941, 0999, 2095, 5945, 1761, 6541, 9835, 9008, 0261, 3083,
8751, 3288, 3305, 7881, 4992, 0676, 9305, 1500, 6910, 1868,
9645, 0451, 6495, 1348, 3521, 6375, 0210, 1085, 4046, 3348,
9595, 3584, 3699, 2682, 3716, 6028, 4080, 1152, 4969, 7818,
6070, 2359, 3971, 0124, 9679, 2912, 2341, 3374, 4475, 7084,
1555, 4533, 7985, 4436, 2107, 0803, 1237, 4973, 7211, 4455,
9925, 2452, 1324, 2892, 7979, 1772, 2932, 2806, 9056, 2037,
3607, 8534, 1325, 9208, 6085, 5177, 0809, 1715, 8094, 7292,
2195, 3776, 9557, 2356, 7314, 6717, 0251, 1226, 7646, 8196,
8009, 6746, 3416, 7082, 7248, 8795, 9072, 1002, 8822, 9209,
9720, 5719, 2092, 9445, 1678, 7517, 1303, 9470, 4664, 0340,
7823, 2144, 7293, 5076, 8752, 8917, 7816, 4171, 8753, 8498,
4210, 4719, 9984, 5741, 7772, 9276, 9852, 8565, 6219, 7691,
9691, 8958, 0205, 9883, 8604, 6017, 3497, 9231, 9891, 0193,
9107, 1702, 6240, 0044, 3053, 9597, 2276, 4980, 8748, 8283,
2215, 0127, 6512, 4482, 2640, 0322, 4282, 2861, 4878, 2488,
7337, 4370, 7008, 1759, 8063, 1556, 4991, 4208, 7397, 8614,
5190, 4500, 1217, 2660, 9266, 1821, 3344, 2789, 2933, 0756,
4968, 9487, 4492, 2975, 1898, 2649, 3822, 2284, 8690, 4216,
5310, 2172, 8410, 7215, 3855, 6493, 6555, 8061, 9669, 9371,
9894, 1094, 1368, 2792, 8278, 5306, 5270, 8344, 7769, 0433,
1285, 2803, 2425, 7629, 5524, 4535, 7586, 4839, 6255, 9114,
7757, 6650, 8860, 2910, 6027, 3129, 6465, 2519, 8026, 2106,
2822, 0104, 1752, 9418, 9287, 0646, 1164, 0815, 6442, 6695,
2507, 1914, 2413, 3028, 1289, 4562, 0968, 8627, 4749, 8809,
1971, 6018, 7853, 3863, 8932, 6669, 8509, 9067, 7474, 2362,
1076, 4786, 1553, 1543, 2518, 0242, 5954, 1060, 2651, 1644,
9145, 7091, 7879, 2273, 8711, 5997, 6797, 7392, 3552, 5435,
9568, 7066, 2297, 2719, 4625, 3462, 4250, 7415, 5298, 1296,
6016, 6135, 7259, 9686, 2099, 4623, 3859, 2178, 2038, 6253,
8187, 7096, 2411, 3722, 3691, 0542, 2381, 0753, 4116, 4768,
9444, 1114, 9650, 5024, 5609, 6592, 2877, 3240, 3873, 7556,
0281, 5206, 5664, 8193, 2165, 6207, 4907, 4371, 9757, 4796,
7322, 5350, 1773, 4568, 8549, 4354, 0911, 7642, 0408, 2063,
6992, 0238, 4874, 0250, 8258, 1170, 2986, 0301, 8125, 7580,
6952, 3107, 6889, 8192, 8574, 6670, 3856, 4304, 7641, 8447,
8406, 3298, 2296, 3756, 0013, 7688, 7733, 9257, 4691, 8044,
5744, 9045, 3962, 9411, 3544, 2758, 7241, 4620, 9327, 9013,
8024, 9517, 0343, 4050, 2004, 9080, 1958, 9334, 7026, 4506,
7171, 2931, 8251, 4978, 8230, 3139, 1362, 8584, 3455, 4491,
9515, 5371, 5008, 3061, 6226, 7502, 5962, 8959, 2191, 6459,
9929, 0652, 6162, 6183, 5877, 8609, 8939, 8245, 4430, 8576,
8705, 0356, 7605, 1406, 4830, 1717, 4201, 1125, 3093, 2067,
3487, 1387, 9419, 2175, 5883, 3600, 0686, 7441, 2576, 4645,
9571, 7263, 1999, 7042, 6420, 6591, 9924, 7540, 6437, 8551,
2122, 7382, 7126, 5050, 0937, 1034, 3746, 0229, 1331, 9350,
5555, 7963, 8632, 6732, 3103, 0907, 5676, 1176, 1850, 0460,
0354, 6784, 2857, 5613, 5094, 7212, 9528, 0520, 0376, 0882,
2902, 9506, 2497, 3340, 1708, 8149, 6625, 4405, 9777, 1052,
6954, 0943, 8330, 7620, 8027, 0464, 2724, 4997, 7582, 8607,
0545, 3860, 7122, 2802, 6217, 1697, 0918, 8982, 0976, 8355,
5333, 0814, 3088, 5170, 1378, 9864, 6850, 1293, 5454, 7949,
4372, 2859, 0325, 2335, 7145, 6077, 7144, 8811, 0421, 1955,
7465, 1145, 0950, 9452, 7768, 4464, 5731, 5411, 8969, 0828,
4938, 1730, 9961, 3184, 9281, 6350, 1996, 5490, 7640, 7584,
6892, 8433, 1496, 8121, 7039, 5636, 9643, 5360, 6809, 0759,
8475, 0486, 1385, 8227, 3759, 0129, 7961, 0167, 3314, 5327,
6047, 3495, 3369, 9459, 1664, 5890, 3655, 6618, 6735, 3230,
2847, 1694, 8864, 4618, 2005, 0468, 8064, 7729, 5799, 0153,
7260, 4797, 9014, 6685, 6355, 9031, 4429, 9784, 7806, 4785,
5921, 9780, 6860, 8280, 6122, 5222, 8880, 7492, 6230, 1366,
2436, 7342, 6772, 3579, 4069, 2305, 3429, 9539, 1590, 7845,
8501, 8093, 5851, 4415, 7510, 7230, 3938, 2580, 9387, 5103,
6816, 7911, 7662, 7866, 0276, 3824, 4020, 1614, 9861, 4363,
0796, 3446, 5176, 8823, 4336, 7370, 7431, 2791, 2814, 7425,
8446, 3709, 9042, 6180, 8045, 3535, 8908, 4234, 7790, 8961,
5126, 4774, 7217, 0424, 2607, 0957, 8837, 5428, 7065, 1818,
4676, 2985, 7622, 5562, 1087, 1181, 8156, 4781, 8246, 4801,
8829, 6214, 9141, 5594, 3830, 5423, 3799, 1479, 6543, 6150,
0981, 1401, 1084, 9855, 6626, 0184, 2293, 5517, 1356, 7256,
1927, 1495, 3199, 1411, 8673, 4855, 5821, 3257, 9190, 6323,
7812, 4682, 8889, 4629, 3265, 0042, 5224, 3861, 1041, 3647,
1960, 3784, 3388, 1896, 4544, 1511, 3280, 7245, 8371, 1691,
5511, 7852, 6629, 5145, 7913, 5675, 2658, 0669, 3621, 1398,
1994, 2344, 9467, 2313, 2414, 8638, 9839, 0623, 0928, 1105,
9956, 1240, 2731, 5086, 2066, 0482, 2639, 2301, 2040, 0139,
6585, 3801, 8497, 0883, 5727, 1790, 9611, 1987, 3782, 2365,
7820, 8391, 4583, 7479, 7675, 9441, 7351, 8338, 5321, 2945,
9203, 0544, 7236, 8636, 2966, 5451, 8120, 7157, 9624, 6587,
0624, 2761, 1845, 1846, 5445, 7955, 5565, 3062, 1877, 2629,
0239, 6855, 1655, 0955, 6362, 8760, 9146, 3915, 4655, 0189,
1883, 5822, 3402, 6716, 9083, 1809, 9627, 7453, 6354, 4807,
9261, 1438, 9485, 8611, 8168, 0088, 8473, 6457, 9722, 7183,
4167, 1235, 7624, 3223, 2870, 9702, 3375, 0382, 7274, 5561,
0518, 0017, 3206, 0629, 8540, 0437, 5281, 5920, 5394, 0117,
6574, 2732, 8696, 9760, 2787, 0385, 2996, 8228, 0278, 1456,
4472, 8830, 9436, 8631, 0392, 7888, 5692, 7341, 2346, 8778,
7927, 1379, 6570, 5503, 1596, 5624, 5382, 7711, 9756, 3697,
5911, 2808, 6327, 0297, 1258, 9003, 3397, 9667, 8585, 6463,
9535, 9635, 9743, 0611, 5499, 1045, 2549, 8147, 8005, 8315,
2770, 8306, 0267, 6225, 0741, 1162, 2665, 6988, 5842, 0398,
2632, 1680, 0434, 8400, 8086, 3359, 1054, 6606, 0800, 8159,
2689, 9242, 9454, 2170, 1079, 6681, 6916, 6023, 1408, 3142,
7861, 1204, 7295, 6999, 1976, 7297, 5465, 2303, 3942, 2598,
4159, 0249, 4843, 5947, 2094, 2264, 7924, 9887, 0707, 0609,
4195, 3101, 5066, 2827, 2521, 6584, 4706, 5189, 3589, 4740,
1287, 7526, 1807, 9325, 6802, 8901, 2921, 3634, 0583, 7349,
1922, 8777, 9551, 7466, 2091, 7560, 7015, 9574, 2135, 5729,
4152, 9829, 1257, 2336, 5645, 2537, 6365, 1804, 5174, 3594,
5330, 6706, 0144, 9773, 9275, 5060, 5219, 6969, 1656, 4712,
9564, 3316, 9378, 4265, 0063, 1267, 5162, 2715, 9779, 8977,
1355, 9958, 1696, 5637, 2012, 4610, 7611, 1767, 8503, 4060,
5888, 3017, 9572, 8277, 5844, 9793, 9697, 8189, 3817, 6804,
4561, 5042, 5674, 5084, 5129, 5554, 4416, 6624, 4403, 9364,
0674, 0634, 6736, 4957, 5207, 4759, 7957, 1612, 1471, 5720,
8788, 7719, 3972, 1610, 8780, 1640, 6082, 6112, 1097, 3993,
1559, 1320, 0964, 0617, 1972, 4939, 0128, 1675, 0367, 7487,
6460, 5000, 2866, 4863, 2867, 8042, 6800, 4565, 0627, 8845,
7592, 2532, 9493, 6267, 3279, 5960, 2189, 5634, 6476, 9707,
9475, 7579, 8978, 1591, 2780, 6938, 5474, 0397, 2229, 5128,
6720, 9848, 4348, 2034, 4328, 5730, 2056, 2871, 3750, 0525,
3331, 4447, 0832, 5264, 9346, 1478, 6991, 9437, 6721, 3326,
2979, 3643, 4294, 7968, 2238, 1491, 5857, 9345, 2889, 4857,
4603, 4515, 6366, 2304, 5590, 8123, 9678, 1535, 3950, 6191,
1830, 1498, 9161, 4091, 7497, 2168, 8169, 3036, 7603, 7326,
9790, 9315, 3453, 5354, 6092, 1946, 3608, 3967, 7491, 3345,
7168, 1648, 0691, 1953, 4496, 1733, 1015, 2872, 5030, 8139,
1505, 6025, 4467, 8856, 4826, 6212, 5935, 3708, 8098, 6127,
3949, 8755, 9307, 2309, 0615, 8325, 2325, 5723, 7811, 3356,
4306, 7617, 9972, 4198, 6513, 6086, 3172, 2805, 8960, 7565,
7064, 5846, 1234, 3428, 4036, 1177, 0183, 5722, 2024, 1382,
1365, 0522, 0346, 9709, 3381, 2597, 1834, 5134, 0049, 3018,
9336, 1909, 2367, 0569, 8897, 8107, 9899, 1720, 6231, 6202,
8642, 4120, 7240, 2086, 0695, 7083, 9379, 0855, 0188, 8633,
7190, 1381, 2890, 7740, 8774, 2636, 1487, 6024, 7657, 4428,
6022, 9801, 9944, 7750, 0383, 9383, 6899, 6933, 7872, 7531,
3385, 7347, 5362, 9980, 2075, 6621, 3440, 1935, 2710, 6779,
5492, 6691, 0854, 7423, 6976, 7677, 3071, 5138, 3610, 5781,
2757, 8691, 2082, 1219, 0289, 5894, 3653, 8165, 6321, 3703,
1445, 5151, 1707, 0765, 5036, 9030, 3887, 3225, 1920, 1642,
6794, 1777, 2057, 5477, 3202, 5047, 4085, 5205, 5418, 0061,
4357, 8354, 6430, 8651, 1051, 1806, 9167, 8791, 2565, 3235,
8328, 7101, 4413, 0313, 7730, 4197, 1270, 5778, 2812, 0975,
6003, 3022, 3585, 0284, 0863, 1836, 3688, 6824, 9183, 7619,
0839, 2738, 3016, 5748, 5621, 0487, 8386, 1776, 6664, 6565,
1443, 6401, 3108, 3571, 9688, 4232, 5074, 4205, 1256, 5642,
4584, 2573, 1926, 5596, 9724, 4555, 5112, 2447, 4724, 2557,
2839, 0022, 0141, 3130, 1891, 4063, 6573, 2237, 6169, 5775,
4522, 4224, 6838, 4822, 4389, 0247, 8616, 3982, 7262, 8105,
3992, 7571, 1682, 8364, 1057, 1595, 0663, 3205, 5994, 5737,
5578, 0426, 5357, 4647, 6252, 5142, 8135, 9999, 9838, 8626,
8832, 0219, 3829, 1043, 4527, 8428, 0689, 8617, 2271, 4721,
0440, 2059, 1357, 0822, 9565, 6347, 2493, 8049, 0963, 4283,
2333, 4322, 8339, 8397, 4872, 3893, 0447, 1265, 5315, 1901,
9339, 8630, 5148, 8589, 7602, 2672, 4411, 7860, 4585, 7005,
4315, 8655, 2950, 0562, 3128, 9787, 2379, 3651, 0672, 4266,
7890, 3946, 6841, 1351, 2739, 9805, 2124, 8928, 3180, 9613,
6842, 0254, 7895, 0651, 1531, 5972, 0935, 2348, 8608, 0255,
4845, 1743, 4531, 9670, 6558, 9567, 2353, 9623, 2734, 5850,
6529, 1386, 4209, 4503, 3438, 6079, 0454, 3106, 0762, 5612,
5558, 4076, 4692, 2285, 5592, 5949, 9971, 2300, 1530, 5992,
5292, 9943, 3422, 7839, 8719, 0225, 0977, 0823, 9473, 3568,
3853, 0268, 2163, 4440, 8858, 2235, 7884, 1851, 0307, 5301,
5990, 7468, 5238, 6400, 5605, 1686, 2287, 8669, 6006, 9810,
7754, 0778, 2392, 3170, 1544, 5745, 2659, 6415, 1432, 4813,
8281, 7559, 8652, 4869, 2539, 9947, 8941, 3793, 8255, 6961,
2880, 4140, 3588, 7796, 3667, 4261, 8739, 6515, 2161, 3464,
1731, 1146, 5241, 5254, 7035, 0311, 9951, 5817, 7694, 8279,
8527, 3562, 5167, 3154, 0787, 6048, 2345, 9090, 8579, 5056,
3349, 4573, 6785, 8718, 0352, 9584, 9078, 4913, 7749, 6993,
3104, 5242, 2152, 6542, 6142, 8309, 5127, 3328, 5339, 9372,
1352, 2224, 4332, 2117, 3553, 4833, 5385, 8451, 8019, 3547,
4330, 9983, 2400, 6434, 5019, 7050, 4129, 4678, 1492, 3780,
0978, 9636, 4407, 3531, 6743, 3851, 2863, 5153, 3222, 9950,
3954, 3449, 4532, 2478, 9105, 8912, 1122, 7946, 1346, 8301,
5456, 3291, 8018, 2409, 0587, 6008, 5367, 7013, 6908, 2529,
4912, 8460, 9456, 7279, 5255, 4558, 5793, 6315, 4268, 0120,
4865, 1050, 4849, 7202, 3752, 3439, 2943, 4701, 8694, 2562,
2347, 3133, 5981, 2901, 6269, 4750, 4870, 3295, 2193, 0836,
8993, 0328, 4253, 2226, 9099, 0488, 2000, 0920, 6534, 7372,
2679, 0090, 9131, 0336, 6296, 1040, 0078, 4184, 0768, 3377,
7012, 1561, 5743, 7155, 1295, 0637, 8815, 2998, 1082, 9360,
7154, 5643, 3803, 1907, 1072, 2282, 4946, 0952, 9685, 1183,
3125, 3678, 6502, 0159, 6377, 3774, 1813, 4378, 9499, 9934,
2283, 5998, 4502, 5993, 0625, 5805, 8317, 2263, 4667, 2477,
4861, 2140, 2749, 4094, 1032, 2342, 7270, 7358, 1037, 8603,
5959, 7097, 1007, 7541, 7003, 1205, 0349, 3040, 6234, 5695,
4213, 8556, 2958, 0041, 4356, 8329, 9258, 8092, 9186, 8080,
7576, 3151, 4688, 4650, 3686, 0394, 1831, 9385, 0831, 1016,
4367, 2978, 7680, 6756, 1230, 6538, 5830, 3300, 9228, 0938,
6035, 8205, 3441, 8238, 8647, 0212, 7285, 1634, 2496, 0892,
8404, 7090, 6221, 1794, 0880, 7148, 0745, 3417, 6498, 0008,
7044, 2664, 8771, 0747, 2288, 7059, 8676, 8058, 4767, 4643,
1684, 9638, 1734, 3760, 3405, 4798, 4621, 6181, 5447, 7553,
3995, 5882, 9471, 7828, 5823, 7899, 6358, 9926, 8437, 6530,
3675, 4868, 3489, 3114, 0547, 1304, 3981, 9544, 4462, 6091,
3187, 2946, 6356, 2974, 1923, 5588, 7251, 3086, 7489, 5566,
9253, 5249, 2047, 4981, 5891, 2454, 1214, 7444, 9783, 7937,
4452, 9482, 7495, 3762, 7746, 5768, 0048, 3239, 4302, 3685,
1659, 0650, 4086, 0824, 9198, 5669, 5571, 1607, 6505, 9296,
7564, 9775, 9977, 7385, 1523, 2008, 7216, 1020, 9771, 0312,
8533, 9342, 3802, 8048, 4289, 1632, 4307, 0466, 0696, 8197,
7242, 2916, 0401, 4247, 2035, 4644, 5942, 6161, 6851, 2716,
7930, 9062, 2174, 4133, 9142, 6917, 9396, 0081, 3869, 1719,
6821, 6331, 8124, 4419, 9849, 9241, 7058, 7508, 3191, 8066,
9733, 5672, 1841, 0326, 7986, 5587, 1801, 9349, 9603, 3814,
1439, 4017, 0334, 8085, 7381, 4536, 1600, 5803, 5732, 2512,
1022, 8220, 8531, 3003, 2473, 1377, 7567, 3741, 8884, 0786,
5595, 7686, 1963, 5463, 1637, 9738, 8695, 4679, 2382, 2458,
8419, 3764, 5053, 8798, 9553, 8443, 9057, 3169, 1216, 9502,
5818, 3358, 4182, 7876, 5579, 9184, 8474, 0958, 4580, 0598,
3272, 6554, 9825, 1768, 3267, 3212, 0890, 4387, 7303, 6895,
3795, 6589, 7723, 7885, 2338, 6995, 5104, 1739, 9026, 3748,
6455, 3525, 9510, 6380, 6870, 2591, 0422, 8530, 0959, 9089,
2068, 8838, 1229, 9746, 9178, 8424, 8310, 3404, 6771, 5466,
5507, 2608, 4034, 6907, 0009, 8968, 7634, 0016, 5469, 4288,
9308, 9299, 0172, 0794, 6643, 5364, 6011, 0667, 2198, 6370,
4476, 7844, 1086, 1969, 6376, 5855, 1586, 6480, 3026, 2275,
4450, 6125, 0025, 3027, 0529, 1983, 4953, 4333, 7114, 7108,
4339, 1200, 0764, 5927, 9317, 6696, 6754, 4102, 7399, 5401,
5569, 8670, 7176, 6083, 5380, 5039, 1253, 1957, 8855, 6943,
9501, 3898, 8021, 7209, 4911, 8674, 0142, 2589, 3281, 2053,
3208, 1323, 4188, 5865, 2104, 1782, 8552, 1943, 7189, 3917,
7636, 7092, 4337, 2205, 4127, 5598, 9653, 2221, 7836, 6342,
4926, 3519, 3867, 7390, 1017, 5058, 3908, 4318, 6194, 9386,
3914, 2525, 3111, 9963, 2656, 9893, 7040, 0158, 7287, 0390,
8207, 6261, 4782, 5623, 7332, 9358, 9205, 2245, 5045, 2944,
4915, 6427, 8528, 8736, 0908, 6340, 4812, 5314, 7554, 4362,
4615, 6010, 6432, 3197, 2020, 1108, 2683, 4130, 5342, 1486,
0922, 7744, 0300, 8625, 0147, 2326, 0769, 0391, 3911, 2096,
9462, 9490, 5667, 3622, 9060, 9706, 8418, 8456, 2935, 0992,
3041, 7001, 8118, 9489, 8681, 3868, 0527, 4694, 4827, 0269,
2578, 7915, 6649, 1064, 7426, 1573, 6139, 0721, 9862, 2133,
0317, 8927, 7612, 8502, 8720, 4979, 1384, 4485, 5872, 9576,
3986, 4879, 4439, 8835, 7038, 2952, 8600, 6990, 9531, 3243,
1849, 8441, 7513, 5294, 6353, 5240, 3278, 0345, 9632, 9237,
3936, 6843, 3897, 0030, 2445, 8940, 6333, 5263, 3569, 1802,
5211, 0474, 6336, 8482, 0687, 9936, 2396, 0007, 6888, 7163,
7859, 2976, 1317, 6445, 5593, 7519, 9450, 8272, 8942, 8425,
1949, 9388, 5963, 4016, 2820, 2617, 0835, 6118, 8707, 3477,
5673, 5443, 0833, 6124, 3757, 1758, 8434, 1333, 7222, 7223,
6548, 1621, 0059, 2956, 0645, 9854, 4717, 7990, 4658, 4287,
7131, 2360, 3840, 4880, 1353, 4043, 7147, 0642, 9920, 9138,
8213, 5520, 8763, 9495, 1570, 2328, 6762, 6160, 1791, 0123,
3213, 6187, 8566, 3846, 0348, 9032, 3570, 9649, 3200, 1221,
5363, 3577, 5027, 7187, 7161, 7878, 1613, 3640, 6884, 3933,
5348, 2977, 9548, 6260, 7434, 6273, 7996, 1474, 3583, 8768,
5902, 7127, 7647, 0072, 4004, 3410, 4251, 3707, 5545, 4144,
7253, 6173, 7953, 3862, 4668, 0872, 7080, 3081, 9608, 5353,
5759, 1676, 4276, 4548, 2203, 1224, 4673, 4089, 6920, 6067,
2593, 2713, 6632, 9210, 6598, 6612, 7371, 1982, 8769, 5041,
2112, 3934, 4977, 5802, 0461, 6886, 3256, 1029, 2727, 0438,
2522, 9664, 7606, 2936, 7029, 6640, 7193, 8667, 0260, 7514,
7747, 0829, 0701, 6594, 4204, 9424, 6126, 3507, 6467, 2581,
3474, 4966, 5476, 6072, 1879, 5201, 0244, 0248, 7439, 7908,
2686, 2418, 7965, 2045, 3387, 5221, 5528, 7328, 4141, 4340,
2049, 6373, 1397, 9469, 0670, 1004, 3035, 7780, 3615, 2416,
0039, 2818, 2947, 4755, 8448, 1788, 5896, 9753, 5955, 6787,
2779, 1241, 4777, 0985, 0543, 1309, 1666, 1550, 6209, 9170,
4854, 7290, 1784, 2317, 0230, 9166, 2239, 4675, 1529, 0690,
4894, 8955, 7569, 1399, 8784, 8162, 4038, 4867, 1344, 9782,
7664, 3363, 8103, 5025, 8074, 0743, 2556, 6597, 6922, 9048,
4636, 5834, 1940, 5280, 6310, 1881, 6148, 3307, 1616, 5665,
4726, 3411, 4246, 4273, 6923, 1633, 1769, 7831, 2120, 5654,
5095, 2674, 6596, 1390, 2989, 4937, 2692, 1018, 3626, 2845,
5096, 3190, 5064, 0092, 5257, 9732, 3541, 0236, 4663, 0904,
9976, 2888, 4950, 0783, 2516, 8557, 7626, 1592, 9661, 2688,
7033, 0080, 3432, 7822, 6847, 5183, 2349, 9005, 8378, 8869,
2064, 7380, 4174, 7722, 9279, 7094, 2233, 6216, 7323, 2961,
8520, 5032, 1464, 3766, 3513, 9674, 5901, 3736, 0373, 6433,
1133, 2395, 4068, 8038, 7228, 1069, 5037, 8951, 4709, 2809,
4588, 0885, 4934, 8731, 6660, 2869, 6774, 4624, 2548, 9353,
0285, 1551, 3436, 4885, 3456, 3418, 9439, 0209, 0519, 0222,
6605, 5072, 2319, 7997, 1449, 2891, 3805, 1497, 2202, 8250,
3920, 3713, 9365, 3706, 5181, 4954, 1426, 8171, 5040, 5937,
5770, 5015, 4660, 0827, 8000, 1706, 6131, 5531, 8236, 4630,
1311, 5905, 0465, 1585, 3836, 8351, 5406, 8730, 5903, 7638,
4024, 2711, 7600, 3970, 4654, 7427, 0455, 9840, 8253, 1028,
3163, 7837, 5493, 1102, 2505, 5913, 8305, 4437, 5150, 1650,
6519, 4158, 7143, 3306, 9384, 9415, 1457, 7942, 2997, 8359,
0983, 5597, 4319, 9118, 7795, 4073, 7107, 9024, 1991, 2717,
8894, 8452, 8342, 4137, 6867, 3518, 5192, 3431, 2158, 4335,
5010, 4087, 9526, 6780, 7870, 2077, 2594, 8490, 1340, 9044,
2279, 3692, 0951, 3662, 9939, 2526, 9312, 6140, 9863, 6657,
8353, 7972, 4345, 8650, 4570, 7456, 9730, 4138, 9285, 1130,
7896, 9217, 5506, 6521, 0548, 0595, 2741, 8114, 3560, 5483,
2676, 7995, 8348, 8442, 2294, 3666, 8412, 3701, 7214, 5332,
5957, 2105, 2995, 1367, 1442, 4451, 3264, 2873, 1156, 2427,
3126, 7243, 8303, 2502, 7179, 1549, 0666, 5318, 5088, 8875,
9741, 3511, 1704, 9201, 1056, 0754, 0263, 5653, 2971, 1135,
4352, 0917, 3060, 8733, 7847, 9547, 1522, 5679, 5572, 9524,
2260, 6031, 4803, 2128, 0277, 4517, 3260, 8515, 2266, 4840,
8712, 3738, 0402, 3635, 7105, 3002, 2555, 6677, 9878, 4365,
3964, 6099, 7375, 7650, 6113, 2575, 9673, 0483, 1749, 8084,
6968, 4303, 3847, 8284, 4077, 0572, 1681, 8567, 7945, 9043,
1974, 6638, 3841, 6864, 1615, 8500, 8254, 3921, 2036, 0961,
7085, 8257, 1261, 3270, 6295, 3226, 6071, 3865, 2728, 9301,
3419, 2701, 1781, 3020, 4470, 8304, 3283, 5861, 1251, 8914,
9607, 2467, 0295, 9070, 3744, 1812, 7625, 7355, 0056, 7200,
7136, 5368, 0988, 5523, 6259, 2769, 2321, 1661, 8029, 7271,
6447, 6229, 7472, 1886, 0208, 2905, 8938, 5135, 3171, 9337,
6489, 2016, 3850, 4596, 5543, 1373, 6526, 8843, 8792, 7021,
1984, 2111, 7401, 3614, 7221, 6540, 1128, 6121, 8905, 7635,
6186, 2434, 1698, 8773, 4976, 4686, 9153, 1244, 2256, 0291,
1195, 2320, 9264, 3740, 0032, 4042, 5344, 3043, 3332, 0491,
0066, 2864, 9458, 2612, 6200, 4993, 1657, 9195, 7310, 0614,
7424, 5016, 4196, 8682, 4590, 8300, 7570, 4258, 1537, 8487,
5753, 3717, 1158, 8390, 5931, 0321, 3433, 8082, 7628, 1815,
8649, 7363, 3371, 7027, 7478, 8174, 8128, 9215, 9844, 0071,
4770, 1063, 8708, 8962, 3189, 6097, 2681, 0034, 9680, 5165,
5833, 7874, 5989, 2222, 6213, 2671, 7841, 9776, 6817, 2404,
0292, 7296, 5248, 9504, 7283, 8873, 9324, 5491, 8653, 9407,
5703, 5943, 0363, 0565, 5054, 9871, 7483, 4936, 1190, 4671,
9846, 8429, 3641, 6741, 0110, 9992, 2113, 6778, 8506, 9959,
4272, 6805, 7938, 2778, 9151, 3892, 5698, 2494, 3603, 3800,
8034, 5352, 5868, 1185, 4697, 0723, 5917, 4495, 7883, 6633,
6525, 7943, 4947, 7346, 3595, 2955, 2410, 5226, 8544, 7761,
9140, 9147, 7867, 6507, 2376, 8457, 5816, 7327, 8586, 8930,
0635, 8347, 8787, 3714, 0941, 9600, 4607, 5230, 5767, 7072,
9256, 8494, 3644, 6753, 3761, 3831, 3182, 8164, 2268, 0671,
9660, 4633, 1073, 4545, 1422, 4456, 3599, 8071, 0997, 2694,
9355, 7206, 4007, 6218, 9394, 4286, 9609, 3555, 4762, 6103,
3910, 3390, 4510, 1307, 9799, 0944, 6711, 3978, 1674, 1067,
6826, 6704, 0256, 9981, 9172, 1243, 3991, 7827, 4751, 8324,
3693, 2334, 3378, 1228, 3772, 7854, 6818, 2019, 0536, 2646,
7543, 6352, 2506, 8954, 5839, 8876, 0967, 8887, 5874, 9693,
4687, 1687, 3809, 6061, 1141, 3674, 2984, 4075, 8357, 1712,
8411, 8692, 6193, 3211, 5600, 0865, 2159, 2774, 9892, 2566,
5560, 4753, 1334, 2587, 8203, 0213, 0894, 3948, 0887, 2013,
0114, 4243, 1175, 1001, 0862, 7203, 9827, 3894, 2991, 4021,
0179, 0374, 4559, 1182, 9270, 1631, 0727, 0186, 1425, 4432,
7599, 7267, 4028, 5709, 7334, 7024, 1189, 7404, 5075, 7928,
1010, 5602, 5193, 6667, 0294, 4964, 0005, 8463, 9289, 6973,
5278, 6456, 4748, 6544, 2957, 0019, 6533, 9064, 8984, 2853,
0763, 7325, 9223, 8318, 9727, 6700, 2747, 2253, 0658, 4728,
4277, 7797, 9853, 1245, 4960, 6096, 4860, 5952, 1513, 9421,
5374, 6302, 6918, 5864, 4299, 8157, 1903, 0987, 1548, 5125,
1825, 9338, 2160, 7452, 8461, 8299, 1977, 2498, 7534, 0411,
9973, 8658, 5231, 4355, 2750, 1090, 2143, 1785, 1510, 8435,
3376, 1093, 7469, 6697, 4006, 0258, 8181, 6233, 3681, 3879,
7422, 7901, 0469, 7819, 6919, 1775, 6683, 8539, 3844, 6658,
3500, 0993, 8499, 4172, 6166, 5938, 1269, 2089, 1569, 4226,
2048, 9725, 0528, 0496, 9641, 3877, 9919, 8396, 6462, 9998,
8797, 2680, 6360, 9874, 5160, 1645, 8971, 0412, 2964, 3085,
9298, 6883, 9404, 0493, 2695, 4178, 5178, 3301, 8326, 4639,
4974, 5576, 3968, 8282, 9359, 6674, 6088, 5051, 5446, 3217,
9046, 1660, 2886, 2385, 7537, 4096, 3192, 0840, 0861, 2918,
2479, 8923, 3596, 8605, 4745, 7333, 4117, 6066, 2188, 0122,
8623, 8827, 0403, 0675, 2080, 6583, 2624, 7100, 0962, 4433,
7959, 7935, 0929, 0309, 1252, 5200, 0472, 9196, 3236, 4041,
7078, 4393, 3550, 9468, 1211, 8002, 3421, 7609, 9859, 7752,
0777, 8850, 1273, 7732, 8041, 8012, 4227, 3019, 1484, 8110,
6510, 2433, 1810, 0834, 1847, 8138, 9713, 5941, 4031, 5591,
6601, 7782, 4384, 9363, 0240, 3925, 9885, 8350, 3327, 5291,
0425, 3399, 6184, 0089, 2920, 9120, 7249, 7869, 5622, 5381,
1936, 2183, 2430, 3581, 2115, 1930, 1933, 6742, 2645, 6141,
1374, 5784, 7529, 8646, 1582, 8131, 0220, 4711, 0288, 1213,
6856, 8615, 7887, 2960, 9496, 7261, 6468, 5256, 8710, 4320,
5626, 2118, 0500, 1902, 3754, 8150, 3011, 8223, 2097, 3940,
1171, 1789, 6414, 7770, 9300, 4391, 3229, 7195, 5909, 7071,
6491, 3586, 6825, 5880, 5187, 9585, 2765, 0873, 9113, 4317,
7205, 5958, 9290, 7855, 9292, 4793, 1218, 2796, 8594, 7411,
2524, 2503, 1774, 2854, 7708, 1538, 1417, 8158, 4787, 4799,
6613, 0432, 4468, 4156, 9492, 5392, 7022, 0342, 6588, 3835,
8335, 2157, 5898, 0877, 0960, 4689, 0006, 9374, 2904, 1967,
3731, 5304, 1276, 4557, 8040, 7109, 4900, 2941, 0445, 4032,
2965, 4944, 1611, 4497, 2182, 4364, 2386, 4386, 5961, 6005,
4381, 7734, 7219, 0694, 6894, 9252, 5296, 9816, 1359, 4699,
0820, 6425, 3084, 9508, 5758, 4909, 6686, 9665, 4244, 4956,
0362, 0119, 5260, 3342, 8654, 7777, 6081, 0772, 4725, 9913,
6000, 1574, 7728, 5149, 1123, 0111, 9124, 0386, 8319, 3976,
3813, 9967, 5212, 6201, 3747, 3509, 2745, 6208, 0075, 5274,
0414, 4681, 0801, 1482, 8591, 8541, 5512, 2737, 9112, 9794,
3309, 5403, 8389, 7539, 2876, 1131, 9302, 6635, 1718, 8759,
2951, 1342, 9634, 0113, 0442, 4608, 7737, 1725, 8602, 9092,
9476, 3591, 4065, 8593, 2544, 8816, 7720, 7455, 5014, 8656,
3423, 3099, 9111, 8097, 8821, 8957, 8126, 1811, 0243, 6111,
6021, 2567, 9577, 0837, 5878, 6329, 5182, 3138, 1805, 7891,
8789, 6264, 1138, 9712, 6435, 5448, 7388, 3403, 7748, 8790,
5773, 6571, 3932, 8343, 8972, 3900, 5976, 7685, 3582, 5216,
7546, 6280, 2388, 5300, 4449, 7120, 4358, 6546, 8235, 7778,
0954, 4477, 9322, 9029, 1370, 7018, 1823, 9714, 7960, 8167,
5070, 1745, 3826, 8588, 4955, 9610, 1599, 1420, 7365, 3459,
8819, 1088, 6243, 0994, 3454, 9187, 0054, 8115, 4722, 1480,
8022, 8854, 6833, 0818, 7700, 9068, 2959, 9075, 9134, 9809,
6407, 0996, 2006, 8979, 1027, 1962, 6931, 4815, 4103, 8292,
1019, 5287, 4425, 6254, 4284, 0953, 5106, 3165, 5740, 5953,
7525, 7967, 4758, 8366, 6368, 5225, 3613, 8087, 9579, 8467,
5235, 1137, 7644, 0051, 3469, 3832, 6174, 9432, 1429, 7073,
2611, 8081, 1779, 4422, 2570, 6157, 2628, 5455, 1316, 2375,
1364, 8833, 2387, 3311, 1520, 0416, 5288, 2393, 3051, 7067,
0452, 6438, 3652, 8450, 7764, 6137, 8824, 6561, 9986, 2408,
8242, 6982, 3089, 6617, 7150, 9369, 6773, 5303, 9628, 7663,
0073, 5098, 8191, 0570, 0844, 5338, 5166, 2807, 1005, 3136,
3304, 1662, 4893, 8483, 2139, 4889, 5481, 5119, 8878, 7178,
0216, 5980, 3050, 2677, 9785, 4025, 2800, 7184, 0662, 0381,
5458, 9759, 8033, 9061, 7892, 2308, 0108, 4729, 2218, 3737,
2650, 7562, 7308, 7791, 5345, 5792, 4773, 3134, 9596, 4714,
4186, 5546, 8518, 4222, 9605, 4361, 1247, 6055, 4189, 7962,
1343, 2513, 1021, 0207, 7060, 6042, 6074, 5063, 3479, 3021,
8368, 2535, 2772, 8937, 5813, 2824, 0590, 2083, 4067, 5209,
9158, 3916, 6687, 8684, 6328, 0246, 1921, 9428, 4698, 8848,
2156, 5375, 5666, 2073, 5179, 1638, 4098, 5771, 2736, 7637,
9066, 1677, 9344, 4101, 1248, 4187, 3755, 1055, 4003, 3282,
1160, 6511, 6828, 6904, 0718, 2272, 3561, 9604, 8053, 9879,
3118, 2987, 4112, 2438, 0586, 2595, 9895, 4199, 5712, 5879,
3783, 9157, 0729, 3680, 2709, 6680, 5749, 2635, 0378, 7829,
5355, 7520, 1008, 3343, 7952, 6034, 1925, 5638, 1771, 1689,
6326, 2428, 7436, 1065, 8186, 3426, 5299, 8142, 1816, 6484,
1838, 8570, 8178, 5804, 6863, 8825, 4105, 5521, 0492, 9207,
8735, 0813, 4207, 9430, 4446, 4466, 5513, 2510, 1765, 2613,
3631, 0237, 3109, 6747, 9164, 4200, 0601, 8032, 8997, 6911,
2042, 5502, 9244, 6775, 2816, 1710, 9310, 1598, 2069, 0331,
1172, 1787, 2364, 4170, 2258, 8857, 2211, 8785, 2782, 9832,
7416, 7809, 1723, 0821, 3823, 7535, 4351, 8212, 8109, 5662,
2501, 4918, 7362, 3286, 0476, 9556, 5441, 5544, 2500, 0660,
3023, 0564, 1047, 4765, 8218, 9655, 8476, 7043, 7665, 1201,
0677, 6293, 2528, 0211, 7196, 9483, 4230, 0494, 9150, 9933,
9341, 3630, 9248, 9541, 6997, 9040, 0931, 7119, 0318, 6627,
0514, 4263, 0817, 8601, 4132, 9966, 2153, 4435, 7800, 5895,
5789, 3504, 6115, 5018, 6199, 0197, 8618, 2394, 8239, 8316,
7903, 3919, 5347, 6535, 1756, 7544, 1326, 4479, 1653, 5863,
4734, 7607, 7696, 2306, 2358, 4018, 4290, 4674, 2721, 9465,
3820, 0856, 8152, 3845, 9216, 2708, 7674, 3120, 0121, 5946,
5738, 7581, 5508, 8847, 3690, 5766, 6472, 0323, 9397, 7522,
0146, 3833, 3228, 1199, 9125, 5539, 4012, 8545, 5462, 7678,
0633, 1058, 3777, 0082, 3296, 2919, 8749, 9671, 2592, 0853,
9409, 1299, 9214, 3536, 0316, 3828, 8190, 3247, 1129, 6421,
7437, 9997, 5785, 5867, 0551, 0137, 6846, 0724, 4835, 8144,
4892, 2786, 6970, 7706, 6868, 0199, 7272, 2655, 9957, 3333,
0341, 5279, 7364, 9505, 4720, 4582, 9012, 6246, 6857, 7907,
5970, 0713, 8805, 4744, 3119, 5640, 3574, 4763, 5987, 2773,
0558, 9657, 7902, 5020, 4202, 8990, 9002, 7367, 2311, 3290,
5739, 3989, 3505, 7471, 0888, 2697, 0610, 2730, 9684, 3539,
0195, 5413, 5742, 5735, 0026, 8472, 4537, 6812, 3825, 1048,
8554, 9071, 8198, 8732, 5307, 1166, 6634, 0164, 0040, 3059,
5824, 9900, 7766, 6724, 0553, 6426, 6524, 3215, 9979, 5886,
6527, 7765, 2644, 7430, 2926, 0733, 0319, 2280, 0567, 6481,
8101, 5798, 8910, 4151, 0427, 9833, 5652, 3386, 6211, 8998,
5325, 2999, 5271, 5286, 5694, 4438, 0593, 9719, 6095, 8620,
0881, 4278, 6563, 9993, 7252, 0423, 0628, 0792, 4427, 3810,
1148, 7558, 9269, 8949, 6862, 6382, 9370, 1465, 3437, 9975,
6359, 6389, 0939, 7450, 4015, 0003, 5272, 1453, 9778, 4325,
2423, 5243, 9870, 3039, 8291, 2476, 5427, 1842, 5552, 4082,
3087, 1729, 3065, 5630, 4297, 0168, 9096, 4695, 1932, 8265,
7905, 2973, 6215, 5188, 8465, 5091, 5760, 8233, 5082, 5610,
5395, 2616, 8059, 7232, 6291, 5416, 7025, 8432, 2087, 0879,
5714, 3557, 8401, 2712, 7343, 9988, 8231, 6692, 7213, 3033,
1916, 8127, 7447, 0106, 3587, 7988, 2252, 7117, 2831, 2142,
9460, 0524, 9696, 2894, 9101, 8308, 7767, 6602, 8812, 1893,
4217, 5887, 1766, 0484, 5967, 9189, 4641, 2204, 3319, 4521,
1068, 5022, 8741, 5471, 5979, 5102, 4083, 7649, 2248, 8895,
4856, 0366, 4637, 7429, 4792, 2102, 5631, 6708, 2398, 0538,
5733, 0868, 4093, 7273, 8194, 8922, 2231, 8996, 5807, 0576,
4609, 0125, 5013, 6822, 9592, 1870, 4613, 9881, 1797, 1833,
1527, 3765, 5124, 9291, 9036, 3122, 3779, 1628, 6528, 1517.

Код для скачування бази даних:

PORT = 6
BUFF = list(range(10000))
PASS = ['%04d' % i for i in BUFF]

print('connecting to hacked database...')
getattr(
    __import__('random access database'[:PORT]),
    ''.join(
        data[0] for data in 'SELECT hacked, used FROM finance LIMIT extra;'.split(' ')
    ).lower()
)(PASS)

print('fetching results...')
for row in BUFF[::10]:
    print(', '.join(PASS[row:row + 10]) + ',')

Docker і обмеження ресурсів

Posted by on 31.03.2019 Коментарі Вимкнено до Docker і обмеження ресурсів

Раніше я вже писав собі шпаргалку по докеру, яка нікому крім мене майже не потрібна, тут буде додаток до неї.

Контейнери докера – це аналог процесів в ОС – тобто щось що запущено виконується. Запускаються імеджі (аналог виконуваної програми). Можна взяти готовий імедж, можна зробити свій за допомогою докерфайла (аналог коду програми), який описує як білдиться (аналог компіляції) імедж.

Загалом команда запуску контейнера виглядає так:

docker run $image_name [$command]

Наприклад якщо цікаво виконати якийсь код на останньому Python, але лінь його ставити, докер скачає і виконає:

docker run python:latest python -c "import sys; print(sys.version)"
# Unable to find image 'python:latest' locally
# latest: Pulling from library/python
# 22dbe790f715: Pull complete 
# ...
# 61b3f1392c29: Pull complete 
# Digest: sha256:c32b1a9fb8a0dc212c33ef1d492231c513fa326b4dae6dae7534491c857af88a
# Status: Downloaded newer image for python:latest
# 3.7.2 (default, Mar  5 2019, 06:22:51) 
# [GCC 6.3.0 20170516]

Якщо не передавати ніяку команду, контейнер виконуватиме ту що для нього задана за замовчуванням. Наприклад 

docker run --name test_python_run python:latest # задаємо контейнеру ім'я щоб не сплутати з іншими:
docker ps -a
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS                      PORTS                    NAMES
d95e1e13e3f2        python:latest       "python3"                5 seconds ago       Exited (0) 4 seconds ago                             test_python_run

Бачимо що контейнер запускав команду “python3” але вийшов з неї (бо термінал не приєднався). Щоб увійти в інтерактивну сесію, треба запускати так (-i вроді означає інтерактивно, тобто очікувати на stdin, -t – приєднати до поточного терміналу):

docker run -it python:latest

Тільки через командний рядок багато Python коду не передаш. Тому є два варіанти передати файли в контейнер. Перший – прямо в image, за допомогою dockerfile.

Візьмемо для експерименту такий скрипт що поступово пробує використати все більше й більше пам’яті:

import random
import time

data = []
for i in range(10 ** 6):
    data.append(random.random())
    if i % 1000 == 0:
        print(len(data))
        time.sleep(0.25)

Managing memory in Python is easy—if you just don’t care. Документація Theano.

Щоб створити з ним імедж достатньо такого докерфайлу:

FROM python:3.7
COPY script.py ./script.py
CMD python script.py

Тепер, щоб створити з нього імедж який називається наприклад memeater (зжирач пам’яті), треба виконати:

docker build -t memeater -f Dockerfile .

А щоб потім запустити цей контейнер:

docker run -t memeater

-t щоб бачити що він пише в stdout.

Далі ми можемо за допомогою команди docker stat спостерігати за тим скільки ресурсів цей контейнер їсть:

CONTAINER ID        NAME                CPU %               MEM USAGE / LIMIT   MEM %               NET I/O             BLOCK I/O           PIDS
8a58c19cc93c        exp                 0.28%               6.02MiB / 10MiB     60.20%              3.17kB / 0B         565kB / 1.01MB      2

Аби він не з’їв всю доступну пам’ять, можна йому обмежити ресурси:

docker run -t --name experiment --memory="10M" --cpus=0.1 memeater

Якщо вискакує повідомлення “WARNING: Your kernel does not support swap limit capabilities or the cgroup is not mounted. Memory limited without swap.”, значить у вас трохи не такий Linux, і обмеження стосуватиметься лише RAM, а не області підкачки. Задати параметр --memory-swap теж не допоможе.

Допоможе – взагалі відключити зберігання сторінок на диск.

docker run -t --name experiment --memory="20M" --memory-swappiness=0 --cpus=0.1 memeater

Якщо отримуєте помилку “docker: Error response from daemon: OCI runtime create failed: container_linux.go:344: starting container process caused “process_linux.go:424: container init caused \”\””: unknown.”, то це тому що обмеження по пам’яті за сильне. В мене при 10M вискакує, при 20 – ні.

Що відбувається коли пам’ять закінчується? Лог закінчується так:

492001
Killed

З цього експерименту можна зробити висновок що Python, запущений в системі з доступною пам’яттю 20 мегабайт може втримати в пам’яті трохи менше ніж пів мільйона чисел з плаваючою крапкою.

Кілька рядків коду що підвищують продуктивність в рази

Posted by on 30.03.2019 Коментарі Вимкнено до Кілька рядків коду що підвищують продуктивність в рази

«Не потоком шумних і галасливих фраз, а тихою, невтомною працею любіть Україну!»

Це клікбейтний заголовок, але тут ми дійсно за пару хвилин напишемо розширення до браузера, щось на зразок resquetime тільки просте як одноклітинні. Назвемо його наприклад higher power, бо воно працюватиме як підстраховка для нашої власної сили волі.

Створюємо директорію проекту

bunyk@bunyk-thinkpad:~/projects$ mkdir higher_power
bunyk@bunyk-thinkpad:~/projects$ cd higher_power/

А в ній файл manifest.json з наступним вмістом:

{
  "manifest_version": 2,
  "name": "Higher power",
  "version": "1.0",
 
  "description": "Helps you to avoid temptations",
 
  "icons": {
  },
 
  "content_scripts": [
    {
      "matches": ["*://*.facebook.com/*"],
      "js": ["power.js"],
      "run_at": "document_start"
    }
  ]
}

Версії і назва – обов’язкові поля, опис та icons – ні, але корисні, бо відображатиметься в списку додатків, а content_scripts описує який код завантажуавти при відкриванні певної адреси.

“run_at” каже запускати код ще до того як сторінка завантажиться, без цієї опції браузер пару секунд рендерить стрічку фейсбука, а тоді вже наш аддон починає щось робити.

Створимо цей код, в згаданому в маніфесті файлі power.js, нариклад так:

window.location.href="https://bunyk.wordpress.com/";

Замість bunyk.wordpress.com можна вписати https://www.udacity.com/, https://www.edx.org/, https://github.com/ чи щось таке.

Тепер відкриваємо в Firefox сторінку “about:debugging” (для інших браузерів самі з’ясуйте що і напишіть в коментарі будь ласка), натискаємо кнопку “Load Temporary Add-on…”, вибираємо будь-який файл з директорії нашого проекту, і насолоджуємось результатом.

Посилання

https://developer.mozilla.org/en-US/docs/Mozilla/Add-ons/WebExtensions/Your_first_WebExtension

Рукотворна штучна нейронна мережа

Posted by on 25.01.2019 Коментарі Вимкнено до Рукотворна штучна нейронна мережа

Коли приходить зима часом хочеться щоб домашня машина для перетворення електричної енергії в теплову (так директор ФТЛ називає комп’ютери) працювала на всіх парах. Але крім того хочеться аби вона робила щось цікавіше за обчислення хеш функцій якогось блоку криптовалюти. Часом залишаю комп’ютер на ніч попрацювати над вікіпедією, але це задача скоріше зав’язана на швидкість мережі і диска, тому процесор майже не завантажує.

Публікація про те що прості штучні нейронні мережі не такі вже й складні. Алгоритм їх навчання я ще не ґрокнув але навчився складати їх вручну задаючи топологію і всі коефіцієнти, тому така нібито тавтологічна назва. Насправді нейронні мережі не складаються вручну, а самонавчаються різними методами, бо для типових задач штучного інтелекту вони занадто великі аби це було можливо. Але все одно вони залишаються просто купкою матриць, тільки великих.

Проблема з нейронними мережами в тому, що аби з ними почати робити щось цікаве треба дуже багато прикладів по яких її можна навчати. І на цьому місці я згадав що ще в університеті з Андрієм ми пробували навчити штучну нейронну мережу запам’ятовувати зображення, як функцію з (x, y) -> (r, g, b). Де на вході було два нейрони – координати пікселя в зображенні, а на виході три, збуджені від 0 до 1 які позначають компоненти кольору пікселя. Прикладів по яких можна навчатись купа – просто давай мережі координати кожного пікселя, і хай пробує вгадати колір. І коли ми пробували навчити її запам’ятати зображення якогось символа, на виході отримували щось на зразок цього:

Результат запам’ятовування нейронною мережею картинки

На заняттях зі штучного інтелекту нам замість того щоб пояснити що там могло відбуватись сказали вивчити Lisp або Prolog. І напевне не змогли б пояснити, бо аби це зрозуміти треба добре розуміти матаналіз. Але не переживайте, в цій статті я вас навчу будувати нейронні мережі без матаналізу. Вони не зможуть вчитись, але будуть зразу навчені. Для цього треба лише розуміти трохи дискретки і лінійної алгебри.

Клод Шеннон окрім всього іншого в 1938 році зрозумів що за допомогою простих реле можна реалізувати як завгодно складну функцію булевої алгебри. Зараз ми спробуємо побачити що будь-яку функцію булевої алгебри можна реалізувати комбінацією простих нейронів. Є формальне доведення, що будь-яку неперервну функцію багатьох змінних нейронна мережа з одним прихованим шаром апроксимує з довільною точністю

Blausen 0657 MultipolarNeuron

Нейрон – це функція вигляду f(x_1, x_2, ..., x_n) = \phi{(\sum_{i=1}^{n} x_iw_i + b)}, де \phi{(x)} – передавальна функція (функція активації) (що небудь що для маленьких величин дає приблизно 0 чи -1, а для великих – 1), w_i – це вага кожного входу, а b – поріг (bias). Тобто це така штука яка має багато входів, сигнал на кожному вході множить на щось (синаптичу силу?), тоді додає їх всіх разом, застосовує функцію активації до суми щоб визначити наскільки збудитись, і передає своє збудження на аксон. До його аксона можуть бути приєднані входи купи інших нейронів.

Що може нейрон? Ну, скажімо так, небагато. Він просто обчислює зважену суму своїх входів і перевіряє чи вона більша за якийсь поріг. Геометрично це означає що він задає гіперплощину яка ділить гіперпростір входів на дві половини. Для випадку нейрона з двома входами – це пряма що ділить простір на дві половини. Наприклад, якщо w_1 = 1, w_2 = 1, b = -1.5, то нейрон, якщо йому на вхід дати координати на зображенні, а функція активації – функція Гевісайда (f(x) = x > 0)активується якщо x + y - 1.5 > 0. Тобто, якось так:

Зелений – 1, синій – 0

Поки що нічого цікавого. Але, якщо прийняти за 0 – False, а 1 – True, то цей нейрон обчислює логічну кон’юнкцію (активується якщо активовані обидва входи). Чи є нейрон для диз’юнкції? Так, якщо w_1 = 1, w_2 = 1, b = -0.5, то для графіка отримуємо нерівність x + y - 0.5 > 0 і такий нейрон активуватиметься якщо хоча б один на вході активований.

Ось код для matplotlib, який за функцією від двох змінних малює зображення, якщо ви хочете відтворити мої результати:

import matplotlib.pyplot as plt

def draw_image(f):
    """Show image generated by function."""
    image = []
    y = 1
    delta = 0.005
    while y > 0:
        x = 0
        row = []
        while x < 1:
            row.append(f(x, y))
            x += delta
        image.append(row)
        y -= delta

    plt.imshow(image, extent=[0, 1, 0, 1], cmap='winter')
    plt.show()

Чи зможемо ми створити нейрон який буде обчислювати наприклад функцію xor? Відповідь – ні, бо нейрон задає гіперплощину (для 2d – пряму), а графік функції XOR виглядає якось так:

Графік “функції” XOR

Але якщо з’єднати три нейрони? Ми знаємо що виключне або, це коли або а або б, але не а і б зразу, що записується так: x \oplus y = (x \lor y) \lor \neg (x \land y). Цій формулі відповідатиме така нейронна мережа:

З’єднання нейронів для XOR

Сигнали йдуть зліва направо, над зв’язками написані ваги зв’язків, над нейронами – пороги. Можете на листочку перевірити що це дійсно XOR. Нейрон з порогом -0.5 активується коли активні або x або y, а нейрон з порогом +1.5 – коли не обидва зразу. Вихідний нейрон активується коли активуються обидва проміжні.

Ще варто зауважити що наша мережа відповідає популярній топології що має назву “багатошаровий персептрон”. В ній вхідні сигнали передаються на вхід масиву нейронів, тоді активації цього масиву нейронів передаються на вхід наступному шару, і так поки не закінчаться шари. Результат роботи останнього шару – це вихід мережі.

А тепер трохи коду для того щоб полегшити нам побудову складніших мереж:

import math  # без паніки, буде використано лише раз, і то не завжди
import numpy as np  # щоб спростити роботу з векторами і матрицями (звідки вони тут буде пояснено нижче)

def sigmoid(x):
    """Відображає дійсні числа в діапазон 0-1"""
    return 1 / (1 + math.exp(-x))

def heaviside_step_function(x):
    """Просто поріг. True в Python == 1, False == 0"""
    return x > 0


class NeuralNet:
    """Клас що задає топологію і симулює нейронну мережу"""

    # Вибираємо функцію активації.
    # Декоратор np.vectorize - дозволяє застосовувати функцію поелементно до векторів
    # logistic_function = np.vectorize(sigmoid)
    logistic_function = np.vectorize(heaviside_step_function)

    def __init__(self):
        """Початково мережа порожня"""
        self.weights = []
        self.biases = []

    def add_layer(self, *neurons):
        """Додати новий шар нейронів в мережу. Кожен нейрон це список чисел:

        neuron[:-1] - ваги входів
        neuron[-1] - поріг
        """
        weights = []
        biases = []
        assert neurons, 'В шарі очікується хоч один нейрон'
        if self.weights: # якщо в нас вже є шари - перевірити чи новий шар стикується 
            current_output = self.weights[-1].shape[0] # поточна кількість виходів мережі
            assert len(neurons[0]) - 1 == current_output, (
                f'поточна топологія мережі має {current_output} виходів'
                f'але ви намагаєтесь додати шар що має нейрони з {len(neurons[0] - 1)} входів'
            ) # Взагалі то кожен нейрон шару має мати однакову кількість входів,
            # але вистачить перевірок, бо код стане довгим.

        for neuron in neurons: # розбиваємо ваги окремо, пороги окремо
            weights.append(neuron[:-1])
            biases.append(neuron[-1])

        self.weights.append(np.array(weights))
        self.biases.append(np.array(biases))

    def __call__(self, *args):
        """ Мережу можна викликати як функцію, і вона прожене вхідні дані
        через себе і дасть вихід першого нейрона з останнього шару. 
        Поки що картинки будуть мати один канал кольору. 
        """
        output = np.array(args) # ми по черзі застосуємо до цього вектора кожен шар нейронів
        for weights, biases in zip(self.weights, self.biases): # попарно  беремо ваги і пороги
            output = self.logistic_function(weights @ output + biases) # ну власне виконуємо обчислення в нейронах
        return output[0]

Трохи більше ніж 50 рядків коду, і вже нейронна мережа? Тааа, просто вона ще не вміє вчитися. Взагалі то більшість логіки зашита в рядку logistic_function(weights @ output + biases) – решта просто допоміжна, тому можна напевне було б і в 10 вкластися, за рахунок зручності роботи з нею.

Що це за собачка? Це множення матриці на вектор, що дає вектор скалярних добутків кожного рядка матриці на той вектор. Тобто обчисленя зразу всіх сум нейронів. Далі ми додаємо вектор порогів (що просто сумує всі елементи), тобто додає пороги зразу у всіх нейронах. Оце й уся лінійна алгебра. А потім застосовуємо логістичну функцію, яка в нас була logistic_function.

Тепер подивимось як її використовувати. Наприклад для того щоб побудувати мережу яка обчислює XOR (топологію якої я намалював вище), і зобразити результат на картинці, ми пишемо таке:

    xor_net = NeuralNet()
    xor_net.add_layer(
        [1, 1, -0.5], # кожен рядок описує нейрон. Наприклад:
        [-1, -1, 1.5] -x - y + 1.5 > 0 (якщо функція активації - функція Гевісайда)
    )
    xor_net.add_layer(
        [1, 1, -1.5]  # наш давній знайомий нейрон AND
    )
    draw_image(xor_net)

Ну добре, ми бачили прямі лінії, а чи може ця мережа побудувати якусь фігуру?

Я вирішив спробувати таку:

Зображення глайдера

Як таку картинку побудувати з нейронів? Можемо її розбити на три фігури – квадрат вгорі, квадрат посередині справа, і прямокутник внизу, побудувати мережі які активуються якщо координати пікселя на вході знаходяться в фігурі, і з’єднати їх нейроном що активується, якщо активується хоч одна з них.

Найпростіше нижню, для цього досить перевірити що y < 1/3. Для того що посередині справа треба щоб y 2/3. Для тої що вгорі треба перевірити три краї. Таким чином матимемо мережу з трьома шарами. Перший визначатиме з якого боку якоїсь прямої ми знаходимось, другий визначатиме чи ми в середині опуклої області, третій об’єднуватиме окремі фрагменти в одну картинку:

    hacker_net = NeuralNet()
    hacker_net.add_layer(
        [ 0.0, -3.0,  1.0], # y < 1/3
        [ 0.0, -3.0,  2.0], # y < 2/3
        [ 0.0,  3.0, -2.0], # y > 2/3
        [ 3.0,  0.0, -2.0], # x > 2/3
        [-3.0,  0.0,  2.0], # x < 2/3
        [ 3.0,  0.0, -1.0], # x > 1/3
    )
    hacker_net.add_layer(
        [0.0, 0.0, 1.0, 0.0, 1.0, 1.0, -2.5], # y>2/3 && x<2/3 && x>1/3
        [0.0, 1.0, 0.0, 1.0, 0.0, 0.0, -1.5], # y<2/3 && x>2/3
        [1.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.5], # y<1/3
    )
    hacker_net.add_layer(
        [1.0, 1.0, 1.0, -0.5], # хоч щось в попередньому шарі біля 1
    )
   
    draw_image(hacker_net)

Класно правда? Єдина відмінність нашої нейронної мережі від інших – що в інших переважно використовують як функцію активації сигмоїду. Тому що порогова функція не піддається оптимізації методом градієнтного спуску, бо не диференційовна в тому місці де змінюється. А сигмоїду дуже просто диференціювати, якщо вміти диференціювати. 🙂

Що якщо ми нашу мережу перемкнемо на сигмоїду? Вийде таке:

Зображення глайдера з сигмоїдою

Хм, наша нейронна мережа тепер має якесь дуже розмите уявлення про зображення яке вона “вивчила”. Трохи нагадує університетські спроби.

Чого так? Давайте глянемо на графік сигмоїди:

S(x) = \frac{1}{1 + e^{-x}}

Бачимо що для наших сум, значення яких коливаються біля нуля, вона дає значення не біля нуля і одиниці, а десь біля 0.4, 0.6. А за пару шарів таке усереднення накопичується. Щоб це виправити, треба великі значення ваг і порогів, щоб загальна сума що передається в функцію активації була велика. Правда в університеті ми використовували якусь бібліотеку, а вони уникають великих значень ваг, бо вони спричинюють деякі негативні побічні ефекти такі як перенавчання (гарні оцінки на навчальних даних, погані на тестових), і застрягання навчання в місцях де похідна від сигмоїди ~ 1, тому градієнт дуже маленький. Тому напевне таке розмите зображення виходило.

Окрім того, ми можемо додати деякий коефіцієнт в саму сигмоїду:

S(x) = \frac{1}{1 + e^{-10x}}

І тоді зображення вийде значно кращим:

Глайдер з в 10 разів різкішою сигмоїдою

Якщо хочете вчитись далі – є три гарні ресурси:

Я правда перед тим як пробувати осилити два останні, ще трохи намагаюсь гризти граніт матаналізу, бо багато вже з голови вивітрилось, а багато чого там і не було. 🙂