notebook.community

Edit and run

Personality prediction





In [2]:



    


import numpy as np
np.random.seed(113) #set seed before any keras import
import pandas as pd
import random
from sklearn.model_selection import train_test_split
from collections import defaultdict
from keras.preprocessing import sequence
from collections import Counter



    


















    






Using TensorFlow backend.

Dataset

First we load the dataset. I built a single csv file that is easy to load and handle using pandas. The original label tagset of TwiSty consists of 16 different labels, however I am going to transform it into a binary classification problem: I will only predict the I(introvert) and E(extrovert) personality traits.

The dataset is huge and it require a lot of RAM: for this reason I decided to trim the maximum number of characters of text per author to 1000. This means that the toy will be a toy model.





In [99]:



    


seed=0
corpus = pd.read_csv('twistytest.csv', 
                     index_col=0, 
                     header=1, 
                     names=['user_id', 'lang', 'text', 'mbti'])

#here we limit the corpus size. The SVM with all the text can learn somethign
corpus.text = corpus.text.apply(lambda x: x) 
corpus.mbti = corpus.mbti.apply(lambda x: x[0])

#corpus = tmp.sample(frac=1, random_state=seed)
e = corpus[corpus.mbti.apply(lambda x: x == 'E')]
i = corpus[corpus.mbti.apply(lambda x: x == 'I')].sample(226)
corpus = pd.concat([e,i]).sample(frac=1, random_state=seed)
print(corpus.shape)

## set max length of doc per author
sentences = corpus.text#.apply(lambda x: x[:100000])
## trim labels: convert problem to binary classification I vs E
labels = corpus.mbti

## make sure we have a label for every data instance
assert(len(sentences)==len(labels))
data={}
np.random.seed(113) #seed
data['target']= np.random.permutation(labels)
np.random.seed(113) # use same seed!
data['data'] = np.random.permutation(sentences)



    


















    






(452, 4)

















In [100]:



    


# preview the dataset
print(corpus.shape)
corpus.head()



    


















    






(452, 4)










    
Out[100]:










  
    

      
      user_id
      lang
      text
      mbti
    

  
  
    

      544
      113022898
      de
      ['@Stoffnuss Ich glaube Emil wird nicht lange ...
      E
    

    

      280
      108731189
      it
      ['http://t.co/pYyYAMCJAc', "AGE SEMPRE PIU' PR...
      E
    

    

      848
      313458775
      de
      ['@Jaqi_Metalbraut wh00t? Ich dacht Endivie wä...
      I
    

    

      324
      531664179
      it
      ["#Ironman3 in one of the most glorious movies...
      I
    

    

      483
      1166332766
      it
      ['La tecnologia mi odia.', "Io stamattina: ogg...
      I
    

  




















In [101]:



    


# plot the distribution of labels

import matplotlib.pyplot as plt

l, v = zip(*Counter(y_train).items())
indexes = np.arange(len(l))
width = 1
plt.bar(indexes, v, width, color=['r', 'b'])
plt.xticks(indexes + width * 0.5, l)
plt.show()



    


















    
























In [102]:



    


#split the data into train, dev, test

X_rest, X_test, y_rest, y_test = train_test_split(data['data'], data['target'], test_size=0.2)
X_train, X_dev, y_train, y_dev = train_test_split(X_rest, y_rest, test_size=0.2)
del X_rest, y_rest
print("#train instances: {} #dev: {} #test: {}".format(len(X_train),len(X_dev),len(X_test)))



    


















    






#train instances: 288 #dev: 73 #test: 91

















In [103]:



    


# compute random baseline per class
Counter(y_test)['I']/sum(Counter(y_test).values())



    


















    
Out[103]:








0.5274725274725275

Test and dev set label distribution





In [104]:



    


# test
l, v = zip(*Counter(y_test).items())
indexes = np.arange(len(l))
width = 1
plt.bar(indexes, v, width, color=['r', 'b'])
plt.xticks(indexes + width * 0.5, l)
plt.show()



    


















    
























In [105]:



    


# dev
l, v = zip(*Counter(y_dev).items())
indexes = np.arange(len(l))
width = 1
plt.bar(indexes, v, width, color=['r', 'b'])
plt.xticks(indexes + width * 0.5, l)
plt.show()

Baseline

For the baseline we use an SVM with a sparse feature representation.

We use both character- and word-ngrams.





In [96]:



    


from sklearn.svm import LinearSVC
from sklearn.dummy import DummyClassifier
from sklearn.pipeline import Pipeline, FeatureUnion
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics import accuracy_score
from sklearn.metrics import classification_report

pipeline = Pipeline([('features', FeatureUnion([('wngram', TfidfVectorizer(ngram_range=(1,2))),
                                                ('cngram', TfidfVectorizer(analyzer='char'))])),
                     ('cls', DummyClassifier())])
pipeline.fit(X_train, y_train)
predictions = pipeline.predict(X_dev)
accuracy_score(predictions, y_dev)

print(classification_report(predictions, y_dev))

testpredictions = pipeline.predict(X_test)
print(accuracy_score(testpredictions, y_test))

print(classification_report(testpredictions, y_test))



    


















    






             precision    recall  f1-score   support

          E       0.45      0.65      0.53        31
          I       0.62      0.43      0.51        42

avg / total       0.55      0.52      0.52        73

0.483516483516
             precision    recall  f1-score   support

          E       0.47      0.45      0.46        44
          I       0.50      0.51      0.51        47

avg / total       0.48      0.48      0.48        91


















In [106]:



    


from sklearn.svm import LinearSVC
from sklearn.dummy import DummyClassifier
from sklearn.pipeline import Pipeline, FeatureUnion
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics import accuracy_score
from sklearn.metrics import classification_report

pipeline = Pipeline([('features', FeatureUnion([('wngram', TfidfVectorizer(ngram_range=(1,2))),
                                                ('cngram', TfidfVectorizer(analyzer='char'))])),
                     ('cls', LinearSVC())])
pipeline.fit(X_train, y_train)
predictions = pipeline.predict(X_dev)
accuracy_score(predictions, y_dev)

print(classification_report(predictions, y_dev))



    


















    






             precision    recall  f1-score   support

          E       0.64      0.68      0.66        41
          I       0.55      0.50      0.52        32

avg / total       0.60      0.60      0.60        73

Results

The SVM works quite well already: we outperform the random baseline by a signficant margin.





In [107]:



    


testpred = pipeline.predict(X_test)
print(accuracy_score(testpred, y_test))
print(classification_report(testpred, y_test))



    


















    






0.692307692308
             precision    recall  f1-score   support

          E       0.67      0.67      0.67        43
          I       0.71      0.71      0.71        48

avg / total       0.69      0.69      0.69        91

Neural network

First we have to encode the labels in the one-hot format. Since this is a binary classification format, we don't convert them to a categorical format.





In [30]:



    


from keras.utils import np_utils
y2i = defaultdict(lambda: len(y2i))
y_train_num = [y2i[mbti] for mbti in y_train]
y_dev_num = [y2i[mbti] for mbti in y_dev]
y_test_num = [y2i[mbti] for mbti in y_test]
num_classes = len(np.unique(y_train_num))
print(num_classes)



    


















    






2

Text representation

For the baseline we used a one-hot encoding. For our neural model we are going to represent the text using a dense representation. We will be building it from characters.





In [31]:



    


from collections import defaultdict

# convert words to indices, taking care of UNKs
def get_characters(sentence, c2i):
    out = []
    for word in sentence.split(" "):
        chars = []
        for c in word:
            chars.append(c2i[c])
        out.append(chars)
    return out

c2i = defaultdict(lambda: len(c2i))

PAD = c2i["<pad>"] # index 0 is padding
UNK = c2i["<unk>"] # index 1 is for UNK
X_train_num = [get_characters(sentence, c2i) for sentence in X_train]
c2i = defaultdict(lambda: UNK, c2i) # freeze - cute trick!
X_dev_num = [get_characters(sentence, c2i) for sentence in X_dev]
X_test_num = [get_characters(sentence, c2i) for sentence in X_test]

max_sentence_length=max([len(s.split(" ")) for s in X_train] 
                        + [len(s.split(" ")) for s in X_dev] 
                        + [len(s.split(" ")) for s in X_test] )
max_word_length = max([len(word)  for sentence in X_train_num for word in sentence])



    











In [32]:



    


### we need both max sent and word length
print(max_sentence_length)
print(max_word_length)
print(X_train[0:2])
print(X_train_num[0:2]) # example how the first two sentences are encoded



    


















    






893
139
[ '[\'Dio, se esisti, aiutami!\', \'The Walking Dead Game Season 2 Episode 3 Trailer: http://t.co/VC66OtRYjf \\nOMMIODDIO!\', \'La mia cara compagna di banco e le sue perle #invalsi2014 http://t.co/RPY9nn2ZO1\', \'Chiedo perdono se non sono molto attiva ultimamente\', \'Comunque non fidatevi della gente, è simpatica solo perché siete in qualche modo utili\', \'#iononvotoM5S anche perché io non posso proprio votare, ehehhe!\', \'"@JFloydZeppelin: @bohemianfloyd http://t.co/gfxe3OQAQJ" you\\\'re a very very nice person :\\\')\', \'Ma perché i Noctiluca sono bioluminescenti e io no?\\nMi sento profondamente offesa\', \'Questa settimana ho:\\n-Versione\\n-Compito di inglese, scienze, disegno e fisica\\n-Interrogazione di poesia e compito http://t.co/dwYafO4h96\', \'Domani ho la versione, è stato un piacere conoscervi :D\', \'Perché perdere tempo con le persone che vi stanno antipatiche, quando potete semplicemente ignorarle?\', \'@hatewillkillus nera ;)\', \'Oggi è una giornata da bestemmia\', "Boh la mia prof di italiano mi fa salire il crimine, l\'omicidio e il mal di testa. Come fa?!", \'Anzi non come lo fa, ma PERCHÉ DIAVOLO NON MI LASCIA VIVERE IN PACE LA MIA ESISTENZA?!\', \'Lo dico sinceramente, non confido molto in #ACUnity . La Ubisoft ha distrutto la trama dopo AC3... spero di sbagliarmi\', \'Vado a guardare i biglietti per tirarmi su il morale ....\', \'"@Multiplayerit: Davvero! :D http://t.co/ZCeN0rOAyp" fottuto Uncharted...\', \'Voglio ringraziare pubblicamente le persone particolarmente brutte perché aumentano la mia autostima. Grazie, ne avevo bisogno, davvero!\', \'Prima mio padre stava guardando colorado ed ero tentata di scappare da casa\', \'Mother should i build the wall?\', \'@allmustDie_ siamo in due http://t.co/FT35VsJ1Qz\', "Qualche oretta fa c\'era un temporale con il sole...\\nAnche il tempo meteorologico mi prende in giro, che bellezza!", \'Non capite, essere svegliati è terribile, poi se per svegliarti accendono le luci sale il crimine in tempi record\', \'I giorni scorsi non sono riuscita ad ascoltare i Pink Floyd, infatti sono state giornataccie :D\', \'Non sopporto più mio fratello, è più fastidioso dello spam o dei pop up\', "L\'arte gotica è troppo soporifera, come diavolo faccio a studiarla?!", \'Secondo me la quarta risposta è quella giusta http://t.co/eCNUUlTdQc\', \'DEVO assolutamente modificare il profilo\', \'Guys, non ho voglia di studiare storia\', \'HO LA MEDIA DEL SETTE IN MATEMATICA! IMPRECO PER LA FELICITÀ\', \'Boh io oggi ho smesso definitivamente di studiare :D\', \'@QueenFan98 secondo me è un fotomontaggio\', \'Un mio compagno ha comprato una rosa alla sua ragazza per il mesiversario.\\nAvete capito bene, MESIVERSARIO,  che stronzata è mai questa?\', \'Non posso ancora credere di essere in vacanza :D\', \'Noo, la connessione fa schifo. Compiangetemi\', \'Ho appena visto qualche video di erika masiniello\\nnon dovevo farlo\', \'Sto per comprare il vinile di The Wall, aspetto questo momento da gennaio\', \'@FloddyMan ahahahha felice di conoscerti :D\', \'@MaxxGhe concordo!\', \'Ora guardo Star Wars perchéè da troppo che non lo guardo\', \'Perché perché perché perché perché perché perché perché perché perché perché perché perché perché perché lo hai fatto, Anakin ?\', "Volevo condividere con voi la mia opera d\'arte su brain training.... ma che ci faccio su brain training a quest\'ora?! http://t.co/n6pEq68mBD", "Non posso crederci :\') http://t.co/FsMe1pr73X", \'Chi tifate questa sera? \\nIo Olanda, la Spagna non la sopporto\', \'In questi giorni sto solo oziando, molto produttivo, davvero!\', \'NOOOO\', \'No no no no no no no\', \'@intostarkness ommioddio ma quanti nove hai? Complimentoni!\', \'@intostarkness D: cavolo! Hai una pagella molto varia ahaha\', "L\'arbitro mi sta facendo salire il crimine im una maniera impressionante", \'Ma che bel goal!\', \'ROSICA, SPAGNA!\', \'SPAGNA, ROSICA! pt 2\', \'W I FUORIGIOCO\', \'OHOHOHOHOH Casillias..... VAN PERSIE DOMINA!\', \'Ultimamente non faccio altro che ignorare\', "Ho la media perfetta dell\'otto e il mio prof di scienze mi ha messo sette. Ma prima di fare le medie si è mangiato i funghi allucinogeni?!", \'E poi non bisogna bestemmiare\', \'#ItaliaInghilterra grande Italia!\', \'WTF?! http://t.co/FPRMKqgZ9x\', \'#np Pink Floyd - The Wall\', \'@Stone_ColdCrazy Sì, è bellissimo a dir poco\', \'"Ma perché non metti una tua foto, magari una selfie"\\nNO, MAI E POI MAI\', \'La prof ha dato una lista di libri da leggere. \\nUnico problema: lei non capisce che io ho tonnellate di libri da leggere per conto mio\', \'A volte vorrei mangiare certe persone antipatiche, proprio come Majin Bu, Hannibal e David Gilmour.\\n\\nOvviamente non posso e devo sopportarle\', \'Ma avete un attacco improvviso di moralismo? Ma per piacere!\', \'Discoteca aka vaccaio\', \'Mi sento pro perchè sono riuscita a far funzionare il mangianastri, ora si ascoltano i Queen come se non ci fosse un domani\', \'Ma esiste davvero gente che ride così, "ihihihihihi", come i cavalli?!\', \'#colombiacostadavorio senza dubbio è la partita più seguita del secolo\\n....\\nSicuramente!\', \'@LoudLikeBrian ti capisco, a'
 '[\'http://t.co/AUia5mDe\', "L\'italia s\'è desta...: Giorni della memoria come se piovesse http://t.co/ITtgz49a", \'Asimov... fottutissimo genio\', \'Ah ma che cazzo non ti puoi guardare neanche più zelig che ogni volta ti sbattono in faccia la pubblicità del Mediaset  http://t.co/HXPBB3xD\', \'Adesso mi inzavano con il nonno e m vek n8u grand napol!\', \'Servizio Pubblico - Diretta http://t.co/d70DRTBk via @Serv_Pubblico\', \'Il mio paese è fantastico: rinvia una partita per un pò di pioggia, lascia morire dei bambini non chiudendo le scuole per una tempesta.\', \'la persona più triste? quella che guarda sempre gli altri, li giudica, fa un pensiero riflessivo e poi si mette al di sopra. ho la bacheca z\', "Spread, sfondato il tetto dei 500 punti - Per chi ha studiato un pò, sa che vuol dire CIAO CIAO Italia. L\'europa è morta, l\'italia è morta,", \'Video divertentissimo, accoppiato da me :P\\n\\nhttp://t.co/bxOEcd8Q http://t.co/RKqeQuQc\', \'Dico io: cassiere in banca, in estate stai al fresco, in inverno al caldo. Fai si e no 6 ore di lavoro al giorno. Prend http://t.co/zzJBT3VO\', \'che succede se cerchi "do a barrel roll" in google?\', \'Il cancro del paese. http://t.co/QGqKqwx6\', \'Vedere chi ha contribuito ad affondare un paese di 60 milioni di persone fuori dalla galera e chi ha affondato una nave da 4200 passeggeri p\', "è troppo chiedere che chi crede in qualsiasi religione schiatti al più presto per il bene dell\'umanità?", \'la casta è viva e lotta contro di noi\', \'Ci sta ricchione e ricchione. Se non sei famoso e non ti chiami DALLA, scordatelo il funerale in chiesa. Per i mafiosi, i pedofili, gli stra\', \'Un sistema basato sulle risorse e non sul denaro. Sono nato in un mondo non alla mia altezza.\', \'Dopo più di due mesi il sito diventa aperto a tutti. gg\\n\\n http://t.co/hgtCi0iX\', "Finiti i 14 libri dei cicli di ASIMOV O_O. In lettura Neanche gli Dei (speriamo sia all\'altezza)", \'non disturbare\', \'non disturbare, non sono al pc\', \'Art 18 cosa cambia http://t.co/AfvmshLm\', \'http://t.co/jJVEHbrm\', \'♥_♥ http://t.co/eSDrZOlX\', \'Telefonata a Sky contro Caressa in Juve - Napoli.: http://t.co/7bEqJTho via @youtube\', \'Napoli, scontri davanti ad Equitalia – Il Fatto Quotidiano TV http://t.co/BVOR65jc #fattoquotidiano via @fattoquotidiano\', \'Napoli, scontri davanti ad Equitalia http://t.co/BVOR65jc\', \'http://t.co/UPYWmMuN\', \'Il Futuro del nostro Mondo: http://t.co/QrRCqyc6 via @youtube\', \'@fioredamora Ma si, resta sempre una festa religiosa e per me religione è sinonimo di ignoranza.\', \'Tweet #FirmaDay\', \'Strage USA: Barbara stai apposto per 2 anni con le puntate! @carmelitadurso\', \'http://t.co/TFHEJayD\', \'Tsunami Tour: http://t.co/eaQtfhu6 via @youtube\', \'http://t.co/fQX9AYYB #tsunamitour\', \'Perché? http://t.co/qdX2JBhx\', \'Movimento 5 Stelle: http://t.co/OKJsxclIK2 via @youtube\', \'Presidente del seggio ladra: http://t.co/Fg68le7jBH via @youtube\', \'@beppe_grillo Subito conflitto di interessi con PD MONTI e INGROIA e abbandonare la trattativa appena cercano di fare i furbi.\', \'http://t.co/jS8XAEBBxs\', \'M5S Folli: http://t.co/zRB5CwUKX3 tramite @YouTube\', \'COPASIR e VIGILANZA RAI al MoVimento 5 Stelle.\\nLa volta buona che scopriremo la verità sulle stragi? #movimento5stelle\', \'Farsi prendere dal panico da soli è come ridere da soli in una stanza vuota. Uno si sente veramente stupido\', \'essere modelle protessioniste significa venire pagate per reagire in modo eccessivo a cose come riso soffiato e scarpe nuove\', \'@beppe_grillo  votate con il pd: conflitto di interessi,reddito di cittadinanza,sostegno alla piccola e media impresa,finanziamento partiti\', \'Il solo motivo per cui chiediamo ad altre persone come è andato il loro fi-ne settimana è perché così gli possiamo raccontare il nostro\', \'Non voglio velleitarie mescolanze con nessuno nemmeno più con voi, ma non sopporto neanche la legge dilagante del fatti i cazzi tuoi\', "@MattiaPasini I prezzi della benzina sono la punta dell\'iceberg, andarsene per quello è tipico da italiano medio", \'@Mov5Stelle :)\', \'I quiz in tv sn studiati per farci sentire a nostro agio in quei fatti casuali e inutili chesn tt quel che ci rimane della nostra istruzione\', "Quand\'è che il futuro è passato dall\'essere una promessa a essere una minaccia?", \'@paomio17 @beppe_grillo è ovvio che stesse parlando dei due B (bersani berlusconi) XD\', \'@beppe_grillo @moviment5stelle @byoblu @gnoma1988\\n alla fine Viola Tesi è collegata in qualche modo a chi voleva fregare il simbolo m5s?\', \'La storia non tiene conto MAI del coraggio.\', \'#HappyBirthdayJustinFromItaly http://t.co/xiyezlMh9B\', \'#rt #ouo seguimi e ti seguo, non unfollowo.\', "Ma che faccione da bambino che c\'ha De Gregorio, con quell\'espressione da cucciolo, tenta di fare la vittima... in galera con il padrone!!!", \'@Adriano_Palozzi ma per favore, ahahahahaha\', \'@ubaldopantani grande :D\', \'@ilpdl qnd vince"I magistrati non vogliono farci governare"qnd perde"I magistrati non vogliono farci fare opposizione"@beppe_grillo comico?\', \'@BlueNavigation @Mov5Stelle credon']
[[[2, 3, 4, 5, 6, 7], [8, 9], [9, 8, 5, 8, 10, 5, 7], [11, 5, 12, 10, 11, 13, 5, 14, 3, 7], [3, 15, 16, 9], [17, 11, 18, 19, 5, 20, 21], [4, 9, 11, 22], [23, 11, 13, 9], [24, 9, 11, 8, 6, 20], [25], [26, 27, 5, 8, 6, 22, 9], [28], [15, 29, 11, 5, 18, 9, 29, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 34, 35, 36, 36, 37, 10, 38, 39, 40, 41], [42, 20, 37, 43, 43, 44, 37, 4, 4, 44, 37, 14, 3, 7], [3, 45, 11], [13, 5, 11], [33, 11, 29, 11], [33, 6, 13, 27, 11, 21, 20, 11], [22, 5], [46, 11, 20, 33, 6], [9], [18, 9], [8, 12, 9], [27, 9, 29, 18, 9], [47, 5, 20, 48, 11, 18, 8, 5, 25, 49, 50, 51], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 38, 52, 39, 53, 20, 20, 25, 54, 37, 50, 3, 7], [3, 35, 16, 5, 9, 22, 6], [27, 9, 29, 22, 6, 20, 6], [8, 9], [20, 6, 20], [8, 6, 20, 6], [13, 6, 18, 10, 6], [11, 10, 10, 5, 48, 11], [12, 18, 10, 5, 13, 11, 13, 9, 20, 10, 9, 3, 7], [3, 35, 6, 13, 12, 20, 55, 12, 9], [20, 6, 20], [41, 5, 22, 11, 10, 9, 48, 5], [22, 9, 18, 18, 11], [21, 9, 20, 10, 9, 7], [56], [8, 5, 13, 27, 11, 10, 5, 33, 11], [8, 6, 18, 6], [27, 9, 29, 33, 16, 57], [8, 5, 9, 10, 9], [5, 20], [55, 12, 11, 18, 33, 16, 9], [13, 6, 22, 6], [12, 10, 5, 18, 5, 3, 7], [3, 47, 5, 6, 20, 6, 20, 48, 6, 10, 6, 43, 58, 24], [11, 20, 33, 16, 9], [27, 9, 29, 33, 16, 57], [5, 6], [20, 6, 20], [27, 6, 8, 8, 6], [27, 29, 6, 27, 29, 5, 6], [48, 6, 10, 11, 29, 9, 7], [9, 16, 9, 16, 16, 9, 14, 3, 7], [3, 59, 60, 61, 62, 18, 6, 63, 22, 54, 9, 27, 27, 9, 18, 5, 20, 30], [60, 46, 6, 16, 9, 13, 5, 11, 20, 41, 18, 6, 63, 22], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 21, 41, 64, 9, 28, 37, 65, 66, 65, 61, 59], [63, 6, 12, 42, 3, 29, 9], [11], [48, 9, 29, 63], [48, 9, 29, 63], [20, 5, 33, 9], [27, 9, 29, 8, 6, 20], [30, 42, 3, 67, 3, 7], [3, 43, 11], [27, 9, 29, 33, 16, 57], [5], [68, 6, 33, 10, 5, 18, 12, 33, 11], [8, 6, 20, 6], [46, 5, 6, 18, 12, 13, 5, 20, 9, 8, 33, 9, 20, 10, 5], [9], [5, 6], [20, 6, 69, 42, 20, 43, 5], [8, 9, 20, 10, 6], [27, 29, 6, 41, 6, 20, 22, 11, 13, 9, 20, 10, 9], [6, 41, 41, 9, 8, 11, 3, 7], [3, 65, 12, 9, 8, 10, 11], [8, 9, 10, 10, 5, 13, 11, 20, 11], [16, 6, 30, 42, 20, 70, 34, 9, 29, 8, 5, 6, 20, 9, 42, 20, 70, 35, 6, 13, 27, 5, 10, 6], [22, 5], [5, 20, 21, 18, 9, 8, 9, 7], [8, 33, 5, 9, 20, 71, 9, 7], [22, 5, 8, 9, 21, 20, 6], [9], [41, 5, 8, 5, 33, 11, 42, 20, 70, 44, 20, 10, 9, 29, 29, 6, 21, 11, 71, 5, 6, 20, 9], [22, 5], [27, 6, 9, 8, 5, 11], [9], [33, 6, 13, 27, 5, 10, 6], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 22, 72, 39, 11, 41, 37, 51, 16, 53, 36, 3, 7], [3, 4, 6, 13, 11, 20, 5], [16, 6], [18, 11], [48, 9, 29, 8, 5, 6, 20, 9, 7], [56], [8, 10, 11, 10, 6], [12, 20], [27, 5, 11, 33, 9, 29, 9], [33, 6, 20, 6, 8, 33, 9, 29, 48, 5], [30, 4, 3, 7], [3, 52, 9, 29, 33, 16, 57], [27, 9, 29, 22, 9, 29, 9], [10, 9, 13, 27, 6], [33, 6, 20], [18, 9], [27, 9, 29, 8, 6, 20, 9], [33, 16, 9], [48, 5], [8, 10, 11, 20, 20, 6], [11, 20, 10, 5, 27, 11, 10, 5, 33, 16, 9, 7], [55, 12, 11, 20, 22, 6], [27, 6, 10, 9, 10, 9], [8, 9, 13, 27, 18, 5, 33, 9, 13, 9, 20, 10, 9], [5, 21, 20, 6, 29, 11, 29, 18, 9, 69, 3, 7], [3, 60, 16, 11, 10, 9, 72, 5, 18, 18, 19, 5, 18, 18, 12, 8], [20, 9, 29, 11], [73, 67, 3, 7], [3, 37, 21, 21, 5], [56], [12, 20, 11], [21, 5, 6, 29, 20, 11, 10, 11], [22, 11], [46, 9, 8, 10, 9, 13, 13, 5, 11, 3, 7], [59, 74, 6, 16], [18, 11], [13, 5, 11], [27, 29, 6, 41], [22, 5], [5, 10, 11, 18, 5, 11, 20, 6], [13, 5], [41, 11], [8, 11, 18, 5, 29, 9], [5, 18], [33, 29, 5, 13, 5, 20, 9, 7], [18, 3, 6, 13, 5, 33, 5, 22, 5, 6], [9], [5, 18], [13, 11, 18], [22, 5], [10, 9, 8, 10, 11, 32], [35, 6, 13, 9], [41, 11, 69, 14, 59, 7], [3, 66, 20, 71, 5], [20, 6, 20], [33, 6, 13, 9], [18, 6], [41, 11, 7], [13, 11], [52, 26, 38, 35, 75, 76], [4, 44, 66, 34, 37, 45, 37], [68, 37, 68], [43, 44], [45, 66, 24, 35, 44, 66], [34, 44, 34, 26, 38, 26], [44, 68], [52, 66, 35, 26], [45, 66], [43, 44, 66], [26, 24, 44, 24, 15, 26, 68, 54, 66, 69, 14, 3, 7], [3, 45, 6], [22, 5, 33, 6], [8, 5, 20, 33, 9, 29, 11, 13, 9, 20, 10, 9, 7], [20, 6, 20], [33, 6, 20, 41, 5, 22, 6], [13, 6, 18, 10, 6], [5, 20], [47, 66, 35, 77, 20, 5, 10, 63], [32], [45, 11], [77, 46, 5, 8, 6, 41, 10], [16, 11], [22, 5, 8, 10, 29, 12, 10, 10, 6], [18, 11], [10, 29, 11, 13, 11], [22, 6, 27, 6], [66, 35, 28, 32, 32, 32], [8, 27, 9, 29, 6], [22, 5], [8, 46, 11, 21, 18, 5, 11, 29, 13, 5, 3, 7], [3, 34, 11, 22, 6], [11], [21, 12, 11, 29, 22, 11, 29, 9], [5], [46, 5, 21, 18, 5, 9, 10, 10, 5], [27, 9, 29], [10, 5, 29, 11, 29, 13, 5], [8, 12], [5, 18], [13, 6, 29, 11, 18, 9], [32, 32, 32, 32, 3, 7], [3, 59, 60, 43, 12, 18, 10, 5, 27, 18, 11, 63, 9, 29, 5, 10, 30], [4, 11, 48, 48, 9, 29, 6, 14], [30, 4], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 54, 35, 9, 68, 49, 29, 37, 66, 63, 27, 59], [41, 6, 10, 10, 12, 10, 6], [77, 20, 33, 16, 11, 29, 10, 9, 22, 32, 32, 32, 3, 7], [3, 34, 6, 21, 18, 5, 6], [29, 5, 20, 21, 29, 11, 71, 5, 11, 29, 9], [27, 12, 46, 46, 18, 5, 33, 11, 13, 9, 20, 10, 9], [18, 9], [27, 9, 29, 8, 6, 20, 9], [27, 11, 29, 10, 5, 33, 6, 18, 11, 29, 13, 9, 20, 10, 9], [46, 29, 12, 10, 10, 9], [27, 9, 29, 33, 16, 57], [11, 12, 13, 9, 20, 10, 11, 20, 6], [18, 11], [13, 5, 11], [11, 12, 10, 6, 8, 10, 5, 13, 11, 32], [23, 29, 11, 71, 5, 9, 7], [20, 9], [11, 48, 9, 48, 6], [46, 5, 8, 6, 21, 20, 6, 7], [22, 11, 48, 48, 9, 29, 6, 14, 3, 7], [3, 52, 29, 5, 13, 11], [13, 5, 6], [27, 11, 22, 29, 9], [8, 10, 11, 48, 11], [21, 12, 11, 29, 22, 11, 20, 22, 6], [33, 6, 18, 6, 29, 11, 22, 6], [9, 22], [9, 29, 6], [10, 9, 20, 10, 11, 10, 11], [22, 5], [8, 33, 11, 27, 27, 11, 29, 9], [22, 11], [33, 11, 8, 11, 3, 7], [3, 43, 6, 10, 16, 9, 29], [8, 16, 6, 12, 18, 22], [5], [46, 12, 5, 18, 22], [10, 16, 9], [72, 11, 18, 18, 69, 3, 7], [3, 60, 11, 18, 18, 13, 12, 8, 10, 4, 5, 9, 78], [8, 5, 11, 13, 6], [5, 20], [22, 12, 9], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 62, 15, 28, 58, 34, 8, 61, 50, 65, 71, 3, 7], [59, 65, 12, 11, 18, 33, 16, 9], [6, 29, 9, 10, 10, 11], [41, 11], [33, 3, 9, 29, 11], [12, 20], [10, 9, 13, 27, 6, 29, 11, 18, 9], [33, 6, 20], [5, 18], [8, 6, 18, 9, 32, 32, 32, 42, 20, 66, 20, 33, 16, 9], [5, 18], [10, 9, 13, 27, 6], [13, 9, 10, 9, 6, 29, 6, 18, 6, 21, 5, 33, 6], [13, 5], [27, 29, 9, 20, 22, 9], [5, 20], [21, 5, 29, 6, 7], [33, 16, 9], [46, 9, 18, 18, 9, 71, 71, 11, 14, 59, 7], [3, 68, 6, 20], [33, 11, 27, 5, 10, 9, 7], [9, 8, 8, 9, 29, 9], [8, 48, 9, 21, 18, 5, 11, 10, 5], [56], [10, 9, 29, 29, 5, 46, 5, 18, 9, 7], [27, 6, 5], [8, 9], [27, 9, 29], [8, 48, 9, 21, 18, 5, 11, 29, 10, 5], [11, 33, 33, 9, 20, 22, 6, 20, 6], [18, 9], [18, 12, 33, 5], [8, 11, 18, 9], [5, 18], [33, 29, 5, 13, 5, 20, 9], [5, 20], [10, 9, 13, 27, 5], [29, 9, 33, 6, 29, 22, 3, 7], [3, 44], [21, 5, 6, 29, 20, 5], [8, 33, 6, 29, 8, 5], [20, 6, 20], [8, 6, 20, 6], [29, 5, 12, 8, 33, 5, 10, 11], [11, 22], [11, 8, 33, 6, 18, 10, 11, 29, 9], [5], [52, 5, 20, 19], [62, 18, 6, 63, 22, 7], [5, 20, 41, 11, 10, 10, 5], [8, 6, 20, 6], [8, 10, 11, 10, 9], [21, 5, 6, 29, 20, 11, 10, 11, 33, 33, 5, 9], [30, 4, 3, 7], [3, 68, 6, 20], [8, 6, 27, 27, 6, 29, 10, 6], [27, 5, 79], [13, 5, 6], [41, 29, 11, 10, 9, 18, 18, 6, 7], [56], [27, 5, 79], [41, 11, 8, 10, 5, 22, 5, 6, 8, 6], [22, 9, 18, 18, 6], [8, 27, 11, 13], [6], [22, 9, 5], [27, 6, 27], [12, 27, 3, 7], [59, 45, 3, 11, 29, 10, 9], [21, 6, 10, 5, 33, 11], [56], [10, 29, 6, 27, 27, 6], [8, 6, 27, 6, 29, 5, 41, 9, 29, 11, 7], [33, 6, 13, 9], [22, 5, 11, 48, 6, 18, 6], [41, 11, 33, 33, 5, 6], [11], [8, 10, 12, 22, 5, 11, 29, 18, 11, 69, 14, 59, 7], [3, 24, 9, 33, 6, 20, 22, 6], [13, 9], [18, 11], [55, 12, 11, 29, 10, 11], [29, 5, 8, 27, 6, 8, 10, 11], [56], [55, 12, 9, 18, 18, 11], [21, 5, 12, 8, 10, 11], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 9, 35, 68, 77, 77, 18, 15, 22, 65, 33, 3, 7], [3, 4, 26, 34, 37], [11, 8, 8, 6, 18, 12, 10, 11, 13, 9, 20, 10, 9], [13, 6, 22, 5, 41, 5, 33, 11, 29, 9], [5, 18], [27, 29, 6, 41, 5, 18, 6, 3, 7], [3, 23, 12, 63, 8, 7], [20, 6, 20], [16, 6], [48, 6, 21, 18, 5, 11], [22, 5], [8, 10, 12, 22, 5, 11, 29, 9], [8, 10, 6, 29, 5, 11, 3, 7], [3, 75, 37], [45, 66], [43, 26, 4, 44, 66], [4, 26, 45], [24, 26, 15, 15, 26], [44, 68], [43, 66, 15, 26, 43, 66, 15, 44, 35, 66, 14], [44, 43, 52, 38, 26, 35, 37], [52, 26, 38], [45, 66], [62, 26, 45, 44, 35, 44, 15, 80, 3, 7], [3, 74, 6, 16], [5, 6], [6, 21, 21, 5], [16, 6], [8, 13, 9, 8, 8, 6], [22, 9, 41, 5, 20, 5, 10, 5, 48, 11, 13, 9, 20, 10, 9], [22, 5], [8, 10, 12, 22, 5, 11, 29, 9], [30, 4, 3, 7], [3, 60, 65, 12, 9, 9, 20, 62, 11, 20, 53, 81], [8, 9, 33, 6, 20, 22, 6], [13, 9], [56], [12, 20], [41, 6, 10, 6, 13, 6, 20, 10, 11, 21, 21, 5, 6, 3, 7], [3, 77, 20], [13, 5, 6], [33, 6, 13, 27, 11, 21, 20, 6], [16, 11], [33, 6, 13, 27, 29, 11, 10, 6], [12, 20, 11], [29, 6, 8, 11], [11, 18, 18, 11], [8, 12, 11], [29, 11, 21, 11, 71, 71, 11], [27, 9, 29], [5, 18], [13, 9, 8, 5, 48, 9, 29, 8, 11, 29, 5, 6, 32, 42, 20, 66, 48, 9, 10, 9], [33, 11, 27, 5, 10, 6], [46, 9, 20, 9, 7], [43, 26, 24, 44, 34, 26, 38, 24, 66, 38, 44, 37, 7], [], [33, 16, 9], [8, 10, 29, 6, 20, 71, 11, 10, 11], [56], [13, 11, 5], [55, 12, 9, 8, 10, 11, 69, 3, 7], [3, 68, 6, 20], [27, 6, 8, 8, 6], [11, 20, 33, 6, 29, 11], [33, 29, 9, 22, 9, 29, 9], [22, 5], [9, 8, 8, 9, 29, 9], [5, 20], [48, 11, 33, 11, 20, 71, 11], [30, 4, 3, 7], [3, 68, 6, 6, 7], [18, 11], [33, 6, 20, 20, 9, 8, 8, 5, 6, 20, 9], [41, 11], [8, 33, 16, 5, 41, 6, 32], [35, 6, 13, 27, 5, 11, 20, 21, 9, 10, 9, 13, 5, 3, 7], [3, 75, 6], [11, 27, 27, 9, 20, 11], [48, 5, 8, 10, 6], [55, 12, 11, 18, 33, 16, 9], [48, 5, 22, 9, 6], [22, 5], [9, 29, 5, 19, 11], [13, 11, 8, 5, 20, 5, 9, 18, 18, 6, 42, 20, 20, 6, 20], [22, 6, 48, 9, 48, 6], [41, 11, 29, 18, 6, 3, 7], [3, 24, 10, 6], [27, 9, 29], [33, 6, 13, 27, 29, 11, 29, 9], [5, 18], [48, 5, 20, 5, 18, 9], [22, 5], [15, 16, 9], [17, 11, 18, 18, 7], [11, 8, 27, 9, 10, 10, 6], [55, 12, 9, 8, 10, 6], [13, 6, 13, 9, 20, 10, 6], [22, 11], [21, 9, 20, 20, 11, 5, 6, 3, 7], [3, 60, 62, 18, 6, 22, 22, 63, 43, 11, 20], [11, 16, 11, 16, 11, 16, 16, 11], [41, 9, 18, 5, 33, 9], [22, 5], [33, 6, 20, 6, 8, 33, 9, 29, 10, 5], [30, 4, 3, 7], [3, 60, 43, 11, 64, 64, 23, 16, 9], [33, 6, 20, 33, 6, 29, 22, 6, 14, 3, 7], [3, 37, 29, 11], [21, 12, 11, 29, 22, 6], [24, 10, 11, 29], [17, 11, 29, 8], [27, 9, 29, 33, 16, 57, 56], [22, 11], [10, 29, 6, 27, 27, 6], [33, 16, 9], [20, 6, 20], [18, 6], [21, 12, 11, 29, 22, 6, 3, 7], [3, 52, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [27, 9, 29, 33, 16, 57], [18, 6], [16, 11, 5], [41, 11, 10, 10, 6, 7], [66, 20, 11, 19, 5, 20], [69, 3, 7], [59, 34, 6, 18, 9, 48, 6], [33, 6, 20, 22, 5, 48, 5, 22, 9, 29, 9], [33, 6, 20], [48, 6, 5], [18, 11], [13, 5, 11], [6, 27, 9, 29, 11], [22, 3, 11, 29, 10, 9], [8, 12], [46, 29, 11, 5, 20], [10, 29, 11, 5, 20, 5, 20, 21, 32, 32, 32, 32], [13, 11], [33, 16, 9], [33, 5], [41, 11, 33, 33, 5, 6], [8, 12], [46, 29, 11, 5, 20], [10, 29, 11, 5, 20, 5, 20, 21], [11], [55, 12, 9, 8, 10, 3, 6, 29, 11, 69, 14], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 20, 36, 27, 26, 55, 36, 81, 13, 74, 4, 59, 7], [59, 68, 6, 20], [27, 6, 8, 8, 6], [33, 29, 9, 22, 9, 29, 33, 5], [30, 3, 67], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 62, 8, 43, 9, 50, 27, 29, 82, 28, 83, 59, 7], [3, 35, 16, 5], [10, 5, 41, 11, 10, 9], [55, 12, 9, 8, 10, 11], [8, 9, 29, 11, 69], [42, 20, 44, 6], [37, 18, 11, 20, 22, 11, 7], [18, 11], [24, 27, 11, 21, 20, 11], [20, 6, 20], [18, 11], [8, 6, 27, 27, 6, 29, 10, 6, 3, 7], [3, 44, 20], [55, 12, 9, 8, 10, 5], [21, 5, 6, 29, 20, 5], [8, 10, 6], [8, 6, 18, 6], [6, 71, 5, 11, 20, 22, 6, 7], [13, 6, 18, 10, 6], [27, 29, 6, 22, 12, 10, 10, 5, 48, 6, 7], [22, 11, 48, 48, 9, 29, 6, 14, 3, 7], [3, 68, 37, 37, 37, 37, 3, 7], [3, 68, 6], [20, 6], [20, 6], [20, 6], [20, 6], [20, 6], [20, 6, 3, 7], [3, 60, 5, 20, 10, 6, 8, 10, 11, 29, 19, 20, 9, 8, 8], [6, 13, 13, 5, 6, 22, 22, 5, 6], [13, 11], [55, 12, 11, 20, 10, 5], [20, 6, 48, 9], [16, 11, 5, 69], [35, 6, 13, 27, 18, 5, 13, 9, 20, 10, 6, 20, 5, 14, 3, 7], [3, 60, 5, 20, 10, 6, 8, 10, 11, 29, 19, 20, 9, 8, 8], [4, 30], [33, 11, 48, 6, 18, 6, 14], [75, 11, 5], [12, 20, 11], [27, 11, 21, 9, 18, 18, 11], [13, 6, 18, 10, 6], [48, 11, 29, 5, 11], [11, 16, 11, 16, 11, 3, 7], [59, 45, 3, 11, 29, 46, 5, 10, 29, 6], [13, 5], [8, 10, 11], [41, 11, 33, 9, 20, 22, 6], [8, 11, 18, 5, 29, 9], [5, 18], [33, 29, 5, 13, 5, 20, 9], [5, 13], [12, 20, 11], [13, 11, 20, 5, 9, 29, 11], [5, 13, 27, 29, 9, 8, 8, 5, 6, 20, 11, 20, 10, 9, 59, 7], [3, 43, 11], [33, 16, 9], [46, 9, 18], [21, 6, 11, 18, 14, 3, 7], [3, 38, 37, 24, 44, 35, 66, 7], [24, 52, 66, 23, 68, 66, 14, 3, 7], [3, 24, 52, 66, 23, 68, 66, 7], [38, 37, 24, 44, 35, 66, 14], [27, 10], [25, 3, 7], [3, 17], [44], [62, 77, 37, 38, 44, 23, 44, 37, 35, 37, 3, 7], [3, 37, 75, 37, 75, 37, 75, 37, 75, 37, 75], [35, 11, 8, 5, 18, 18, 5, 11, 8, 32, 32, 32, 32, 32], [34, 66, 68], [52, 26, 38, 24, 44, 26], [4, 37, 43, 44, 68, 66, 14, 3, 7], [3, 77, 18, 10, 5, 13, 11, 13, 9, 20, 10, 9], [20, 6, 20], [41, 11, 33, 33, 5, 6], [11, 18, 10, 29, 6], [33, 16, 9], [5, 21, 20, 6, 29, 11, 29, 9, 3, 7], [59, 75, 6], [18, 11], [13, 9, 22, 5, 11], [27, 9, 29, 41, 9, 10, 10, 11], [22, 9, 18, 18, 3, 6, 10, 10, 6], [9], [5, 18], [13, 5, 6], [27, 29, 6, 41], [22, 5], [8, 33, 5, 9, 20, 71, 9], [13, 5], [16, 11], [13, 9, 8, 8, 6], [8, 9, 10, 10, 9, 32], [43, 11], [27, 29, 5, 13, 11], [22, 5], [41, 11, 29, 9], [18, 9], [13, 9, 22, 5, 9], [8, 5], [56], [13, 11, 20, 21, 5, 11, 10, 6], [5], [41, 12, 20, 21, 16, 5], [11, 18, 18, 12, 33, 5, 20, 6, 21, 9, 20, 5, 69, 14, 59, 7], [3, 26], [27, 6, 5], [20, 6, 20], [46, 5, 8, 6, 21, 20, 11], [46, 9, 8, 10, 9, 13, 13, 5, 11, 29, 9, 3, 7], [3, 47, 44, 10, 11, 18, 5, 11, 44, 20, 21, 16, 5, 18, 10, 9, 29, 29, 11], [21, 29, 11, 20, 22, 9], [44, 10, 11, 18, 5, 11, 14, 3, 7], [3, 17, 15, 62, 69, 14], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 62, 52, 38, 43, 84, 55, 21, 54, 53, 64, 3, 7], [3, 47, 20, 27], [52, 5, 20, 19], [62, 18, 6, 63, 22], [70], [15, 16, 9], [17, 11, 18, 18, 3, 7], [3, 60, 24, 10, 6, 20, 9, 78, 35, 6, 18, 22, 35, 29, 11, 71, 63], [24, 85, 7], [56], [46, 9, 18, 18, 5, 8, 8, 5, 13, 6], [11], [22, 5, 29], [27, 6, 33, 6, 3, 7], [3, 59, 43, 11], [27, 9, 29, 33, 16, 57], [20, 6, 20], [13, 9, 10, 10, 5], [12, 20, 11], [10, 12, 11], [41, 6, 10, 6, 7], [13, 11, 21, 11, 29, 5], [12, 20, 11], [8, 9, 18, 41, 5, 9, 59, 42, 20, 68, 37, 7], [43, 66, 44], [26], [52, 37, 44], [43, 66, 44, 3, 7], [3, 45, 11], [27, 29, 6, 41], [16, 11], [22, 11, 10, 6], [12, 20, 11], [18, 5, 8, 10, 11], [22, 5], [18, 5, 46, 29, 5], [22, 11], [18, 9, 21, 21, 9, 29, 9, 32], [42, 20, 77, 20, 5, 33, 6], [27, 29, 6, 46, 18, 9, 13, 11, 30], [18, 9, 5], [20, 6, 20], [33, 11, 27, 5, 8, 33, 9], [33, 16, 9], [5, 6], [16, 6], [10, 6, 20, 20, 9, 18, 18, 11, 10, 9], [22, 5], [18, 5, 46, 29, 5], [22, 11], [18, 9, 21, 21, 9, 29, 9], [27, 9, 29], [33, 6, 20, 10, 6], [13, 5, 6, 3, 7], [3, 66], [48, 6, 18, 10, 9], [48, 6, 29, 29, 9, 5], [13, 11, 20, 21, 5, 11, 29, 9], [33, 9, 29, 10, 9], [27, 9, 29, 8, 6, 20, 9], [11, 20, 10, 5, 27, 11, 10, 5, 33, 16, 9, 7], [27, 29, 6, 27, 29, 5, 6], [33, 6, 13, 9], [43, 11, 40, 5, 20], [74, 12, 7], [75, 11, 20, 20, 5, 46, 11, 18], [9], [4, 11, 48, 5, 22], [23, 5, 18, 13, 6, 12, 29, 32, 42, 20, 42, 20, 37, 48, 48, 5, 11, 13, 9, 20, 10, 9], [20, 6, 20], [27, 6, 8, 8, 6], [9], [22, 9, 48, 6], [8, 6, 27, 27, 6, 29, 10, 11, 29, 18, 9, 3, 7], [3, 43, 11], [11, 48, 9, 10, 9], [12, 20], [11, 10, 10, 11, 33, 33, 6], [5, 13, 27, 29, 6, 48, 48, 5, 8, 6], [22, 5], [13, 6, 29, 11, 18, 5, 8, 13, 6, 69], [43, 11], [27, 9, 29], [27, 5, 11, 33, 9, 29, 9, 14, 3, 7], [3, 4, 5, 8, 33, 6, 10, 9, 33, 11], [11, 19, 11], [48, 11, 33, 33, 11, 5, 6, 3, 7], [3, 43, 5], [8, 9, 20, 10, 6], [27, 29, 6], [27, 9, 29, 33, 16, 56], [8, 6, 20, 6], [29, 5, 12, 8, 33, 5, 10, 11], [11], [41, 11, 29], [41, 12, 20, 71, 5, 6, 20, 11, 29, 9], [5, 18], [13, 11, 20, 21, 5, 11, 20, 11, 8, 10, 29, 5, 7], [6, 29, 11], [8, 5], [11, 8, 33, 6, 18, 10, 11, 20, 6], [5], [65, 12, 9, 9, 20], [33, 6, 13, 9], [8, 9], [20, 6, 20], [33, 5], [41, 6, 8, 8, 9], [12, 20], [22, 6, 13, 11, 20, 5, 3, 7], [3, 43, 11], [9, 8, 5, 8, 10, 9], [22, 11, 48, 48, 9, 29, 6], [21, 9, 20, 10, 9], [33, 16, 9], [29, 5, 22, 9], [33, 6, 8, 85, 7], [59, 5, 16, 5, 16, 5, 16, 5, 16, 5, 16, 5, 59, 7], [33, 6, 13, 9], [5], [33, 11, 48, 11, 18, 18, 5, 69, 14, 3, 7], [3, 47, 33, 6, 18, 6, 13, 46, 5, 11, 33, 6, 8, 10, 11, 22, 11, 48, 6, 29, 5, 6], [8, 9, 20, 71, 11], [22, 12, 46, 46, 5, 6], [56], [18, 11], [27, 11, 29, 10, 5, 10, 11], [27, 5, 79], [8, 9, 21, 12, 5, 10, 11], [22, 9, 18], [8, 9, 33, 6, 18, 6, 42, 20, 32, 32, 32, 32, 42, 20, 24, 5, 33, 12, 29, 11, 13, 9, 20, 10, 9, 14, 3, 7], [3, 60, 45, 6, 12, 22, 45, 5, 19, 9, 74, 29, 5, 11, 20], [10, 5], [33, 11, 27, 5, 8, 33, 6, 7], [11]], [[2, 3, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 66, 77, 5, 11, 58, 13, 4, 9, 3, 7], [59, 45, 3, 5, 10, 11, 18, 5, 11], [8, 3, 56], [22, 9, 8, 10, 11, 32, 32, 32, 30], [23, 5, 6, 29, 20, 5], [22, 9, 18, 18, 11], [13, 9, 13, 6, 29, 5, 11], [33, 6, 13, 9], [8, 9], [27, 5, 6, 48, 9, 8, 8, 9], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 44, 15, 10, 21, 71, 51, 53, 11, 59, 7], [3, 66, 8, 5, 13, 6, 48, 32, 32, 32], [41, 6, 10, 10, 12, 10, 5, 8, 8, 5, 13, 6], [21, 9, 20, 5, 6, 3, 7], [3, 66, 16], [13, 11], [33, 16, 9], [33, 11, 71, 71, 6], [20, 6, 20], [10, 5], [27, 12, 6, 5], [21, 12, 11, 29, 22, 11, 29, 9], [20, 9, 11, 20, 33, 16, 9], [27, 5, 79], [71, 9, 18, 5, 21], [33, 16, 9], [6, 21, 20, 5], [48, 6, 18, 10, 11], [10, 5], [8, 46, 11, 10, 10, 6, 20, 6], [5, 20], [41, 11, 33, 33, 5, 11], [18, 11], [27, 12, 46, 46, 18, 5, 33, 5, 10, 86], [22, 9, 18], [43, 9, 22, 5, 11, 8, 9, 10], [], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 75, 83, 52, 74, 74, 28, 64, 4, 3, 7], [3, 66, 22, 9, 8, 8, 6], [13, 5], [5, 20, 71, 11, 48, 11, 20, 6], [33, 6, 20], [5, 18], [20, 6, 20, 20, 6], [9], [13], [48, 9, 19], [20, 81, 12], [21, 29, 11, 20, 22], [20, 11, 27, 6, 18, 14, 3, 7], [3, 24, 9, 29, 48, 5, 71, 5, 6], [52, 12, 46, 46, 18, 5, 33, 6], [70], [4, 5, 29, 9, 10, 10, 11], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 22, 82, 49, 4, 38, 15, 74, 19], [48, 5, 11], [60, 24, 9, 29, 48, 78, 52, 12, 46, 46, 18, 5, 33, 6, 3, 7], [3, 44, 18], [13, 5, 6], [27, 11, 9, 8, 9], [56], [41, 11, 20, 10, 11, 8, 10, 5, 33, 6, 30], [29, 5, 20, 48, 5, 11], [12, 20, 11], [27, 11, 29, 10, 5, 10, 11], [27, 9, 29], [12, 20], [27, 87], [22, 5], [27, 5, 6, 21, 21, 5, 11, 7], [18, 11, 8, 33, 5, 11], [13, 6, 29, 5, 29, 9], [22, 9, 5], [46, 11, 13, 46, 5, 20, 5], [20, 6, 20], [33, 16, 5, 12, 22, 9, 20, 22, 6], [18, 9], [8, 33, 12, 6, 18, 9], [27, 9, 29], [12, 20, 11], [10, 9, 13, 27, 9, 8, 10, 11, 32, 3, 7], [3, 18, 11], [27, 9, 29, 8, 6, 20, 11], [27, 5, 79], [10, 29, 5, 8, 10, 9, 69], [55, 12, 9, 18, 18, 11], [33, 16, 9], [21, 12, 11, 29, 22, 11], [8, 9, 13, 27, 29, 9], [21, 18, 5], [11, 18, 10, 29, 5, 7], [18, 5], [21, 5, 12, 22, 5, 33, 11, 7], [41, 11], [12, 20], [27, 9, 20, 8, 5, 9, 29, 6], [29, 5, 41, 18, 9, 8, 8, 5, 48, 6], [9], [27, 6, 5], [8, 5], [13, 9, 10, 10, 9], [11, 18], [22, 5], [8, 6, 27, 29, 11, 32], [16, 6], [18, 11], [46, 11, 33, 16, 9, 33, 11], [71, 3, 7], [59, 24, 27, 29, 9, 11, 22, 7], [8, 41, 6, 20, 22, 11, 10, 6], [5, 18], [10, 9, 10, 10, 6], [22, 9, 5], [58, 49, 49], [27, 12, 20, 10, 5], [70], [52, 9, 29], [33, 16, 5], [16, 11], [8, 10, 12, 22, 5, 11, 10, 6], [12, 20], [27, 87, 7], [8, 11], [33, 16, 9], [48, 12, 6, 18], [22, 5, 29, 9], [35, 44, 66, 37], [35, 44, 66, 37], [44, 10, 11, 18, 5, 11, 32], [45, 3, 9, 12, 29, 6, 27, 11], [56], [13, 6, 29, 10, 11, 7], [18, 3, 5, 10, 11, 18, 5, 11], [56], [13, 6, 29, 10, 11, 7, 59, 7], [3, 34, 5, 22, 9, 6], [22, 5, 48, 9, 29, 10, 9, 20, 10, 5, 8, 8, 5, 13, 6, 7], [11, 33, 33, 6, 27, 27, 5, 11, 10, 6], [22, 11], [13, 9], [30, 52, 42, 20, 42, 20, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 46, 64, 37, 26, 33, 22, 81, 65], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 38, 84, 55, 9, 65, 12, 65, 33, 3, 7], [3, 4, 5, 33, 6], [5, 6, 30], [33, 11, 8, 8, 5, 9, 29, 9], [5, 20], [46, 11, 20, 33, 11, 7], [5, 20], [9, 8, 10, 11, 10, 9], [8, 10, 11, 5], [11, 18], [41, 29, 9, 8, 33, 6, 7], [5, 20], [5, 20, 48, 9, 29, 20, 6], [11, 18], [33, 11, 18, 22, 6, 32], [62, 11, 5], [8, 5], [9], [20, 6], [36], [6, 29, 9], [22, 5], [18, 11, 48, 6, 29, 6], [11, 18], [21, 5, 6, 29, 20, 6, 32], [52, 29, 9, 20, 22], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 71, 71, 61, 74, 15, 28, 34, 37, 3, 7], [3, 33, 16, 9], [8, 12, 33, 33, 9, 22, 9], [8, 9], [33, 9, 29, 33, 16, 5], [59, 22, 6], [11], [46, 11, 29, 29, 9, 18], [29, 6, 18, 18, 59], [5, 20], [21, 6, 6, 21, 18, 9, 69, 3, 7], [3, 44, 18], [33, 11, 20, 33, 29, 6], [22, 9, 18], [27, 11, 9, 8, 9, 32], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 65, 23, 55, 84, 55, 72, 64, 36, 3, 7], [3, 34, 9, 22, 9, 29, 9], [33, 16, 5], [16, 11], [33, 6, 20, 10, 29, 5, 46, 12, 5, 10, 6], [11, 22], [11, 41, 41, 6, 20, 22, 11, 29, 9], [12, 20], [27, 11, 9, 8, 9], [22, 5], [36, 49], [13, 5, 18, 5, 6, 20, 5], [22, 5], [27, 9, 29, 8, 6, 20, 9], [41, 12, 6, 29, 5], [22, 11, 18, 18, 11], [21, 11, 18, 9, 29, 11], [9], [33, 16, 5], [16, 11], [11, 41, 41, 6, 20, 22, 11, 10, 6], [12, 20, 11], [20, 11, 48, 9], [22, 11], [51, 25, 49, 49], [27, 11, 8, 8, 9, 21, 21, 9, 29, 5], [27, 3, 7], [59, 56], [10, 29, 6, 27, 27, 6], [33, 16, 5, 9, 22, 9, 29, 9], [33, 16, 9], [33, 16, 5], [33, 29, 9, 22, 9], [5, 20], [55, 12, 11, 18, 8, 5, 11, 8, 5], [29, 9, 18, 5, 21, 5, 6, 20, 9], [8, 33, 16, 5, 11, 10, 10, 5], [11, 18], [27, 5, 79], [27, 29, 9, 8, 10, 6], [27, 9, 29], [5, 18], [46, 9, 20, 9], [22, 9, 18, 18, 3, 12, 13, 11, 20, 5, 10, 86, 69, 59, 7], [3, 18, 11], [33, 11, 8, 10, 11], [56], [48, 5, 48, 11], [9], [18, 6, 10, 10, 11], [33, 6, 20, 10, 29, 6], [22, 5], [20, 6, 5, 3, 7], [3, 35, 5], [8, 10, 11], [29, 5, 33, 33, 16, 5, 6, 20, 9], [9], [29, 5, 33, 33, 16, 5, 6, 20, 9, 32], [24, 9], [20, 6, 20], [8, 9, 5], [41, 11, 13, 6, 8, 6], [9], [20, 6, 20], [10, 5], [33, 16, 5, 11, 13, 5], [4, 66, 45, 45, 66, 7], [8, 33, 6, 29, 22, 11, 10, 9, 18, 6], [5, 18], [41, 12, 20, 9, 29, 11, 18, 9], [5, 20], [33, 16, 5, 9, 8, 11, 32], [52, 9, 29], [5], [13, 11, 41, 5, 6, 8, 5, 7], [5], [27, 9, 22, 6, 41, 5, 18, 5, 7], [21, 18, 5], [8, 10, 29, 11, 3, 7], [3, 77, 20], [8, 5, 8, 10, 9, 13, 11], [46, 11, 8, 11, 10, 6], [8, 12, 18, 18, 9], [29, 5, 8, 6, 29, 8, 9], [9], [20, 6, 20], [8, 12, 18], [22, 9, 20, 11, 29, 6, 32], [24, 6, 20, 6], [20, 11, 10, 6], [5, 20], [12, 20], [13, 6, 20, 22, 6], [20, 6, 20], [11, 18, 18, 11], [13, 5, 11], [11, 18, 10, 9, 71, 71, 11, 32, 3, 7], [3, 4, 6, 27, 6], [27, 5, 79], [22, 5], [22, 12, 9], [13, 9, 8, 5], [5, 18], [8, 5, 10, 6], [22, 5, 48, 9, 20, 10, 11], [11, 27, 9, 29, 10, 6], [11], [10, 12, 10, 10, 5, 32], [21, 21, 42, 20, 42, 20], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 16, 21, 10, 35, 5, 49, 5, 83, 3, 7], [59, 62, 5, 20, 5, 10, 5], [5], [50, 51], [18, 5, 46, 29, 5], [22, 9, 5], [33, 5, 33, 18, 5], [22, 5], [66, 24, 44, 43, 37, 34], [37, 78, 37, 32], [44, 20], [18, 9, 10, 10, 12, 29, 11], [68, 9, 11, 20, 33, 16, 9], [21, 18, 5], [4, 9, 5], [88, 8, 27, 9, 29, 5, 11, 13, 6], [8, 5, 11], [11, 18, 18, 3, 11, 18, 10, 9, 71, 71, 11, 67, 59, 7], [3, 20, 6, 20], [22, 5, 8, 10, 12, 29, 46, 11, 29, 9, 3, 7], [3, 20, 6, 20], [22, 5, 8, 10, 12, 29, 46, 11, 29, 9, 7], [20, 6, 20], [8, 6, 20, 6], [11, 18], [27, 33, 3, 7], [3, 66, 29, 10], [50, 81], [33, 6, 8, 11], [33, 11, 13, 46, 5, 11], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 66, 41, 48, 13, 8, 16, 45, 13, 3, 7], [3, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 40, 61, 34, 26, 75, 46, 29, 13, 3, 7], [3, 89, 78, 89], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 9, 24, 4, 29, 54, 37, 18, 83, 3, 7], [3, 15, 9, 18, 9, 41, 6, 20, 11, 10, 11], [11], [24, 19, 63], [33, 6, 20, 10, 29, 6], [35, 11, 29, 9, 8, 8, 11], [5, 20], [61, 12, 48, 9], [70], [68, 11, 27, 6, 18, 5, 32, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 82, 46, 26, 55, 61, 15, 16, 6], [48, 5, 11], [60, 63, 6, 12, 10, 12, 46, 9, 3, 7], [3, 68, 11, 27, 6, 18, 5, 7], [8, 33, 6, 20, 10, 29, 5], [22, 11, 48, 11, 20, 10, 5], [11, 22], [26, 55, 12, 5, 10, 11, 18, 5, 11], [90], [44, 18], [62, 11, 10, 10, 6], [65, 12, 6, 10, 5, 22, 5, 11, 20, 6], [15, 34], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 74, 34, 37, 38, 36, 58, 40, 33], [47, 41, 11, 10, 10, 6, 55, 12, 6, 10, 5, 22, 5, 11, 20, 6], [48, 5, 11], [60, 41, 11, 10, 10, 6, 55, 12, 6, 10, 5, 22, 5, 11, 20, 6, 3, 7], [3, 68, 11, 27, 6, 18, 5, 7], [8, 33, 6, 20, 10, 29, 5], [22, 11, 48, 11, 20, 10, 5], [11, 22], [26, 55, 12, 5, 10, 11, 18, 5, 11], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 74, 34, 37, 38, 36, 58, 40, 33, 3, 7], [3, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 77, 52, 39, 17, 13, 43, 12, 68, 3, 7], [3, 44, 18], [62, 12, 10, 12, 29, 6], [22, 9, 18], [20, 6, 8, 10, 29, 6], [43, 6, 20, 22, 6, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 65, 29, 38, 35, 55, 63, 33, 36], [48, 5, 11], [60, 63, 6, 12, 10, 12, 46, 9, 3, 7], [3, 60, 41, 5, 6, 29, 9, 22, 11, 13, 6, 29, 11], [43, 11], [8, 5, 7], [29, 9, 8, 10, 11], [8, 9, 13, 27, 29, 9], [12, 20, 11], [41, 9, 8, 10, 11], [29, 9, 18, 5, 21, 5, 6, 8, 11], [9], [27, 9, 29], [13, 9], [29, 9, 18, 5, 21, 5, 6, 20, 9], [56], [8, 5, 20, 6, 20, 5, 13, 6], [22, 5], [5, 21, 20, 6, 29, 11, 20, 71, 11, 32, 3, 7], [3, 15, 72, 9, 9, 10], [47, 62, 5, 29, 13, 11, 4, 11, 63, 3, 7], [3, 24, 10, 29, 11, 21, 9], [77, 24, 66, 30], [74, 11, 29, 46, 11, 29, 11], [8, 10, 11, 5], [11, 27, 27, 6, 8, 10, 6], [27, 9, 29], [25], [11, 20, 20, 5], [33, 6, 20], [18, 9], [27, 12, 20, 10, 11, 10, 9, 14], [60, 33, 11, 29, 13, 9, 18, 5, 10, 11, 22, 12, 29, 8, 6, 3, 7], [3, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 15, 62, 75, 26, 61, 11, 63, 4, 3, 7], [3, 15, 8, 12, 20, 11, 13, 5], [15, 6, 12, 29, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 9, 11, 65, 10, 41, 16, 12, 36], [48, 5, 11], [60, 63, 6, 12, 10, 12, 46, 9, 3, 7], [3, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 41, 65, 83, 53, 66, 39, 39, 74], [47, 10, 8, 12, 20, 11, 13, 5, 10, 6, 12, 29, 3, 7], [3, 52, 9, 29, 33, 16, 57, 69], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 55, 22, 83, 25, 61, 74, 16, 64, 3, 7], [3, 43, 6, 48, 5, 13, 9, 20, 10, 6], [58], [24, 10, 9, 18, 18, 9, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 37, 84, 61, 8, 64, 33, 18, 44, 84, 25], [48, 5, 11], [60, 63, 6, 12, 10, 12, 46, 9, 3, 7], [3, 52, 29, 9, 8, 5, 22, 9, 20, 10, 9], [22, 9, 18], [8, 9, 21, 21, 5, 6], [18, 11, 22, 29, 11, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 62, 21, 36, 81, 18, 9, 82, 40, 74, 75], [48, 5, 11], [60, 63, 6, 12, 10, 12, 46, 9, 3, 7], [3, 60, 46, 9, 27, 27, 9, 78, 21, 29, 5, 18, 18, 6], [24, 12, 46, 5, 10, 6], [33, 6, 20, 41, 18, 5, 10, 10, 6], [22, 5], [5, 20, 10, 9, 29, 9, 8, 8, 5], [33, 6, 20], [52, 4], [43, 37, 68, 15, 44], [9], [44, 68, 23, 38, 37, 44, 66], [9], [11, 46, 46, 11, 20, 22, 6, 20, 11, 29, 9], [18, 11], [10, 29, 11, 10, 10, 11, 10, 5, 48, 11], [11, 27, 27, 9, 20, 11], [33, 9, 29, 33, 11, 20, 6], [22, 5], [41, 11, 29, 9], [5], [41, 12, 29, 46, 5, 32, 3, 7], [3, 16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 40, 24, 81, 83, 66, 26, 74, 74, 64, 8, 3, 7], [3, 43, 58, 24], [62, 6, 18, 18, 5, 30], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 71, 38, 74, 58, 35, 72, 77, 84, 83, 28], [10, 29, 11, 13, 5, 10, 9], [60, 39, 6, 12, 15, 12, 46, 9, 3, 7], [3, 35, 37, 52, 66, 24, 44, 38], [9], [34, 44, 23, 44, 45, 66, 68, 54, 66], [38, 66, 44], [11, 18], [43, 6, 34, 5, 13, 9, 20, 10, 6], [58], [24, 10, 9, 18, 18, 9, 32, 42, 20, 45, 11], [48, 6, 18, 10, 11], [46, 12, 6, 20, 11], [33, 16, 9], [8, 33, 6, 27, 29, 5, 29, 9, 13, 6], [18, 11], [48, 9, 29, 5, 10, 86], [8, 12, 18, 18, 9], [8, 10, 29, 11, 21, 5, 69], [47, 13, 6, 48, 5, 13, 9, 20, 10, 6, 58, 8, 10, 9, 18, 18, 9, 3, 7], [3, 62, 11, 29, 8, 5], [27, 29, 9, 20, 22, 9, 29, 9], [22, 11, 18], [27, 11, 20, 5, 33, 6], [22, 11], [8, 6, 18, 5], [56], [33, 6, 13, 9], [29, 5, 22, 9, 29, 9], [22, 11], [8, 6, 18, 5], [5, 20], [12, 20, 11], [8, 10, 11, 20, 71, 11], [48, 12, 6, 10, 11, 32], [77, 20, 6], [8, 5], [8, 9, 20, 10, 9], [48, 9, 29, 11, 13, 9, 20, 10, 9], [8, 10, 12, 27, 5, 22, 6, 3, 7], [3, 9, 8, 8, 9, 29, 9], [13, 6, 22, 9, 18, 18, 9], [27, 29, 6, 10, 9, 8, 8, 5, 6, 20, 5, 8, 10, 9], [8, 5, 21, 20, 5, 41, 5, 33, 11], [48, 9, 20, 5, 29, 9], [27, 11, 21, 11, 10, 9], [27, 9, 29], [29, 9, 11, 21, 5, 29, 9], [5, 20], [13, 6, 22, 6], [9, 33, 33, 9, 8, 8, 5, 48, 6], [11], [33, 6, 8, 9], [33, 6, 13, 9], [29, 5, 8, 6], [8, 6, 41, 41, 5, 11, 10, 6], [9], [8, 33, 11, 29, 27, 9], [20, 12, 6, 48, 9, 3, 7], [3, 60, 46, 9, 27, 27, 9, 78, 21, 29, 5, 18, 18, 6], [], [48, 6, 10, 11, 10, 9], [33, 6, 20], [5, 18], [27, 22, 30], [33, 6, 20, 41, 18, 5, 10, 10, 6], [22, 5], [5, 20, 10, 9, 29, 9, 8, 8, 5, 7, 29, 9, 22, 22, 5, 10, 6], [22, 5], [33, 5, 10, 10, 11, 22, 5, 20, 11, 20, 71, 11, 7, 8, 6, 8, 10, 9, 21, 20, 6], [11, 18, 18, 11], [27, 5, 33, 33, 6, 18, 11], [9], [13, 9, 22, 5, 11], [5, 13, 27, 29, 9, 8, 11, 7, 41, 5, 20, 11, 20, 71, 5, 11, 13, 9, 20, 10, 6], [27, 11, 29, 10, 5, 10, 5, 3, 7], [3, 44, 18], [8, 6, 18, 6], [13, 6, 10, 5, 48, 6], [27, 9, 29], [33, 12, 5], [33, 16, 5, 9, 22, 5, 11, 13, 6], [11, 22], [11, 18, 10, 29, 9], [27, 9, 29, 8, 6, 20, 9], [33, 6, 13, 9], [56], [11, 20, 22, 11, 10, 6], [5, 18], [18, 6, 29, 6], [41, 5, 70, 20, 9], [8, 9, 10, 10, 5, 13, 11, 20, 11], [56], [27, 9, 29, 33, 16, 57], [33, 6, 8, 85], [21, 18, 5], [27, 6, 8, 8, 5, 11, 13, 6], [29, 11, 33, 33, 6, 20, 10, 11, 29, 9], [5, 18], [20, 6, 8, 10, 29, 6, 3, 7], [3, 68, 6, 20], [48, 6, 21, 18, 5, 6], [48, 9, 18, 18, 9, 5, 10, 11, 29, 5, 9], [13, 9, 8, 33, 6, 18, 11, 20, 71, 9], [33, 6, 20], [20, 9, 8, 8, 12, 20, 6], [20, 9, 13, 13, 9, 20, 6], [27, 5, 79], [33, 6, 20], [48, 6, 5, 7], [13, 11], [20, 6, 20], [8, 6, 27, 27, 6, 29, 10, 6], [20, 9, 11, 20, 33, 16, 9], [18, 11], [18, 9, 21, 21, 9], [22, 5, 18, 11, 21, 11, 20, 10, 9], [22, 9, 18], [41, 11, 10, 10, 5], [5], [33, 11, 71, 71, 5], [10, 12, 6, 5, 3, 7], [59, 60, 43, 11, 10, 10, 5, 11, 52, 11, 8, 5, 20, 5], [44], [27, 29, 9, 71, 71, 5], [22, 9, 18, 18, 11], [46, 9, 20, 71, 5, 20, 11], [8, 6, 20, 6], [18, 11], [27, 12, 20, 10, 11], [22, 9, 18, 18, 3, 5, 33, 9, 46, 9, 29, 21, 7], [11, 20, 22, 11, 29, 8, 9, 20, 9], [27, 9, 29], [55, 12, 9, 18, 18, 6], [56], [10, 5, 27, 5, 33, 6], [22, 11], [5, 10, 11, 18, 5, 11, 20, 6], [13, 9, 22, 5, 6, 59, 7], [3, 60, 43, 6, 48, 58, 24, 10, 9, 18, 18, 9], [30, 67, 3, 7], [3, 44], [55, 12, 5, 71], [5, 20], [10, 48], [8, 20], [8, 10, 12, 22, 5, 11, 10, 5], [27, 9, 29], [41, 11, 29, 33, 5], [8, 9, 20, 10, 5, 29, 9], [11], [20, 6, 8, 10, 29, 6], [11, 21, 5, 6], [5, 20], [55, 12, 9, 5], [41, 11, 10, 10, 5], [33, 11, 8, 12, 11, 18, 5], [9], [5, 20, 12, 10, 5, 18, 5], [33, 16, 9, 8, 20], [10, 10], [55, 12, 9, 18], [33, 16, 9], [33, 5], [29, 5, 13, 11, 20, 9], [22, 9, 18, 18, 11], [20, 6, 8, 10, 29, 11], [5, 8, 10, 29, 12, 71, 5, 6, 20, 9, 3, 7], [59, 65, 12, 11, 20, 22, 3, 56], [33, 16, 9], [5, 18], [41, 12, 10, 12, 29, 6], [56], [27, 11, 8, 8, 11, 10, 6], [22, 11, 18, 18, 3, 9, 8, 8, 9, 29, 9], [12, 20, 11], [27, 29, 6, 13, 9, 8, 8, 11], [11], [9, 8, 8, 9, 29, 9], [12, 20, 11], [13, 5, 20, 11, 33, 33, 5, 11, 69, 59, 7], [3, 60, 27, 11, 6, 13, 5, 6, 50, 82], [60, 46, 9, 27, 27, 9, 78, 21, 29, 5, 18, 18, 6], [56], [6, 48, 48, 5, 6], [33, 16, 9], [8, 10, 9, 8, 8, 9], [27, 11, 29, 18, 11, 20, 22, 6], [22, 9, 5], [22, 12, 9], [74], [88, 46, 9, 29, 8, 11, 20, 5], [46, 9, 29, 18, 12, 8, 33, 6, 20, 5, 67], [83, 4, 3, 7], [3, 60, 46, 9, 27, 27, 9, 78, 21, 29, 5, 18, 18, 6], [60, 13, 6, 48, 5, 13, 9, 20, 10, 58, 8, 10, 9, 18, 18, 9], [60, 46, 63, 6, 46, 18, 12], [60, 21, 20, 6, 13, 11, 50, 53, 81, 81, 42, 20], [11, 18, 18, 11], [41, 5, 20, 9], [34, 5, 6, 18, 11], [15, 9, 8, 5], [56], [33, 6, 18, 18, 9, 21, 11, 10, 11], [5, 20], [55, 12, 11, 18, 33, 16, 9], [13, 6, 22, 6], [11], [33, 16, 5], [48, 6, 18, 9, 48, 11], [41, 29, 9, 21, 11, 29, 9], [5, 18], [8, 5, 13, 46, 6, 18, 6], [13, 58, 8, 69, 3, 7], [3, 45, 11], [8, 10, 6, 29, 5, 11], [20, 6, 20], [10, 5, 9, 20, 9], [33, 6, 20, 10, 6], [43, 66, 44], [22, 9, 18], [33, 6, 29, 11, 21, 21, 5, 6, 32, 3, 7], [3, 47, 75, 11, 27, 27, 63, 74, 5, 29, 10, 16, 22, 11, 63, 61, 12, 8, 10, 5, 20, 62, 29, 6, 13, 44, 10, 11, 18, 63], [16, 10, 10, 27, 30, 31, 31, 10, 32, 33, 6, 31, 64, 5, 63, 9, 71, 18, 43, 16, 53, 74, 3, 7], [3, 47, 29, 10], [47, 6, 12, 6], [8, 9, 21, 12, 5, 13, 5], [9], [10, 5], [8, 9, 21, 12, 6, 7], [20, 6, 20], [12, 20, 41, 6, 18, 18, 6, 72, 6, 32, 3, 7], [59, 43, 11], [33, 16, 9], [41, 11, 33, 33, 5, 6, 20, 9], [22, 11], [46, 11, 13, 46, 5, 20, 6], [33, 16, 9], [33, 3, 16, 11], [4, 9], [23, 29, 9, 21, 6, 29, 5, 6, 7], [33, 6, 20], [55, 12, 9, 18, 18, 3, 9, 8, 27, 29, 9, 8, 8, 5, 6, 20, 9], [22, 11], [33, 12, 33, 33, 5, 6, 18, 6, 7], [10, 9, 20, 10, 11], [22, 5], [41, 11, 29, 9], [18, 11], [48, 5, 10, 10, 5, 13, 11, 32, 32, 32], [5, 20], [21, 11, 18, 9, 29, 11], [33, 6, 20], [5, 18], [27, 11, 22, 29, 6, 20, 9, 14, 14, 14, 59, 7], [3, 60, 66, 22, 29, 5, 11, 20, 6, 78, 52, 11, 18, 6, 71, 71, 5], [13, 11], [27, 9, 29], [41, 11, 48, 6, 29, 9, 7], [11, 16, 11, 16, 11, 16, 11, 16, 11, 16, 11, 3, 7], [3, 60, 12, 46, 11, 18, 22, 6, 27, 11, 20, 10, 11, 20, 5], [21, 29, 11, 20, 22, 9], [30, 4, 3, 7], [3, 60, 5, 18, 27, 22, 18], [55, 20, 22], [48, 5, 20, 33, 9, 59, 44], [13, 11, 21, 5, 8, 10, 29, 11, 10, 5], [20, 6, 20], [48, 6, 21, 18, 5, 6, 20, 6], [41, 11, 29, 33, 5], [21, 6, 48, 9, 29, 20, 11, 29, 9, 59, 55, 20, 22], [27, 9, 29, 22, 9, 59, 44], [13, 11, 21, 5, 8, 10, 29, 11, 10, 5], [20, 6, 20], [48, 6, 21, 18, 5, 6, 20, 6], [41, 11, 29, 33, 5], [41, 11, 29, 9], [6, 27, 27, 6, 8, 5, 71, 5, 6, 20, 9, 59, 60, 46, 9, 27, 27, 9, 78, 21, 29, 5, 18, 18, 6], [33, 6, 13, 5, 33, 6, 69, 3, 7], [3, 60, 74, 18, 12, 9, 68, 11, 48, 5, 21, 11, 10, 5, 6, 20], [60, 43, 6, 48, 58, 24, 10, 9, 18, 18, 9], [33, 29, 9, 22, 6, 20]]]

















In [33]:



    


def pad_words(tensor_words, max_word_len, pad_symbol_id, max_sent_len=None):
    """
    pad character list all to same word length
    """
    padded = []
    for words in tensor_words:
        if max_sent_len: #pad all to same sentence length (insert empty word list)
            words = [[[0]]*(max_sent_len-len(words))+ words][0] #prepending empty words
        padded.append(sequence.pad_sequences(words, maxlen=max_word_len, value=pad_symbol_id))
    return np.array(padded)



    











In [34]:



    


X_train_pad_char = pad_words(X_train_num, max_word_length, 0, max_sent_len=max_sentence_length)
X_dev_pad_char = pad_words(X_dev_num, max_word_length, 0, max_sent_len=max_sentence_length)
X_test_pad_char = pad_words(X_test_num, max_word_length, 0, max_sent_len=max_sentence_length)



    











In [35]:



    


X_train_pad_char.shape



    


















    
Out[35]:








(57, 893, 139)

















In [108]:



    


from keras.models import Model, Sequential
from keras.layers import Dense, Input, GRU, TimeDistributed, Embedding, Bidirectional
import keras

Composing words only out of characters

Instead of using a separate word embedding matrix, compose words through characters (see https://aclweb.org/anthology/W/W16/W16-4303.pdf)





In [60]:



    


batch_size=8
max_chars = len(c2i)
c_dim=50
c_h_dim=32
w_h_dim=32
char_vocab_size = len(c2i)

## lower-level character LSTM
input_chars = Input(shape=(max_sentence_length, max_word_length), name='main_input')

embedded_chars = TimeDistributed(Embedding(char_vocab_size, c_dim,
                                         input_length=max_word_length), name='char_embedding')(input_chars)
char_lstm = TimeDistributed(Bidirectional(GRU(c_h_dim)), name='GRU_on_char')(embedded_chars)

word_lstm_from_char = Bidirectional(GRU(w_h_dim), name='GRU_on_words')(char_lstm)

# And add a prediction node on top
predictions = Dense(1, activation='relu', name='output_layer')(word_lstm_from_char)



    











In [61]:



    


model = Model(inputs=input_chars, outputs=predictions)


model.compile(loss='binary_crossentropy', optimizer='adam',
                      metrics=['accuracy'])

model.summary()



    


















    






_________________________________________________________________
Layer (type)                 Output Shape              Param #   
=================================================================
main_input (InputLayer)      (None, 893, 139)          0         
_________________________________________________________________
char_embedding (TimeDistribu (None, 893, 139, 50)      32900     
_________________________________________________________________
GRU_on_char (TimeDistributed (None, 893, 64)           15936     
_________________________________________________________________
GRU_on_words (Bidirectional) (None, 64)                18624     
_________________________________________________________________
output_layer (Dense)         (None, 1)                 65        
=================================================================
Total params: 67,525
Trainable params: 67,525
Non-trainable params: 0
_________________________________________________________________

















In [66]:



    


from IPython.display import SVG
from keras.utils.vis_utils import model_to_dot, plot_model

plot_model(model, to_file='model.png')
SVG(model_to_dot(model).create(prog='dot', format='svg'))



    


















    
Out[66]:








G



140581090833856

main_input: InputLayer



140581090396256

char_embedding(embedding_5): TimeDistributed(Embedding)



140581090833856->140581090396256





140581090488272

GRU_on_char(bidirectional_5): TimeDistributed(Bidirectional)



140581090396256->140581090488272





140581087596496

GRU_on_words(gru_7): Bidirectional(GRU)



140581090488272->140581087596496





140581090558024

output_layer: Dense



140581087596496->140581090558024





















In [48]:



    


model.fit(X_train_pad_char, y_train_num, epochs=10, batch_size=8)



    


















    






Epoch 1/10
57/57 [==============================] - 98s - loss: 8.7660 - acc: 0.4561    
Epoch 2/10
57/57 [==============================] - 98s - loss: 8.7660 - acc: 0.4561    
Epoch 3/10
57/57 [==============================] - 98s - loss: 8.7660 - acc: 0.4561    
Epoch 4/10
57/57 [==============================] - 98s - loss: 8.7660 - acc: 0.4561    
Epoch 5/10
57/57 [==============================] - 98s - loss: 8.7660 - acc: 0.4561    
Epoch 6/10
57/57 [==============================] - 99s - loss: 8.7660 - acc: 0.4561    
Epoch 7/10
57/57 [==============================] - 99s - loss: 8.7660 - acc: 0.4561    
Epoch 8/10
57/57 [==============================] - 99s - loss: 8.7660 - acc: 0.4561    
Epoch 9/10
57/57 [==============================] - 99s - loss: 8.7660 - acc: 0.4561    
Epoch 10/10
57/57 [==============================] - 99s - loss: 8.7660 - acc: 0.4561    










    
Out[48]:








<keras.callbacks.History at 0x7fdd504c9b00>

















In [49]:



    


loss, accuracy = model.evaluate(X_dev_pad_char, y_dev_num)



    


















    






15/15 [==============================] - 9s

















In [42]:



    


print(accuracy)



    


















    






0.40000000596

















In [50]:



    


loss, accuracy = model.evaluate(X_test_pad_char, y_test_num)



    


















    






18/18 [==============================] - 11s

















In [51]:



    


print(accuracy)



    


















    






0.666666686535

Conclusions

The model did not learn anything at all: the performance reflects the label distribution in the test set. When trained with enough data, the SVM can learn and solve to some extent the problem. The neural model needs a lot more data.

Content source: anbasile/perspred

Similar notebooks:

notebook.community | gallery | about