P16812 [HackerEarth] Learning about all the sinusoidal functions of trigonometry, Rahul has grown fond of numbers, whose digits increase and decrease alternatively.
提高
题目描述

Learning about all the sinusoidal functions of trigonometry, Rahul has grown fond of numbers, whose digits increase and decrease alternatively.

Let's call d[i] is the i^th digit of a number d. Formally, a wavy number is defined as a number d such that either d[0] < d[1] > d[2] ... or d[0] > d[1] < d[2] ...

Given a number N, can you find the integers L and R such that the range [L, N] and [N, R] each contain exactly K wavy numbers. Also, these ranges should be as large as possible.

Note that if no L ≥ 1 is found or the required value of R exceeds 10^18, you should output -1.

Input:
The first line of input file contains T, the number of test cases to follow.
Each of the following T lines contain two space-separated integers N and K.

Output:
Output exactly T lines, each containing two integers L and R sepated by a single space.

Constraints:
1 ≤ T ≤ 625
1 ≤ K, N ≤ 10^18

SAMPLE INPUT
2
9 2
2 3

SAMPLE OUTPUT
8 11
-1 4

Explanation

Case 1:
[8, 9] has 2 wavy numbers 8 and 9.
[9, 11] has 2 wavy numbers 8 and 10. Note that [9, 10] also has 2 wavy numbers but its size is not maximal.

Case 2:
Note that for no value of L ≥ 1 we can have a range that has 3 wavy numbers and the range ends at 2. So, value of L is -1. R is simply 4 as [2, 4] contains 3 wavy numbers 2, 3 and 4.

输入格式

见题面

输出格式

见题面

样例输入
25 91278 3085 85996 20531 77348 7418 92582 11129 92647 1856 89403 2824 85116 4469 68209 17305 76400 17421 80467 208 77848 26812 97158 9627 97309 7290 89596 6796 87085 11865 93992 1263 95397 9361 70846 1259 86204 900 94247 22952 59361 8704 99698 10842 96056 6188 64942 11015 89029 784
样例输出
715010319192824388 725484745380307142 436043749243849675 439561624051313271 916465817693703281 967080535270903251 595736380815265836 638260734054806449 946131408463967392 959591857371527093 902065618021609383 924070926490736020 729272917343615262 783848397806271846 518382549674958586 560315284856164703 845063849680438683 893703253616376947 828686836190508255 890435120807171818 849163506561627355 896907032646350607 867353513093837276 967354856354948794 934272968150618387 -1 381516493424290725 419052906594524171 793706481209271805 868073813130727574 808290858781956299 816021848671738239 596737065906162858 694536341706580915 847261505341649293 904087934010848481 948196729164826195 -1 869571839373867276 902070327193709462 694548080616481327 807495623190618492 867675718492728261 909392835162908464 694506480717064715 696746492634150800 908076818580719274 979373826590738670 686907050207096906 805142416161417275 293748153707173759 306251846292826240 690327592619460720 818082709142404272 929580737240419385 -1 895829151214291302 968351658292439691 958585878690315044 -1 605151615061947376 724080956084518253 836252638151628561 918271602180759285 734275604065808797 807463948180549391 563605061804395709 571978693947241538 969162802120867399 -1 907154945382837131 -1 937692914391634366 -1 869896736063915164 968150526170838784 838061219680513072 -1 436452927583935251 535171539561825182 725450819187936392 805374624391538193 848040528095619282 903051626395967453 783702181305350508 795709294835093512 717142838254869398 728053436092659385 958295616080646295 968385656294978092 428341819260757454 462419462314143411 845250938482747263 913176817093857461 791656042918250740 808343957081749259 927075609490506375 -1 819571539162767594 848780836580938030 939097839271913272 -1 949153439093867088 956575805291314339 959154627190439251 -1 949676937283515154 -1 826121809241804272 867284945352409675 908043636364937574 928794536095819152 737374639890428287 958032714175645286 809792515130847492 817473538453834095 593437390719490746 617241626482928696 968040829392503094 979796938364847164 929053427180307098 -1 891406287867561209 -1 767372767564746052 782627232435253947 786948387878394906 805140749164834274 904142805143909195 906396717091429561 814364826191956231 -1 787828463638353747 935391819451537452 570416341407292616 581819781816293411 916374745181639785 927240719343937296 690824360629376959 813191707274726231 967265868452747365 989280628571436089 780769694929384924 946242934041406394 706354714393769781 792919043719143835 812062424353957454 912161734171625491 581415251918032725 657572948580219071 816143714264602083 938381704121802182 946042505361637376 978390429051529172 671219572547292908 681657570749561526 848083935073419287 878152857271517051 846042618383539799 890716391434132300 868187918170615091 879484618141728689 869690935372759373 892409382424085834 767380506172917021 968342425142737590 878240716343845455 -1 939583425494813183 -1 829354869490948051 916280548680604269 949490925492918074 -1 836593738163768088 845240958161749689 798969461518293739 956184818054709179 827390808585649233 925076823073625270 925282435280807163 -1 890302053517480508 918462649032736129 834386929353427233 837020603096718792 896989153503093629 907351657573746570 767191548151216255 782808451848783744 814265826032868677 892549285905031613 848041914392306153 -1 967072302063638684 989592709043946120 696739465908085839 703050903194827389 938592438074534343 -1 896937184659565857 903062815340434142 979473648374857043 -1 836362614292329472 892814270719060506 924121407670727585 -1 759190818580809795 783909082989040524 707572837151738051 748150517163424050 897949496728382969 -1 829560707098967242 869165949380408090 892303231326282924 958375724371538049 782517093507596960 826072806184859391 728182956180409354 736231808180658369 959010707094518396 -1 659891408092605493 685906394716360655 670768191639095908 734193969053867394 879560605273756476 -1 909172734281708797 -1 726576848460913131 804281526351416193 968196978021635254 979474525490719130 769340105352828296 856173916384729230 713083748260925052 729681919280326263 869670548687978473 878095619597858693 869680829586805085 968231728584849779 847090723295846242 891756192506392915 767562928263718682 879196945175847181 879481728291547341 -1 892416087856396840 893957271814273501 659273639690906594 684647062404182833 816074835476804295 948090838171307270 695606250316470214 749476738572738183 747140109170725084 834391407164624381 819098917351726272 878161539692712151 803251516184945492 824284724020204191 671978076928363605 672809342946174518 849350758287812162 879253626341704262 938093749393416063 947164548584878362 808484827165759575 815351709152709269 628161939670608343 637574516053706481 935461219585816262 -1 967470827576968041 -1 693429791219791760 706281317283627280 979494701060909496 -1 825261818371517085 928462835294929892 957032945486969461 -1 617264913297917153 746495747494823029 894658484928372750 958010747083834169 946490879452912144 -1 646583904241406464 659142634074506189 802040309131858186 948260328096824273 538580647694756383 574738275809140968 867194745054723187 918453609892609570 694968061315190826 748271418041619471 735230936451747577 849575826141604353 363808780509682719 371806073947474634 869495959171329231 925192705194525459 808084647360807297 915494503198906449 892302153756230736 928464657582706186 827394515097827671 859121403132649252 784939262839461710 -1 867175929262637575 895656475723261968 909250816261509671 914342819373802064 607560329093537691 671516283936030315 560318173858096859 616370403021706296 919082717452435452 924163528080548253 690923161958360219 759042647190917564 243739295857180209 252645162707060824 959781517584957466 989895807176927251 814043429285739486 945080609594868790 937182635262736066 -1 913130709192735284 957374612180838097 927032637352309171 959563547252857572 919193536565959452 928231219132408380 926354618672958474 949687837175845071 739083614360906374 890539343928272500 947231505281718363 -1 890436080439251508 -1 798909681926098914 823250407460726372 805163707270403191 839295627170545284 918230517571813164 947371768274729461 856292713262815185 894818052607353405 745271713061818199 828572318591812020 946585956597814097 979362538042624030 918380546563614172 947192407121217184 890103285625380604 909896714374619395 939052989793836465 -1 867394707240639187 959187813040534342 928282914232817682 935093727180205264 808781508290979251 927171703193635353 956273813121715073 -1 927263427140425492 959262747384948164 938072328271518576 -1 814290903196907084 895608272725262544 838592825121409292 -1 827381437132505475 868121927690748142 804296813132905062 848342734040747696 956465609073908499 -1 859691947494937252 867073437252858273 935395906342757231 -1 959891437183425291 -1 969480438560909343 -1 639353546491609044 645343604092638139 949020524376867096 -1 905260709141704241 919585938376809672 848685716261506344 947476929471526170 680208393618243709 729041817173804370 869681868184817577 892418473417491645 836090326393947461 903261969381508175 716040535192319031 814370879075925391 726152918296924199 747163507291616369 968574768591518194 979153919898957679 827254857684501087 926596947154505079 947596908450856033 -1 848141859362406474 908162947130709190 902185858141946496 937080217694548361 958051829274619594 -1 945020709142428121 949071945271768141 485709282717151430 490217482945173645 928192979792726272 -1 637061658460835282 690737561969073808 627391527132527452 690219198924296804 694859392429560608 704296924240615160 818132715381934181 917471857061847379 638181819191916487 724041436154828173 891623292869492625 915232829891416391 757565756490827393 909161428243758470 909251308694829091 935132946580325081 793736173639393414 968393908197926570 786905083418174930 790639353957143417 637121614396749799 648154845262719252 624263427285739064 827152738572416186 917380512085745292 949381506181734170 574529385935292637 574659083904095626 949284529891217076 -1 680529784729031416 717397807673948361 856181708691923282 868280716353438152 781816364735263718 925482317481216270 917352968140839363 -1 847140718351408354 -1 580403010717020110 745151618486958094 908690929175858577 958180546191625186 929053638130649275 -1 956162738781315154 -1 893959232917140940 -1 809686868080215391 937021957243706194 780109191429063603 968064816275907070 809370945163417463 823272508143505197 838121807352718285 916392418270907395 693658481537130435 706341518462869564 614340938692967342 637353858363846172 756376958132646232 827151605131524262 957380929284628151 -1 658695828372749197 690825083958143948 757040435231209033 836573426395636581 834275814292545498 892527091859485735 827081839361517372 918791747362327051 891937241401040547 926260634182318261 547161616586847263 562838383413152736 893756021817061824 928674913063628690 847340945082545353 937363402094706070 949072549490708022 -1 896908181215031407 -1 879190706050758352 890809293949241647 781634395904180516 845031869352537281 949094548450835342 -1 639484718494904064 683417393623098968 968052935091617099 -1 769692926042816064 879343727053809370 394989792539692926 418495823132738391 637383419897838061 647498907381728797 923132937463416366 948351919485809242 807282616580419122 835120605280925091 718031749690515133 878030535283915172 825270658372906341 895946452423240326 937252758781949197 978253809684646262 816496808387949266 849020205450726139 757561838231725132 828131909783769394 785636094804175702 837385626091409173 979370508472658372 -1 947163745165934073 -1 383824064539163404 409172648360814371 948795619240758083 957120549274505082 819685829575617081 845390545076745071 818150109394529495 917462838281908274 792979042618593548 849896809570818793 808450502161429381 905090967270725491 935270626173729782 957162815194706142 745184659490317075 845093768280923070 867140608580406084 -1 849594516370418052 -1 825390216170846481 867570927371905372 372723287928061329 383539490504140600 896803280737480217 949592857161506396 924092407496838682 939672946162717361 808362937120403042 837364549380829271 939483613051709141 -1 916050918090617599 949481826075718009 914184759051945152 989260917290327271 768780309164917266 826143879684524294 927390307030318383 -1 856597835375812041 948594637283978483 706252878591607192 807680107561426129 928154523230649581 -1 837286837492626196 896808173856043714 907295809471958071 -1 897819353607492404 979582327265904094 804380817141309585 823163514390929793 905461828382407273 -1 748780416186945044 757051806262648481 628152906342413253 768596947574536163 929382436240835171 936191768780107191 938130219481703161 -1 680607492516342539 735495967142608361 928694657482908682 -1 847454726174836199 959593806587968169 937382639698947677 957171206162657559 878591549272608566 -1 793946176824392926 891837354519570617 857453708287857452 949594824160408680 967591817180967472 -1 839472849071615033 845230735242648392 592658594959450509 629673545370907579 487939092626042637 508073946171738696 708286867270612121 768793526371706096 918462326382605244 -1 835390735186936151 896757570304341403 908370308164956041 959392749020707453 759792718190416276 817585602091429251 814376814290704085 856340318260818593 935094506471949199 -1 824252929290609086 924286856093504072 704170509781218797 827083759470768159 793803183428192629 806463909241618681 818143616174812091 905464858581937586 968481819131848184 979192414120538053 807582934010439074 867172757352814380 859160639190825463 -1 628292308281705143 681639075939073828 798959290417152760 817295626350825381 905493726581506393 978692629483638592 792416370539675860 802171834185802195 959230214143438277 -1 856395812152535494 928284705471904251 686815176917051526 845042636083709094 847373439193846296 903285829041728383 758054719562936283 785817260501020815 781909683839682713 834394849391838362 627685834063819174 670545360508182306 769286718131937188 780713281868062811 635097816463735096 649596848270647493 857353769797835098 934343625280948061 340906383424354818 372548160737276846 927181645292507065 -1 781879586978290107 907180905343805364 905173747241607285 -1 829453817686834281 924050217243989694 859694867580102088 936560639284614084 629483548570318341 680716451429681658 848372909493614072 858194518286817195 848142706050635341 890749342435363644 727585825392604252 829784856260509292 564839291436561920 607163717471709349 782859796856131546 815254989387925353 895979592425081306 -1 605394914385978344 646040729562425151 739464639191956181 796969565739196913 915162618041209797 -1 834360423132635497 856073647565939262 845284879583839497 -1 592406092707560837 605294936141806192 735084756563406065 894601010307092308 526493837684758482 561989170989370511 918263746483428454 937586736386728783 834380879161848051 890605474508783437 917574647041512055 926181929064527189 938582858784539571 -1 829341808460549595 895709042438576937 906092717297906287 -1 795919462549276702 869275747362824053 917471968372615277 -1 539381706263537143 607284869241539473 837575945052707465 869792312051813131 924096835073809099 939597828391539494 712064506098923061 759194908365726050 576705231824292314 748395629152625462 928194948075827574 969595603252509596 926230938292727396 -1 629121517073847251 692839064805265988 392429287924192548 403174846065613184 564637291723285919 645484602172824262 826062937081739488 919676718182636139 646071819274908264 681879380326492412 847021845490869294 934051425492658560 909690829471648191 934281726282426231 867191813173969183 890737251848691634 767340979494527153 857075879171206493 513180927154917098 564527570612042918 797817393601051216 937451413040657697 716086815161419173 791416343813252655 838152823171318573 916374704261529060 927565608365919475 959030968274848780 816251636274879355 927143916383967491 781917374919784937 834390727264769597 907351658061405366 918064523171658572 958064935032718798 968797816094956189 929243916064869893 -1 937592729580549472 -1 909074629060509584 946370328186837593 657350436372426173 726020318375647681 812195634131978796 859494946362959052 836351929121738372 939280425064624381 626593403231747162 695758262758070734 607150758380817166 608465727271617492 947164708260835355 -1 708284505073412143 723183967582869484 918371767470734366 -1 915020819793427198 -1 739263638174939291 891824073835161415 725195609197925282 768081438031909185 691867452936464527 814294867284629062 782768180838162909 784729121749290756 969097845021319786 -1 917260847150928232 -1 896903281919792769 928395626093937049 746121528396916198 759593912130608275 769492615275823199 826261835092319050 907041205161524275 938062434272919672 734363516271958385 794656453823042837 816572418590839285 890708794647454618 957493759587827385 -1 373726265713195737 384648571938031426 816342536581419376 828394829490604070 879893967494505492 -1 904385835382914276 -1 590758150829242528 596717473945495945 929460217564802055 -1 946281727680909072 959381656561979780 856460867282937088 905194634010807495 829263518194735084 834395804372506561 792814292939281740 856181925490947253 856561213140609394 894623060418350203 927132424132545066 -1 890926160615465728 938793747242959290 946193419797905031 -1 562514052728796927 637485947271203072 867091628797856141 -1 906070727354649593 908230209498924062 924063969364606095 968797959794738286 907364618097979288 946362635381756090 895738052616040617 -1 808786829681989296 859141924281949150 928383745465725296 -1 879162537352509098 905250645460856271 737291715063428452 747583805262416059 909453419597905063 978251909590418786 792705397956272324 893438360216351736 848197819294715142 947471527241418694 890507390405020769 958670537161607597 682307096718240315 768084856183438086 786948680725460969 829565718671407269 935354913053948392 -1 946371868152819575 -1 836051524065619295 -1 927564924031659585 -1 805153916271329372 819021749790304264 948292639065768453 989260818580734362 646231925294805477 695918153703170856 702063909793769099 759194819060537360 836370519376935295 915141549893959269 647030735363905377 687912010719674925 909054539793957386 -1 978061838042917385 -1 902083416582659688 927043917373626561 856392415120624094 896947041659293607 415151616254549055 419281839273845369 739561545342548381 768232868473836341 839020525384916173 846171979373507693 739091429391618594 801020424152312039 837684817475835296 869673618150318363 574867193645021880 706196804273425449 792727182847290528 856162826232989292 659461646093838373 697903182713062303 681839380716452718 780429353739396837 956385848041989297 -1 906132945087807296 -1 824252767470417261 897848360959153627 645292913071439366 675767173978692927 682868171309693858 693626362824230804 526141316051867164 560209395836051836 892757297879161946 967176707560737683 917191209042713296 -1 916353646296716387 927373409471905386 827581328781929396 949164819183429494 903251923162835083 945283819574708185 815261313163636455 -1 919043845382824133 978360106593646040 814021806253427251 958190629096938153 590319570407390917 691616585906092436 914280505473989673 929072725186704142 907185715163718686 937494826354646569 948781519294929241 -1 891925260726287946 -1 828680814097859796 -1 819371418051836385 926265649285808681 749561327364846233 816121648461627374 813281415475968575 904093936191818689 535140957484815499 537250737562813019 827385707593429781 837080659150978092 905164602183979244 937250928340607086 908053989040835233 -1 979492647361747084 979792959695938595 937274527298946061 -1 902194937054707096 968681516293535053 759021814380638281 868364957090219584 628780501065815133 769690748587878290 847460615142909261 858343978683923279 848484546471609781 904383845053907572 716373537495703165 749140417476819162 738061309363425451 791537242828462811 947354801030919395 958450825251929091 908382629394837672 969261717696758294 782409171725180968 907020714172607342 959082719473738587 967682915163709096 729795969792767476 734041416460858789 535484958796948052 573615041203051947 817173645093909172 937280726450209297 352746010423181538 407287929074824090 628171949472928287 693868395657194724 698916595718487906 781638674509053411 868796945381867297 917192309381517019 548683724081628092 591409793839042634 768242967683659298 848385703180109384 927454958184947072 969281847490907562 718272906460606564 745042956141429162 784989362805151706 903183724054915280 848183412082708675 890714241905391600 838275658491913065 916242957690639494 904340108474704132 -1 936464969496716396 -1 919485847273737698 -1 947131627583816399 -1 868194928052645354 946060649251407294 757464856052868681 769241435494857362 934385904164725374 -1 924192949481409033 -1 609683828060949122 636050706460907092 607695605290538394 681527342401042744 694905151647575827 703175867676869469 949232767260837121 -1 572759590429280914 583508020979590306 716053416231827477 728065703276978296 818060869163549074 847584806160809453 917392427173936363 -1 949187928174868384 -1 839454601072539686 868132806040807239 892915040949393620 -1 561326484818151807 565846352324074737 757092819798929491 787827681616287913 908353607472326063 -1 692305187956252959 834362657290959251 769272978670704182 848143749140967491 767673759393435096 782326240606564903 615495827693536177 645175918374846271 896767231324141307 903020716192846063 838680804160868244 -1 938393835152439496 -1 503032439391607152 507493615362769159 793545086907496836 827290539783436029 879561509286879052 906371879570426370 806161747584757475 945354513194707175 946185908580526285 957231607092617494 746298936454706375 809141318670428691 892914351628043626 913151878780939082 591714297807060836 594537132537070513 749150938280724185 814263905383749897 879385768250109562 949242714291637080 928131408176715488 -1 937490406275905165 -1 968082838281979341 -1 769031908095747183 918461401020616386 893402170834192305 -1 878194912095624351 890909893915050214 908480658254606382 -1 587837475913081327 685909231812093977 792605175908482869 828241619360507450 739482947281537474 756293825363847264 463905095746561415 536342529152319896 675606573936493714 838691818151606379 890105380326481827 905232426395935274 767153957086969472 806131968290437573 767196935281828366 794769375837181415 792616053759680736 856380935470802181 704043813072704351 719094504073848585 797978486902098910 827353429151738170 916482316240603091 -1 849583739190439074 924342949186817681 948363419385767032 -1 957680423020805375 -1 927153538165827387 959375726163517453 759154945231804177 792636197968364713 838591525362907386 859251537453657062 719121536054806085 746381515282979394 726570715062639161 791519063658671747 729684847581534387 826561927074523153 780658785907380207 927182818382512175 603264645192418693 723291936010615394 937251319495617183 938375707273846152 825194715254947242 913090837052425297 835150858564519097 838290534373605290 904165816263615198 918783527170706042 481215473939072839 573917398908270202 989270803154809285 -1 846483737581427243 909360928680937495 670209380927276703 686947587818790424 890703063734394748 947274836352606264 928460858462319387 -1 926052619250208796 -1 596868175803140546 609354517482748790 849395826462836387 906394728374858252 978181978453858086 -1 748094818381219792 809150837676829394 768232878091506161 795729272708250900 935480846070956293 -1 795716121537492950 809082314163501091 729191929083435298 828361507180627175 859890326472918371 917694903232708349 919076813142618166 978286712196968283