favorite We need a little bit of your help to keep things running, click on this banner to learn more

Summer School 2011 in Sevastopol, Day 3


Consider aset of stringsconsisting only ofdecimaldigits, orletters of the alphabetof both registers.Two lineswill be assumedto be similar ifthey have the samelength and, in addition,at the samepositionsarethe symbolsof the samecategory, provided thatsuch categorieshave3 -all digits,lettersandsmallletterscaseof a largeregister.

For eachset consisting ofsomething like that,is introducedto subtract.We orderall thelines likethisin the lexicographicorder, thennumber them, startingfrom scratch.The result ofsubtractionfrom lineAlineBwill assumea certainline ofC,satisfying:

N(C)=(N(A)-N(B)) mod M,

where M -total number of lineslikethis, N(A), N(B)andN(C) -respectivelythe row numbersA, B andC, and themodoperationiscommonsensein mathematics- that is,is the smallestnon-negativenumber to besubtracted fromthe second operand,so that it becomesa multiple ofthe first.


The firstlineof input containsA, andsecond -containsB. It is guaranteed thatA and Bare similar, andtheirlengthis at least 1and no more than500000.


In the outputa single line- the answerof the problem(C).

Time limit 1 second
Memory limit 64 MiB
Input example #1
Output example #1