题目描述
Anurag is a good boy. He studies at IIT Kharagpur, where a person's capabilities are measured on two scales
CGPA : academic performance, denoted by C
Studapa: coolness/popularity, denoted by S
There are N challenges that one can face at IIT Kharagpur. To pass a challenge i one needs to have C ≥ ReqC[i] OR S ≥ ReqS[i]. Completing a challenge does not decrease the capabilities. In fact, P[i] spare points are awarded on completion of challenge i . Spare points can be used to boost the capabilities in any manner.
For example if Anurag wants to use 5 spare points then he can use it to increase his his C by 0 and S by 5 or, C by 1 and S by 4 or, C by 2 and S by 3, and so on. Even though spare points can be used at any time, once used, the spare points cannot be gained back.
Initially Anurag has C = 0 and S = 0. He has an image to keep and he wants to know before hand how many spare points will enable him to win how many challenges.
Constraints
1 ≤ T ≤ 20 (Number of test cases)
1 ≤ N ≤ 100
0 ≤ ReqC[i] ≤10^9
0 ≤ ReqS[i] ≤ 10^9
0 ≤ P[i] ≤ 10^9
Input
The first line contains T, the number of test cases. Then T test cases follow.
The fist line of each test case contains N. The next line contains N integers of the array ReqC. The next line contains N integers of the array ReqS. The next line contains N integers of the array P.
Output
Print T lines, one for each test case.
For each test case print N space separated integers. The first integer represents the minimum number of spare points needed to complete 1 challenge, the second integer represents the minimum number of spare points needed to complete 2 challenges, and so on.
SAMPLE INPUT
2
3
10 20 30
30 20 10
1 1 1
2
1 2
2 1
1 1
SAMPLE OUTPUT
10 19 28
1 1
Explanation
In the first case:
Anurag needs atleast 10 spare points to solve even one mission.
To solve two mission Anurag needs 19 spare points to start with. He can start out by using 10 of the spare points to increase his C. Then he can solve the first challenge and gain 1 spare point. Now after this he has 9 + 1 = 10 spare point by which he can boost C further to make it 20, which will get him the second challenge.
To solve three missions He will need an additional 9 points (a total of 28 points) so that he can boost his C further to 30.
In the second case:
He just needs 1 spare point to solve both the challenges. He can boost C by 1. Then solve the first challenge. Then use the gained spare point for further boosting the C to solve the second challenge.
输入格式
见题面
输出格式
见题面
样例输入
20
50
278000000 683000000 585000000 1000000000 713000000 455000000 459000000 965000000 208000000 342000000 427000000 1000000 805000000 609000000 938000000 92000000 426000000 889000000 985000000 503000000 966000000 816000000 432000000 945000000 628000000 886000000 416000000 20000000 780000000 252000000 139000000 414000000 287000000 356000000 962000000 539000000 374000000 1000000 37000000 547000000 953000000 483000000 870000000 806000000 956000000 389000000 414000000 86000000 189000000 916000000
373000000 772000000 448000000 616000000 708000000 972000000 926000000 556000000 356000000 50000000 787000000 1000000 986000000 923000000 13000000 149000000 91000000 796000000 648000000 101000000 540000000 410000000 586000000 536000000 985000000 450000000 742000000 828000000 344000000 97000000 307000000 782000000 278000000 436000000 381000000 114000000 672000000 1000000 601000000 165000000 810000000 90000000 941000000 613000000 626000000 647000000 797000000 182000000 717000000 500000000
3000000 6000000 29000000 23000000 12000000 11000000 8000000 16000000 27000000 5000000 22000000 12000000 24000000 1000000 8000000 1000000 11000000 29000000 26000000 12000000 2000000 4000000 20000000 5000000 16000000 29000000 7000000 23000000 2000000 19000000 12000000 12000000 13000000 19000000 15000000 17000000 2000000 24000000 17000000 14000000 14000000 3000000 17000000 3000000 21000000 19000000 7000000 20000000 29000000 13000000
50
469000000 29000000 742000000 82000000 404000000 169000000 168000000 926000000 629000000 342000000 28000000 987000000 617000000 164000000 844000000 18000000 537000000 275000000 959000000 922000000 44000000 829000000 944000000 86000000 686000000 1000000 151000000 399000000 686000000 1000000 44000000 724000000 118000000 967000000 66000000 88000000 622000000 159000000 497000000 684000000 416000000 726000000 250000000 359000000 476000000 518000000 502000000 948000000 244000000 640000000
630000000 662000000 448000000 383000000 750000000 546000000 271000000 203000000 256000000 814000000 904000000 366000000 219000000 880000000 808000000 181000000 459000000 836000000 900000000 341000000 494000000 95000000 497000000 404000000 712000000 1000000 867000000 501000000 694000000 1000000 104000000 286000000 85000000 105000000 373000000 716000000 843000000 149000000 694000000 461000000 715000000 201000000 818000000 380000000 725000000 283000000 236000000 7000000 339000000 95000000
14000000 1000000 18000000 30000000 1000000 18000000 19000000 3000000 7000000 7000000 15000000 28000000 5000000 26000000 28000000 28000000 11000000 29000000 18000000 20000000 17000000 19000000 18000000 23000000 17000000 4000000 20000000 3000000 14000000 2000000 4000000 24000000 20000000 25000000 1000000 6000000 6000000 7000000 14000000 5000000 25000000 18000000 9000000 30000000 17000000 2000000 26000000 19000000 25000000 11000000
50
254000000 972000000 185000000 941000000 499000000 126000000 579000000 414000000 479000000 685000000 459000000 827000000 545000000 289000000 636000000 214000000 563000000 116000000 93000000 41000000 703000000 902000000 15000000 67000000 765000000 112000000 188000000 373000000 349000000 660000000 325000000 226000000 882000000 1000000 394000000 9000000 708000000 651000000 484000000 645000000 492000000 225000000 902000000 597000000 11000000 892000000 727000000 131000000 1000000 909000000
666000000 28000000 492000000 891000000 224000000 222000000 755000000 99000000 213000000 715000000 128000000 893000000 756000000 385000000 669000000 509000000 355000000 411000000 985000000 425000000 294000000 456000000 8000000 69000000 588000000 603000000 943000000 839000000 832000000 610000000 907000000 739000000 240000000 1000000 250000000 935000000 497000000 9000000 728000000 159000000 935000000 987000000 754000000 729000000 481000000 492000000 270000000 722000000 1000000 163000000
18000000 18000000 20000000 7000000 1000000 6000000 12000000 27000000 9000000 7000000 21000000 7000000 13000000 12000000 10000000 16000000 13000000 4000000 2000000 2000000 7000000 10000000 14000000 26000000 30000000 13000000 8000000 24000000 1000000 20000000 22000000 30000000 8000000 26000000 25000000 8000000 3000000 30000000 14000000 6000000 3000000 4000000 16000000 12000000 24000000 3000000 5000000 18000000 2000000 11000000
50
216000000 712000000 570000000 93000000 595000000 260000000 892000000 758000000 921000000 90000000 473000000 664000000 178000000 465000000 627000000 493000000 376000000 163000000 889000000 637000000 107000000 641000000 46000000 297000000 485000000 60000000 297000000 43000000 95000000 380000000 517000000 979000000 233000000 532000000 954000000 538000000 397000000 435000000 953000000 809000000 147000000 331000000 427000000 706000000 45000000 717000000 345000000 989000000 835000000 834000000
600000000 222000000 808000000 883000000 325000000 34000000 23000000 499000000 298000000 860000000 870000000 223000000 821000000 848000000 664000000 955000000 426000000 772000000 355000000 462000000 286000000 973000000 307000000 547000000 694000000 839000000 783000000 841000000 544000000 591000000 578000000 204000000 576000000 387000000 810000000 744000000 787000000 408000000 627000000 532000000 679000000 962000000 388000000 540000000 503000000 39000000 440000000 892000000 442000000 787000000
1000000 1000000 16000000 20000000 25000000 7000000 26000000 9000000 20000000 15000000 29000000 9000000 29000000 4000000 22000000 11000000 4000000 28000000 24000000 30000000 21000000 14000000 17000000 21000000 5000000 7000000 10000000 7000000 17000000 6000000 14000000 22000000 23000000 12000000 26000000 24000000 16000000 5000000 22000000 22000000 13000000 18000000 5000000 6000000 8000000 22000000 6000000 21000000 16000000 29000000
50
364000000 132000000 919000000 834000000 461000000 647000000 146000000 111000000 957000000 255000000 444000000 91000000 149000000 837000000 310000000 933000000 407000000 211000000 819000000 719000000 34000000 545000000 570000000 225000000 297000000 833000000 92000000 110000000 588000000 915000000 707000000 613000000 219000000 880000000 88000000 584000000 289000000 321000000 355000000 880000000 310000000 1000000 942000000 158000000 467000000 765000000 921000000 507000000 785000000 393000000
301000000 811000000 317000000 619000000 136000000 861000000 371000000 69000000 702000000 127000000 915000000 198000000 131000000 461000000 569000000 2000000 805000000 966000000 50000000 39000000 673000000 166000000 740000000 457000000 659000000 26000000 843000000 390000000 378000000 663000000 420000000 522000000 145000000 522000000 476000000 947000000 926000000 391000000 673000000 501000000 509000000 1000000 503000000 622000000 829000000 936000000 3000000 914000000 65000000 13000000
6000000 26000000 7000000 4000000 1000000 6000000 14000000 7000000 10000000 4000000 6000000 20000000 5000000 11000000 11000000 3000000 30000000 8000000 23000000 20000000 10000000 24000000 29000000 19000000 7000000 27000000 22000000 14000000 15000000 6000000 14000000 3000000 9000000 19000000 30000000 8000000 16000000 8000000 27000000 4000000 16000000 28000000 14000000 27000000 29000000 3000000 3000000 12000000 16000000 29000000
50
102000000 775000000 457000000 710000000 126000000 901000000 404000000 20000000 793000000 540000000 443000000 781000000 464000000 398000000 8000000 1000000 86000000 787000000 618000000 297000000 49000000 262000000 444000000 374000000 829000000 943000000 789000000 738000000 1000000 918000000 640000000 597000000 414000000 965000000 541000000 816000000 750000000 253000000 836000000 549000000 82000000 671000000 464000000 332000000 42000000 83000000 817000000 414000000 848000000 572000000
770000000 775000000 199000000 865000000 906000000 729000000 956000000 681000000 727000000 982000000 980000000 266000000 14000000 362000000 157000000 1000000 421000000 35000000 948000000 835000000 24000000 982000000 246000000 901000000 732000000 711000000 480000000 556000000 998000000 203000000 630000000 885000000 604000000 696000000 246000000 861000000 298000000 322000000 317000000 665000000 581000000 663000000 56000000 862000000 650000000 620000000 611000000 881000000 807000000 501000000
20000000 28000000 29000000 11000000 28000000 9000000 20000000 24000000 8000000 3000000 28000000 14000000 16000000 16000000 5000000 13000000 12000000 22000000 10000000 24000000 2000000 12000000 7000000 21000000 2000000 19000000 4000000 15000000 2000000 29000000 20000000 7000000 12000000 29000000 5000000 30000000 22000000 1000000 30000000 29000000 18000000 4000000 29000000 11000000 5000000 8000000 3000000 9000000 3000000 18000000
50
536000000 85000000 1000000 617000000 910000000 73000000 273000000 108000000 972000000 803000000 253000000 294000000 292000000 333000000 228000000 184000000 605000000 375000000 916000000 178000000 378000000 163000000 433000000 95000000 506000000 848000000 146000000 798000000 200000000 993000000 1000000 65000000 827000000 735000000 941000000 377000000 566000000 881000000 978000000 782000000 569000000 706000000 615000000 763000000 829000000 115000000 246000000 327000000 971000000 1000000
12000000 424000000 1000000 359000000 416000000 318000000 258000000 312000000 588000000 89000000 978000000 717000000 772000000 510000000 206000000 882000000 319000000 850000000 338000000 852000000 247000000 746000000 59000000 514000000 340000000 220000000 447000000 142000000 10000000 691000000 1000000 655000000 853000000 621000000 960000000 946000000 827000000 527000000 201000000 507000000 193000000 695000000 599000000 768000000 531000000 888000000 465000000 949000000 456000000 1000000
28000000 24000000 13000000 24000000 16000000 9000000 18000000 18000000 14000000 29000000 28000000 9000000 8000000 13000000 12000000 21000000 15000000 3000000 9000000 19000000 1000000 16000000 25000000 29000000 22000000 30000000 1000000 6000000 17000000 5000000 14000000 8000000 6000000 14000000 19000000 14000000 11000000 10000000 15000000 8000000 15000000 1000000 10000000 5000000 25000000 11000000 24000000 5000000 21000000 15000000
50
559000000 1000000 652000000 909000000 244000000 475000000 1000000 73000000 710000000 1000000 779000000 105000000 717000000 931000000 115000000 221000000 779000000 901000000 963000000 542000000 416000000 94000000 898000000 726000000 558000000 989000000 571000000 453000000 1000000 524000000 725000000 668000000 1000000 492000000 211000000 765000000 525000000 941000000 629000000 288000000 439000000 898000000 571000000 798000000 231000000 298000000 184000000 825000000 149000000 319000000
915000000 1000000 555000000 853000000 283000000 381000000 1000000 34000000 596000000 1000000 161000000 717000000 757000000 347000000 279000000 892000000 90000000 358000000 983000000 762000000 753000000 375000000 799000000 373000000 981000000 740000000 412000000 947000000 1000000 977000000 930000000 199000000 1000000 812000000 743000000 216000000 443000000 113000000 464000000 1000000 219000000 606000000 338000000 193000000 866000000 655000000 562000000 699000000 357000000 906000000
1000000 16000000 1000000 1000000 26000000 11000000 5000000 5000000 17000000 20000000 12000000 18000000 29000000 8000000 19000000 24000000 9000000 13000000 17000000 26000000 5000000 10000000 15000000 19000000 22000000 21000000 4000000 12000000 16000000 23000000 2000000 8000000 10000000 5000000 24000000 4000000 5000000 25000000 4000000 7000000 11000000 17000000 26000000 28000000 23000000 9000000 14000000 21000000 5000000 19000000
50
188000000 336000000 755000000 938000000 48000000 839000000 17000000 332000000 70000000 860000000 873000000 902000000 189000000 658000000 860000000 672000000 607000000 241000000 674000000 388000000 1000000 3000000 805000000 539000000 201000000 48000000 557000000 294000000 122000000 289000000 756000000 526000000 795000000 776000000 467000000 444000000 340000000 324000000 698000000 688000000 950000000 849000000 659000000 356000000 449000000 917000000 158000000 705000000 696000000 619000000
156000000 486000000 802000000 532000000 982000000 589000000 316000000 944000000 453000000 687000000 346000000 814000000 13000000 719000000 73000000 169000000 853000000 532000000 660000000 22000000 1000000 121000000 970000000 475000000 580000000 45000000 271000000 197000000 973000000 740000000 185000000 976000000 386000000 162000000 236000000 57000000 710000000 38000000 492000000 998000000 927000000 36000000 513000000 772000000 746000000 856000000 197000000 319000000 155000000 801000000
29000000 1000000 16000000 2000000 16000000 2000000 23000000 29000000 7000000 12000000 14000000 30000000 20000000 16000000 26000000 2000000 17000000 19000000 3000000 23000000 3000000 10000000 4000000 27000000 23000000 30000000 22000000 24000000 17000000 16000000 9000000 10000000 15000000 5000000 30000000 5000000 18000000 19000000 3000000 11000000 4000000 22000000 9000000 10000000 15000000 19000000 9000000 6000000 14000000 20000000
50
933000000 944000000 907000000 731000000 976000000 258000000 451000000 135000000 401000000 815000000 18000000 895000000 537000000 418000000 639000000 604000000 488000000 274000000 92000000 463000000 536000000 185000000 995000000 930000000 929000000 16000000 59000000 189000000 981000000 488000000 799000000 410000000 468000000 737000000 86000000 1000000 656000000 949000000 179000000 1000000 466000000 990000000 422000000 385000000 194000000 123000000 272000000 101000000 290000000 21000000
359000000 724000000 832000000 91000000 275000000 466000000 622000000 275000000 862000000 51000000 786000000 13000000 462000000 110000000 945000000 256000000 478000000 32000000 559000000 184000000 398000000 445000000 874000000 994000000 960000000 467000000 399000000 74000000 482000000 342000000 690000000 951000000 426000000 68000000 922000000 1000000 20000000 657000000 274000000 1000000 830000000 299000000 40000000 216000000 843000000 926000000 872000000 463000000 418000000 304000000
17000000 28000000 20000000 8000000 17000000 4000000 19000000 28000000 24000000 9000000 13000000 3000000 13000000 23000000 17000000 18000000 30000000 3000000 23000000 16000000 26000000 13000000 5000000 28000000 6000000 23000000 12000000 27000000 1000000 22000000 14000000 9000000 1000000 25000000 9000000 5000000 22000000 22000000 30000000 25000000 11000000 14000000 18000000 23000000 13000000 10000000 25000000 14000000 12000000 26000000
50
393000000 999000000 2000000 719000000 524000000 616000000 620000000 545000000 338000000 218000000 33000000 147000000 234000000 1000000 985000000 663000000 438000000 971000000 317000000 510000000 935000000 635000000 1000000 945000000 423000000 40000000 433000000 536000000 13000000 779000000 41000000 350000000 796000000 676000000 266000000 186000000 395000000 652000000 972000000 1000000 141000000 52000000 18000000 579000000 322000000 510000000 954000000 1000000 587000000 274000000
33000000 259000000 688000000 669000000 798000000 257000000 344000000 211000000 13000000 69000000 817000000 854000000 963000000 1000000 287000000 364000000 156000000 664000000 95000000 665000000 807000000 416000000 1000000 19000000 7000000 811000000 986000000 503000000 441000000 782000000 711000000 952000000 172000000 726000000 787000000 982000000 507000000 288000000 553000000 1000000 92000000 305000000 856000000 399000000 12000000 823000000 60000000 1000000 808000000 965000000
9000000 24000000 7000000 17000000 24000000 19000000 9000000 15000000 25000000 6000000 22000000 14000000 11000000 20000000 26000000 26000000 26000000 11000000 18000000 13000000 12000000 23000000 11000000 17000000 17000000 5000000 15000000 24000000 12000000 25000000 19000000 11000000 22000000 8000000 4000000 16000000 27000000 13000000 16000000 8000000 11000000 3000000 24000000 17000000 21000000 9000000 29000000 24000000 17000000 6000000
50
896000000 532000000 809000000 305000000 2000000 345000000 341000000 373000000 956000000 19000000 952000000 382000000 445000000 155000000 387000000 541000000 567000000 714000000 159000000 84000000 154000000 185000000 254000000 435000000 871000000 681000000 383000000 843000000 313000000 730000000 85000000 638000000 327000000 446000000 351000000 860000000 650000000 550000000 496000000 126000000 700000000 235000000 408000000 190000000 974000000 1000000 487000000 340000000 72000000 431000000
923000000 571000000 260000000 257000000 144000000 829000000 958000000 32000000 546000000 688000000 923000000 911000000 13000000 594000000 480000000 283000000 583000000 232000000 505000000 553000000 475000000 542000000 677000000 783000000 256000000 361000000 111000000 704000000 171000000 207000000 916000000 970000000 159000000 453000000 139000000 562000000 571000000 807000000 167000000 805000000 643000000 563000000 590000000 545000000 980000000 1000000 997000000 929000000 964000000 267000000
17000000 21000000 11000000 25000000 20000000 24000000 28000000 17000000 15000000 27000000 25000000 9000000 25000000 20000000 26000000 10000000 22000000 25000000 29000000 29000000 23000000 16000000 24000000 22000000 5000000 9000000 8000000 4000000 16000000 12000000 8000000 25000000 2000000 22000000 13000000 27000000 14000000 5000000 6000000 5000000 19000000 25000000 18000000 22000000 6000000 6000000 7000000 16000000 5000000 26000000
50
904000000 889000000 868000000 321000000 531000000 879000000 298000000 811000000 505000000 638000000 996000000 895000000 251000000 807000000 83000000 382000000 419000000 44000000 799000000 224000000 976000000 813000000 370000000 80000000 468000000 1000000 796000000 941000000 417000000 584000000 487000000 465000000 182000000 348000000 819000000 605000000 294000000 1000000 2000000 866000000 241000000 638000000 709000000 473000000 407000000 62000000 332000000 466000000 1000000 905000000
833000000 283000000 303000000 289000000 38000000 429000000 674000000 820000000 530000000 858000000 274000000 683000000 986000000 912000000 693000000 160000000 714000000 565000000 695000000 35000000 441000000 132000000 469000000 974000000 482000000 1000000 500000000 641000000 763000000 592000000 354000000 934000000 761000000 174000000 155000000 477000000 448000000 1000000 764000000 89000000 78000000 213000000 259000000 503000000 824000000 488000000 411000000 773000000 1000000 960000000
15000000 15000000 22000000 23000000 13000000 6000000 29000000 17000000 9000000 13000000 6000000 24000000 5000000 8000000 29000000 24000000 12000000 10000000 5000000 10000000 5000000 29000000 23000000 10000000 30000000 14000000 4000000 13000000 3000000 16000000 3000000 13000000 25000000 20000000 23000000 21000000 30000000 3000000 5000000 5000000 12000000 26000000 26000000 15000000 4000000 12000000 21000000 25000000 17000000 28000000
50
921000000 728000000 333000000 1000000 668000000 146000000 918000000 701000000 151000000 946000000 263000000 17000000 514000000 248000000 849000000 971000000 712000000 935000000 93000000 998000000 687000000 742000000 445000000 354000000 922000000 128000000 640000000 145000000 314000000 828000000 873000000 419000000 184000000 956000000 423000000 337000000 299000000 864000000 381000000 660000000 207000000 475000000 578000000 686000000 859000000 372000000 689000000 272000000 481000000 670000000
939000000 127000000 516000000 1000000 912000000 771000000 871000000 23000000 229000000 741000000 50000000 736000000 409000000 547000000 562000000 690000000 456000000 418000000 715000000 388000000 415000000 782000000 260000000 769000000 780000000 212000000 936000000 160000000 507000000 906000000 653000000 980000000 961000000 397000000 199000000 996000000 627000000 265000000 29000000 28000000 591000000 155000000 362000000 360000000 17000000 953000000 276000000 63000000 94000000 960000000
4000000 25000000 10000000 26000000 11000000 27000000 26000000 3000000 1000000 25000000 8000000 5000000 5000000 6000000 29000000 10000000 9000000 2000000 24000000 15000000 25000000 24000000 10000000 29000000 22000000 23000000 19000000 17000000 29000000 25000000 20000000 24000000 3000000 11000000 1000000 7000000 1000000 6000000 28000000 7000000 18000000 12000000 8000000 14000000 3000000 5000000 7000000 26000000 9000000 24000000
50
786000000 697000000 57000000 568000000 670000000 68000000 805000000 988000000 502000000 569000000 197000000 130000000 667000000 866000000 59000000 805000000 798000000 430000000 1000000 596000000 640000000 641000000 668000000 889000000 219000000 337000000 225000000 733000000 326000000 993000000 831000000 473000000 924000000 505000000 280000000 238000000 236000000 291000000 828000000 949000000 849000000 614000000 453000000 734000000 267000000 757000000 252000000 403000000 778000000 273000000
576000000 629000000 284000000 980000000 346000000 222000000 494000000 194000000 592000000 393000000 99000000 872000000 791000000 322000000 880000000 691000000 764000000 230000000 1000000 71000000 996000000 161000000 706000000 266000000 507000000 162000000 834000000 1000000000 175000000 757000000 725000000 719000000 837000000 663000000 25000000 531000000 377000000 37000000 58000000 762000000 602000000 419000000 613000000 520000000 251000000 216000000 887000000 91000000 482000000 872000000
19000000 30000000 28000000 19000000 19000000 12000000 13000000 9000000 8000000 11000000 3000000 8000000 30000000 10000000 13000000 19000000 1000000 18000000 7000000 30000000 15000000 6000000 5000000 9000000 19000000 11000000 30000000 16000000 4000000 16000000 25000000 5000000 23000000 22000000 26000000 22000000 17000000 21000000 18000000 9000000 23000000 20000000 16000000 10000000 19000000 25000000 2000000 27000000 25000000 18000000
50
305000000 237000000 553000000 1000000 238000000 85000000 736000000 481000000 779000000 228000000 776000000 415000000 466000000 706000000 826000000 934000000 596000000 881000000 999000000 766000000 929000000 370000000 1000000 793000000 251000000 534000000 991000000 606000000 698000000 878000000 451000000 608000000 856000000 915000000 903000000 336000000 853000000 957000000 450000000 1000000 763000000 751000000 1000000 51000000 323000000 32000000 582000000 496000000 173000000 394000000
198000000 271000000 276000000 1000000 998000000 386000000 757000000 605000000 748000000 536000000 763000000 700000000 6000000 239000000 3000000 954000000 527000000 283000000 626000000 444000000 358000000 762000000 468000000 703000000 168000000 696000000 72000000 360000000 104000000 211000000 625000000 620000000 133000000 943000000 676000000 208000000 355000000 362000000 616000000 1000000 183000000 873000000 1000000 660000000 823000000 904000000 882000000 198000000 983000000 548000000
17000000 7000000 4000000 4000000 13000000 2000000 5000000 5000000 24000000 17000000 5000000 15000000 27000000 11000000 9000000 23000000 9000000 8000000 28000000 8000000 21000000 30000000 5000000 16000000 6000000 1000000 17000000 13000000 12000000 25000000 1000000 4000000 23000000 27000000 17000000 25000000 2000000 12000000 26000000 21000000 4000000 28000000 6000000 25000000 3000000 26000000 13000000 20000000 27000000 6000000
50
744000000 775000000 810000000 917000000 1000000 848000000 829000000 660000000 928000000 156000000 101000000 894000000 369000000 949000000 19000000 294000000 314000000 611000000 985000000 1000000 450000000 527000000 344000000 663000000 539000000 411000000 872000000 810000000 278000000 1000000 715000000 903000000 325000000 60000000 177000000 949000000 695000000 292000000 588000000 775000000 399000000 687000000 396000000 812000000 389000000 574000000 499000000 965000000 569000000 419000000
363000000 372000000 820000000 275000000 1000000 939000000 955000000 481000000 757000000 984000000 954000000 364000000 232000000 936000000 429000000 705000000 702000000 280000000 433000000 1000000 124000000 501000000 795000000 627000000 470000000 565000000 601000000 26000000 979000000 1000000 743000000 174000000 630000000 589000000 562000000 917000000 628000000 360000000 864000000 724000000 348000000 786000000 324000000 167000000 809000000 54000000 278000000 868000000 393000000 106000000
8000000 27000000 11000000 5000000 17000000 25000000 16000000 25000000 18000000 5000000 25000000 29000000 4000000 6000000 28000000 23000000 3000000 13000000 14000000 1000000 24000000 11000000 6000000 26000000 13000000 13000000 10000000 21000000 22000000 3000000 24000000 16000000 10000000 30000000 7000000 28000000 5000000 6000000 4000000 6000000 16000000 21000000 1000000 29000000 20000000 14000000 7000000 29000000 17000000 8000000
50
570000000 13000000 54000000 454000000 225000000 628000000 492000000 8000000 50000000 706000000 1000000 299000000 926000000 305000000 295000000 135000000 732000000 130000000 414000000 405000000 536000000 238000000 954000000 711000000 57000000 526000000 61000000 229000000 1000000 362000000 526000000 40000000 312000000 221000000 583000000 690000000 880000000 6000000 74000000 587000000 561000000 847000000 703000000 332000000 277000000 729000000 974000000 279000000 645000000 588000000
656000000 975000000 321000000 651000000 704000000 877000000 366000000 647000000 228000000 221000000 1000000 241000000 1000000000 777000000 697000000 255000000 778000000 768000000 234000000 663000000 781000000 271000000 116000000 996000000 872000000 698000000 163000000 436000000 31000000 279000000 21000000 381000000 144000000 538000000 479000000 298000000 102000000 473000000 342000000 370000000 360000000 33000000 678000000 200000000 643000000 669000000 69000000 138000000 586000000 909000000
17000000 13000000 15000000 21000000 19000000 12000000 30000000 17000000 3000000 30000000 22000000 27000000 28000000 15000000 14000000 3000000 23000000 10000000 25000000 5000000 13000000 25000000 11000000 26000000 12000000 11000000 12000000 22000000 26000000 8000000 13000000 6000000 8000000 23000000 6000000 11000000 11000000 28000000 18000000 4000000 6000000 8000000 30000000 4000000 21000000 30000000 27000000 26000000 18000000 26000000
50
218000000 931000000 1000000 947000000 451000000 740000000 19000000 165000000 474000000 192000000 227000000 844000000 736000000 218000000 915000000 153000000 126000000 210000000 244000000 461000000 373000000 426000000 342000000 1000000 606000000 778000000 170000000 301000000 218000000 3000000 155000000 219000000 195000000 151000000 903000000 796000000 440000000 518000000 986000000 625000000 948000000 209000000 115000000 307000000 518000000 465000000 547000000 938000000 233000000 296000000
320000000 78000000 1000000 436000000 100000000 79000000 253000000 39000000 798000000 780000000 650000000 788000000 626000000 336000000 321000000 583000000 870000000 906000000 878000000 494000000 903000000 429000000 654000000 1000000 593000000 504000000 558000000 698000000 323000000 399000000 412000000 418000000 392000000 70000000 35000000 65000000 574000000 500000000 355000000 36000000 753000000 316000000 486000000 241000000 712000000 669000000 75000000 421000000 766000000 707000000
23000000 3000000 26000000 30000000 5000000 30000000 26000000 26000000 20000000 19000000 13000000 4000000 30000000 9000000 21000000 3000000 23000000 28000000 16000000 30000000 16000000 6000000 11000000 7000000 8000000 28000000 15000000 3000000 29000000 17000000 11000000 28000000 25000000 18000000 9000000 20000000 14000000 20000000 17000000 19000000 7000000 16000000 12000000 1000000 11000000 13000000 9000000 26000000 13000000 21000000
50
252000000 353000000 709000000 270000000 95000000 375000000 731000000 685000000 844000000 918000000 580000000 1000000 1000000 383000000 897000000 807000000 266000000 147000000 779000000 324000000 661000000 802000000 803000000 790000000 367000000 879000000 962000000 61000000 448000000 705000000 993000000 459000000 610000000 346000000 402000000 400000000 525000000 555000000 396000000 29000000 235000000 476000000 378000000 939000000 173000000 1000000 179000000 412000000 563000000 662000000
918000000 20000000 89000000 58000000 764000000 739000000 350000000 81000000 170000000 945000000 193000000 1000000 1000000 912000000 256000000 335000000 684000000 775000000 808000000 721000000 369000000 771000000 70000000 510000000 963000000 952000000 319000000 611000000 830000000 900000000 207000000 628000000 879000000 667000000 940000000 720000000 579000000 794000000 219000000 931000000 368000000 24000000 489000000 282000000 201000000 1000000 418000000 874000000 198000000 879000000
23000000 30000000 4000000 28000000 14000000 19000000 3000000 3000000 16000000 29000000 20000000 12000000 8000000 9000000 15000000 8000000 13000000 1000000 17000000 16000000 13000000 14000000 10000000 21000000 19000000 30000000 14000000 28000000 14000000 16000000 8000000 18000000 2000000 22000000 26000000 10000000 20000000 28000000 23000000 1000000 20000000 18000000 16000000 11000000 6000000 6000000 11000000 21000000 4000000 25000000
样例输出
1000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 24000000 41000000
1000000 1000000 1000000 2000000 4000000 18000000 18000000 23000000 23000000 25000000 27000000 27000000 27000000 27000000 32000000 34000000 47000000 47000000 47000000 47000000 47000000 47000000 47000000 53000000 53000000 53000000 53000000 53000000 53000000 53000000 53000000 53000000 53000000 53000000 53000000 88000000 88000000 102000000 111000000 116000000 116000000 117000000 117000000 117000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 9000000 17000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000 18000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 6000000 18000000 28000000 33000000 54000000 54000000 77000000 80000000 80000000 94000000 124000000 137000000 191000000 191000000 206000000 206000000 246000000 270000000 270000000 318000000 318000000 364000000 364000000 364000000 364000000 374000000 382000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 23000000 23000000 23000000 47000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 67000000 69000000 69000000 69000000 69000000 69000000 69000000 69000000 69000000 69000000 69000000 93000000 93000000 96000000 116000000 121000000 121000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 2000000 7000000 14000000 20000000 29000000 41000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 15000000 15000000 15000000 15000000 17000000 23000000 23000000 26000000 26000000 45000000 69000000 79000000 79000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000 108000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 3000000 20000000 20000000 26000000 26000000 26000000 48000000 63000000 69000000 73000000 73000000 73000000 74000000 102000000 103000000 103000000 103000000 128000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000 139000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 14000000 48000000 95000000 122000000 122000000 131000000 140000000 140000000 140000000 140000000 140000000 140000000 140000000 140000000 145000000 174000000 174000000
2000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 3000000 8000000 17000000 17000000 17000000 24000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 38000000 61000000 79000000 95000000 136000000 147000000 147000000 147000000 147000000 162000000
12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 22000000 22000000 40000000 41000000 41000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 45000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 60000000 73000000 76000000 76000000 76000000
1000000 1000000 1000000 1000000 4000000 5000000 5000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 12000000 33000000 56000000 56000000 71000000 75000000 76000000 80000000 102000000 111000000 111000000 111000000 112000000 112000000 112000000 112000000 112000000 112000000 117000000 117000000 120000000 147000000 162000000 162000000 182000000 182000000 184000000 184000000 184000000 219000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 4000000 4000000 14000000 19000000 19000000 19000000 19000000 27000000 41000000 41000000 41000000 41000000 41000000 41000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000 44000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000000 10000000 10000000 10000000 10000000 20000000 20000000 20000000 20000000 20000000 20000000 20000000 20000000 20000000 20000000 20000000 20000000 38000000 67000000 99000000 106000000 113000000 113000000 113000000 113000000 113000000 113000000 113000000 141000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 19000000 35000000 35000000 35000000 35000000 35000000 35000000 35000000 35000000 35000000 35000000 35000000 38000000 38000000 58000000 58000000 62000000 62000000 62000000 62000000 62000000 62000000 65000000 77000000 79000000 116000000 116000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 10000000 10000000 29000000 29000000 29000000 34000000 34000000 79000000 79000000 79000000 104000000 105000000 143000000 151000000 151000000 157000000 157000000 157000000 157000000 157000000 161000000 161000000 161000000 161000000 163000000 182000000 208000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 31000000 66000000 70000000 71000000 80000000 80000000 80000000 80000000 80000000 80000000 80000000 80000000 80000000 85000000 85000000 101000000 117000000 158000000 171000000 171000000 171000000 171000000 191000000 191000000 237000000
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 15000000 29000000 43000000 59000000 59000000 62000000 63000000 80000000 80000000 80000000 80000000 80000000 80000000 80000000 105000000 105000000 105000000 105000000 105000000 105000000 136000000 147000000 155000000 183000000
1000000 1000000 7000000 16000000 34000000 34000000 34000000 34000000 34000000 34000000 34000000 34000000 34000000 34000000 34000000 34000000 38000000 51000000 51000000 62000000 73000000 78000000 81000000 81000000 81000000 81000000 98000000 98000000 98000000 98000000 98000000 98000000 98000000 111000000 112000000 112000000 118000000 123000000 123000000 123000000 131000000 137000000 137000000 137000000 152000000 152000000 152000000 152000000 152000000 152000000
1000000 1000000 1000000 1000000 1000000 15000000 17000000 35000000 35000000 36000000 63000000 76000000 99000000 99000000 99000000 126000000 126000000 126000000 126000000 126000000 126000000 126000000 126000000 126000000 132000000 151000000 151000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 160000000 173000000 175000000 199000000 215000000 223000000 239000000 264000000 264000000 273000000 279000000