結果

問題 No.183 たのしい排他的論理和(EASY)
ユーザー 14番14番
提出日時 2016-07-17 14:18:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,906 ms / 5,000 ms
コード長 25,175 bytes
コンパイル時間 2,204 ms
コンパイル使用メモリ 104,332 KB
実行使用メモリ 161,932 KB
最終ジャッジ日時 2023-09-12 01:02:27
合計ジャッジ時間 13,056 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
23,912 KB
testcase_01 AC 64 ms
24,160 KB
testcase_02 AC 64 ms
22,616 KB
testcase_03 AC 64 ms
24,476 KB
testcase_04 AC 63 ms
24,032 KB
testcase_05 AC 64 ms
22,604 KB
testcase_06 AC 62 ms
22,028 KB
testcase_07 AC 1,906 ms
161,932 KB
testcase_08 AC 1,084 ms
114,268 KB
testcase_09 AC 758 ms
84,184 KB
testcase_10 AC 915 ms
96,672 KB
testcase_11 AC 1,165 ms
121,852 KB
testcase_12 AC 67 ms
25,188 KB
testcase_13 AC 61 ms
19,820 KB
testcase_14 AC 94 ms
45,568 KB
testcase_15 AC 1,208 ms
125,348 KB
testcase_16 AC 63 ms
22,328 KB
testcase_17 AC 320 ms
47,088 KB
testcase_18 AC 1,522 ms
139,760 KB
testcase_19 AC 193 ms
35,000 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        int switchCount = int.Parse(Reader.ReadLine());
        this.SwitchList = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();
        this.Dic = new bool[SwitchList.Length, (1<<14 + 1)];
        this.GetAns(0, 0);
        Console.WriteLine(this.ans.Count);
    }
    
    private bool[,] Dic;

    private Dictionary<int, bool> ans = new Dictionary<int, bool>();
    private void GetAns(int idx, int num) {
        if(idx >= this.SwitchList.Length) {
            if(!ans.ContainsKey(num)) {
                ans.Add(num, true);
            }
            return;
        }
        if(this.Dic[idx, num]) {
            return;
        }
        this.GetAns(idx + 1, num);
        this.GetAns(idx + 1, num ^ SwitchList[idx]);
        this.Dic[idx, num] = true;
    }

    private int[] SwitchList;


    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"


4432
1573 9858 11310 296 3530 4923 9081 15701 13194 16064 6994 14179 12879 10116 14329 5285 8983 10205 11774 1386 9688 11327 15265 5187 10098 10345 13966 6092 2663 7571 9722 4799 3664 13580 8693 13797 15858 14186 6315 3088 14423 4954 13429 2439 6868 9965 3327 16261 5147 11543 1635 4117 283 2878 1457 12737 2782 12785 15498 12904 3639 5874 16117 2143 10573 3618 5861 14232 8607 14145 5214 2762 5942 14651 4048 1732 4647 7018 12144 10076 9108 1377 10979 5865 12692 5406 2638 15670 8159 5815 3212 15338 14630 13253 4964 347 7383 7858 7014 1326 1569 721 15675 5698 6652 13312 14672 10623 2600 12406 4998 2755 4026 12754 2412 15768 9835 9686 5592 10078 4086 13409 9222 9988 4738 11477 15869 13124 14896 2831 8845 14828 9696 1321 10264 780 9204 2190 10595 8569 6038 11387 4354 1752 1779 680 10939 4615 10484 10345 10088 5171 4368 4623 15301 10323 5866 14545 8494 10811 11744 1378 8583 1872 1192 8321 15504 13595 13600 4778 5508 13590 11666 14209 1305 3886 32 8752 12637 4033 7679 13906 2249 9458 14813 7501 16005 7408 13661 13069 9849 4764 12483 963 258 2883 5346 8713 14972 16266 2010 15652 4454 9860 2579 14165 4145 10223 12258 2401 7583 2455 6430 10832 11547 12597 1231 15866 13544 794 6816 3932 9128 3724 16175 11948 6855 13536 44 2841 8176 7730 13867 11945 6322 13721 8749 10089 7611 1647 2554 749 8209 11823 12364 276 7150 195 2376 13123 9862 656 711 12889 78 6365 4207 2212 5907 1808 1891 15829 4364 139 3308 9588 10527 6730 10341 2789 10108 11351 6105 12553 2264 9820 10254 5930 6896 1013 11368 4654 1708 4956 3846 9339 10165 3071 1403 1645 11992 15778 536 6871 11154 10373 642 1993 9930 8834 214 13619 5060 1172 12645 132 2645 10786 13292 6664 9484 8598 15239 6437 9658 16177 7832 8646 242 4135 9025 12677 9150 9252 2015 5933 5011 13218 1617 7585 9299 3609 11314 792 2699 6752 110 9994 10477 14181 5235 15377 7665 12995 16328 7519 15737 6556 5646 307 1390 9670 7361 2694 7906 369 1380 4154 14618 4090 1354 14935 2266 2341 4258 14025 13352 5762 10335 7982 9986 10003 6067 11750 1355 15515 14729 3347 7311 8965 1753 11642 7841 15223 8313 14538 4171 4891 5724 1783 8492 9349 10474 2782 448 12189 12476 367 8241 14478 5503 11721 13539 8710 13354 15567 12165 6493 3843 4276 2109 15023 6870 9405 12350 6839 9130 8290 522 8540 1146 8013 8850 2859 2391 11981 2464 1902 16328 6592 13177 7681 10803 7569 12885 7946 2337 3984 5745 15854 12331 13452 1866 5907 11432 7387 8224 13231 3676 11314 3289 10381 10310 3381 13072 535 14820 2897 14363 464 14421 1824 8936 2049 2960 6939 2575 4998 7095 1375 12283 15562 7959 5269 13624 15504 9797 7552 5809 9916 8162 10461 5054 1518 7396 12154 9371 12654 14602 1109 12094 11604 386 9399 3537 6342 8551 12393 2598 9982 905 12188 11060 4804 2533 9325 2127 8967 11055 2584 9145 1892 2585 14353 14629 14220 3089 5893 5442 1464 262 7090 8524 761 2011 11455 3001 14760 14733 15690 1311 9449 7679 14239 14515 10546 3719 6637 6079 5060 2457 15706 4957 1399 11234 7445 13337 1285 12354 14426 6198 9596 241 10722 13808 12936 12622 7058 6279 4915 12289 6291 10783 7651 12847 14498 2704 3518 10293 3454 1418 11842 16210 9237 5768 15467 7262 4845 1951 4499 4564 11334 13483 14645 9863 10868 2295 7335 1218 16319 16315 5190 5073 15000 2627 3747 12523 14861 10642 6832 16384 312 15229 4087 6465 8364 5135 9716 6100 10464 1879 4697 5465 7497 428 14953 10409 1768 5971 4000 13610 7984 4915 9369 5669 5232 2695 234 2106 5674 10073 11962 8647 14369 13472 5301 826 10973 9753 8265 3634 9871 8447 2670 11400 8673 13982 14743 13126 791 3062 6697 7817 13283 6236 10063 14238 11927 5640 2870 10867 3791 2024 7308 430 885 4998 7556 11577 572 15351 11854 2882 1567 11687 2852 13268 242 1758 4568 14445 3620 7339 10064 7589 10770 5002 7678 6070 2763 10528 11762 2247 8874 2700 12158 9273 13237 10672 4395 9677 9261 442 7149 5035 13225 1063 2214 5454 5475 12256 8050 12281 9178 6463 12599 4646 5364 7136 12926 15041 161 7022 956 182 3026 11067 1486 4134 16004 14020 6864 5663 1549 11254 11985 611 9976 14521 8331 6597 13155 11646 14523 14193 9542 12089 10600 3386 7614 15237 10274 9533 5515 7316 14694 8683 13383 10083 4441 14806 7064 11733 1707 964 3774 2939 287 616 8262 11844 4316 9227 3324 14501 3670 13831 964 361 15839 7485 8412 5389 14699 6678 1012 9877 12986 8430 4151 4364 12537 13676 9924 13338 13759 852 5780 14370 6608 16022 9911 12745 7738 754 7127 2742 11752 806 13244 14349 2618 8546 7306 8807 1605 12958 1416 4947 7336 9721 13933 3940 6326 15992 10881 9177 16177 13866 13397 12856 14515 5614 14535 15661 1153 1738 14759 9353 4762 15767 6866 11447 11100 7660 2256 2513 12115 8479 14188 10243 12922 14499 13256 11473 10526 1148 9169 7437 11018 15230 5949 6908 15602 11022 7326 416 2841 7906 4121 10009 1650 8908 1217 2697 390 8834 12425 11626 14934 10376 1263 1194 6214 6454 832 13585 12620 1241 10584 2856 1041 14379 2755 2373 1096 5862 5663 1248 4177 854 13764 954 8219 12571 15476 14058 11156 9509 9048 10358 16222 13708 6322 5100 5810 11992 7077 760 13499 4232 14225 2031 9326 8001 161 16299 6032 6326 377 14278 6516 2957 433 4888 2560 3581 14383 391 5697 8107 10707 5385 9330 9885 14193 13992 10716 14091 12022 3402 9214 15396 8880 9657 12254 2945 6449 2387 15904 4154 9209 3365 5365 4627 5742 363 15148 8047 13531 15441 10487 7789 1338 10287 14909 15269 8167 9666 10869 2923 2118 525 2862 16276 14555 8490 13222 464 1280 12103 673 8316 9096 1744 8274 12489 8347 7449 11121 8420 3415 16277 7299 1985 11217 12415 355 9832 10233 12851 14545 9321 4912 8757 5055 3640 12997 12746 14332 2710 8090 358 13168 4164 94 7300 6116 1437 15750 10024 11384 1545 5496 1515 2987 6396 13708 3891 15670 8623 3210 3230 15458 11864 5283 15882 9491 3751 8626 5160 13449 9289 2468 2720 863 4341 10000 10504 9198 5560 3963 13822 560 9121 8065 2157 6819 7278 4226 11494 4657 3093 5839 5588 15829 13820 662 620 2303 15002 5044 8383 3612 5223 11454 12999 14042 15637 14018 11472 1987 1425 2150 14022 4581 13524 5690 1407 9959 4652 7397 12435 6360 2497 13591 9050 15428 8086 6082 5552 14298 4547 5100 585 795 9210 12871 7543 569 3424 6853 14468 6072 11438 12608 11433 12531 9505 1594 5023 15647 5322 12927 3188 10711 2577 1323 3868 2429 11379 9563 4299 1968 14662 431 6216 13448 7097 11505 7716 13725 6624 12200 12521 7741 4959 14035 11177 7934 6930 7297 1571 6392 16372 160 1918 1825 6961 7768 6038 432 3680 7905 14342 7128 12920 11029 32 10052 4947 14286 1560 14571 15158 10553 14022 8323 4700 5971 2545 7054 465 13125 7556 712 6016 13453 6051 12051 7679 13751 9025 4467 303 16072 10627 421 14976 13561 9883 13485 7346 4800 7552 16185 959 1367 15385 9506 8783 3560 14615 8734 10455 185 13334 2970 10495 16225 869 2970 10731 7488 6037 10626 1857 10468 4808 13934 1665 524 13761 6913 11131 6533 6450 13283 8846 2192 3085 4659 15625 7186 8702 7868 15574 13006 5433 15106 15200 13925 15754 15087 5703 11805 4394 14900 11639 482 16374 15981 13914 5846 9129 14891 6046 8948 8055 9262 3710 7579 3221 13244 1261 5834 8974 11249 13886 10440 2827 7298 4889 3828 6843 10086 3613 15991 13196 7415 9810 10161 13047 6779 5581 14897 4773 5005 5678 8859 4705 16366 7234 2409 6338 7384 12277 10147 6158 13089 14902 3547 6556 6912 1446 903 13984 11248 2219 11938 13523 6047 14131 16158 11734 5077 750 7839 12529 11561 872 16302 14117 16235 6788 10486 1459 12458 5862 14107 8500 14122 13593 4099 14752 13738 759 14406 10805 11407 1190 9063 1113 7584 9308 13099 12128 2634 15072 7135 6432 3935 4151 13777 5424 15302 485 4466 7528 10146 6818 15614 13722 1974 13721 13141 8473 4003 13560 15252 1602 16284 6527 12699 13273 6157 7123 5346 14709 3428 6021 7900 1706 453 2561 522 11381 8582 2086 4182 5209 5060 14364 12960 8860 2261 11071 12281 16366 4873 490 14724 5787 13316 6781 11454 7631 9350 145 4892 12929 2696 7905 5614 7657 1552 7620 14518 4673 5417 7888 1007 3021 11485 5876 15614 9467 8306 994 11516 14429 9110 14698 13062 12151 6127 10440 702 7530 2176 10886 15590 15186 14608 4833 15807 1927 365 13804 3989 9797 12168 1595 6672 4708 14187 9113 13427 10801 4609 4736 1668 2617 11014 750 15469 4790 13094 12650 5009 7572 5474 14726 3715 3868 1454 12871 12359 2370 15110 4144 1727 14540 8047 6599 13683 5712 10003 13849 7881 16197 7709 14552 10653 8570 2922 15909 2769 11493 10275 2927 15764 12007 12649 10403 6967 5084 1472 9391 12468 3169 7635 9543 5983 8986 13449 2426 2396 3211 7339 5138 5976 4602 10724 16332 8393 803 2717 5589 11916 3683 768 11208 13783 4604 11652 6710 15136 3052 2147 9950 402 12751 14899 4628 14149 3193 8550 440 12406 11849 9065 6105 660 12025 9039 9021 3182 11127 5049 921 11643 10533 1029 2510 4847 6528 6152 7551 5148 12947 9782 12457 10321 25 2614 2588 16224 2742 7313 13968 2672 10907 8909 1219 16011 6408 15303 10611 4136 7089 4682 15474 2776 11301 12301 11418 4517 15109 9622 11463 1812 9866 15590 6043 7120 8502 13384 4637 6452 5448 2545 12691 15103 2384 15878 13320 13305 6374 13541 8176 11204 6456 11323 4774 13027 10389 6688 6454 9919 5857 550 13424 841 9109 8214 14773 9500 2324 3809 15518 1443 9436 7074 8801 8162 11035 11144 8956 10539 15073 7308 3708 14600 8808 1175 7140 1948 10180 14022 8159 2008 9107 6001 13296 14882 4692 2354 9060 1537 14804 308 14426 7589 10489 13330 3076 8383 4599 4975 3913 7990 6156 9090 1763 5954 13073 10543 258 11007 14332 8389 10672 1179 466 4202 5940 4480 14002 546 16349 11589 15639 15799 12266 12512 1749 1220 9414 8323 4366 11141 1876 4486 6018 9902 9955 7860 12001 3441 15725 16287 9478 361 4436 5491 15345 12067 12099 3124 12544 13173 926 523 11546 5562 12713 2219 14334 14421 7609 6941 863 11848 12928 6686 733 99 11290 12304 15336 3323 7280 11142 6073 14617 6446 999 871 7230 3141 8037 8496 4749 13056 2123 5445 10520 6490 1400 11927 15733 5772 5651 6087 2025 14189 14834 3548 11500 1746 16061 11302 10741 8336 15224 11885 1603 7123 7618 8788 13662 6616 13053 857 14772 8213 2631 2649 9136 4023 1946 13342 6868 206 5763 14813 1418 10558 13802 3311 15745 10373 9605 15853 13765 7173 11005 14441 16035 13498 6412 9622 15606 7046 8213 11082 10238 5959 8642 10974 12347 16174 8626 6855 705 7936 8741 8708 3972 3846 2917 16053 8303 6851 11423 15810 3874 4435 2549 10364 325 8573 6710 14089 4137 15855 12007 3582 7886 664 5370 828 2820 7942 12689 8456 8380 11731 10497 4026 11206 15992 9414 10658 3157 9719 22 14174 11323 5506 9890 8307 12761 12300 11734 9700 13115 211 7597 987 15405 2486 3284 8594 7042 7386 12131 5027 14487 15165 12350 3147 16038 5735 15248 2673 415 13205 8201 7545 16140 11662 710 4273 3528 15867 1717 2084 10364 9199 490 5027 9592 105 668 14786 3481 5398 7293 10769 14873 14989 3992 741 47 2561 1264 10548 3991 8839 13085 520 3438 1524 5258 11250 14907 15687 10864 3473 13975 10543 6440 6465 9331 1122 13576 15646 1379 12322 6382 10691 9303 9808 9441 6224 9678 7217 9815 2559 2540 9374 13553 13739 10585 11010 5254 2165 11608 5192 15779 1677 14967 5929 480 2004 12646 4823 6613 10076 4025 2403 15961 2276 1714 9486 7729 14382 8214 5315 6038 11049 3088 9368 13916 4476 12660 11596 14667 12104 862 9066 13582 265 10454 9661 10803 15127 12376 10150 11103 6269 7080 13992 6666 2220 16326 5987 9318 14566 12455 9343 7784 3964 13127 6073 5750 16100 4676 6846 6312 13332 10858 1887 14910 8274 3930 15394 11436 654 11696 7759 15680 11459 9026 5776 10295 9713 8688 11515 8875 2318 15064 6881 9179 16158 12612 16255 1393 13529 8425 11964 1186 983 12279 7106 10975 7243 10536 11579 8590 12663 3110 7653 15406 1888 14427 1668 7146 10548 7091 13798 10592 3961 2875 13926 3964 9370 1217 9792 9471 8373 13769 11547 13448 13707 9348 7508 8509 7608 14906 14851 563 1275 1422 6158 6255 2318 980 11512 9916 14465 10358 6394 10092 9643 7413 16126 11928 11767 11415 10469 8691 8079 16330 837 3229 11523 11854 2309 11412 9978 14582 12236 4381 11356 14796 14780 2372 9058 12111 9834 7147 4720 602 2923 15626 11415 1647 7642 6115 14153 4029 8131 10386 3628 2986 2891 7717 12016 4582 11110 4985 16359 7041 10328 4795 10481 13191 6364 74 5518 5904 5025 10983 412 9588 4217 14626 10281 11124 1234 14015 16173 4639 4312 11854 7395 3980 9782 12167 13027 307 13016 4498 6824 15262 2718 12655 7353 10852 2744 5447 915 9254 15191 8654 3665 3019 6256 12225 3292 3384 12341 1775 6837 11231 7187 14503 4127 7698 5196 10078 2117 3810 10205 10196 4898 11495 14268 3565 6415 6919 1688 1999 8755 13362 10869 11648 10206 8104 871 15532 10458 2485 4579 4674 723 10282 561 6638 8863 6214 8230 2879 1357 9328 7384 4404 15940 11374 8759 14412 3515 10665 5494 7373 12379 1928 5195 3041 2211 15762 3593 994 7914 9787 3199 469 7957 3279 1451 3578 16150 1148 6259 5395 7643 711 16243 2481 10493 11775 1630 2866 8774 12733 4166 1332 4775 1518 907 13729 11445 10265 7422 2309 5033 6811 12505 9666 15300 10858 10665 9789 1010 13137 1636 3648 6832 10263 14705 9409 3538 7007 9078 886 11701 6147 11992 14178 3617 6007 9346 13738 16063 2448 10278 11297 4177 3369 7301 7213 12517 6229 13231 13200 6929 12156 10058 8708 7509 10912 2700 6645 10276 15763 8192 1921 1739 13055 15026 1540 10544 6689 5802 14580 10477 8364 13351 1089 9361 5949 5870 2640 10924 8688 5893 12672 13606 15605 5495 2936 1808 13361 7591 13214 3038 12198 7347 2833 655 4452 7982 7723 1332 5799 12003 15241 15582 6803 9424 3341 1827 2487 8317 8003 3805 12399 5413 14783 3951 13404 4891 8099 2422 7617 9019 14571 1349 8551 11948 3300 13405 4572 6111 3616 14891 9502 1760 11045 12366 4605 434 1331 3728 6828 15440 8070 5352 8757 10564 10381 15907 4751 6779 14897 13373 14713 4349 10882 2151 1471 5095 3328 8437 6128 10740 1805 257 5569 7954 1953 3267 9721 7643 11470 8926 4672 11414 13979 119 6 4176 352 5429 12759 13757 14773 4907 12854 15978 5744 6239 11960 11554 13795 15631 874 6620 6097 6133 9034 2608 3415 9880 9394 8946 12723 8594 3285 9079 7362 14027 12533 314 13954 6656 5872 15728 13342 12531 15025 11387 4210 8557 4052 5929 15175 100 4213 2545 1157 1967 8612 14320 13278 12877 10965 7987 4362 3217 15212 14874 3559 916 6986 7749 6826 6131 14949 7010 5698 7905 10950 14507 14500 4698 10949 15144 11569 15109 14244 5160 9832 12912 11698 6632 7629 1803 12225 628 7226 6640 8457 10540 5561 10714 2000 5389 3376 2416 6780 14381 9423 10895 1371 4010 7157 12188 14507 8245 2314 10303 7796 3166 6496 14760 6508 6335 827 5169 9022 6063 9269 8350 4951 8132 7433 13200 8756 637 13909 8507 7397 5856 11737 15319 2988 10201 5757 10755 15371 11716 9370 667 15441 14034 9086 5602 10040 14821 7113 16080 15543 8416 8765 6463 6378 4151 4762 3115 2438 9365 3159 4418 4895 13926 9165 13411 461 13513 1815 3739 470 8176 5883 14724 12451 674 1455 1997 12224 11278 13821 9214 7315 14692 5027 12088 5806 14496 16093 14503 12120 10121 5316 7008 11198 15749 2033 11348 2308 14620 15347 1099 5407 7546 4491 5019 8635 350 8252 11395 2794 5255 11237 15987 14527 13478 10448 3737 6189 6106 768 11500 13687 439 12939 14016 15758 4978 11613 3706 9821 206 7137 2442 11828 16128 2126 8095 997 14385 2315 10810 15187 13585 10290 15567 6993 4027 7596 6179 10401 608 10358 15745 6018 4484 14416 16246 8964 16325 2865 10833 11070 584 1294 3925 1394 9094 12438 13372 5127 1483 15453 13366 11037 4240 4493 10044 4826 14705 15425 7239 8928 13977 14107 15850 1507 10935 15461 3173 10415 7437 6631 14401 5999 1266 2643 14884 6855 7337 2952 2275 12791 15969 13891 15185 11937 625 5032 7861 13865 15278 5694 1107 9906 2795 12727 13721 2629 16188 12504 11432 9847 13449 6607 3738 14112 8900 10352 15583 275 12527 685 7490 13332 2340 3558 14474 5590 6319 2346 14562 14187 12043 8862 5657 12182 6255 15605 6361 1642 3958 15239 13144 6165 1447 157 12187 2618 11911 7271 10953 5402 5264 2109 15526 14337 9667 2652 11923 3591 14611 11014 3678 1352 5872 12192 8966 11581 7862 14213 13566 1672 562 6961 9495 4125 3687 14727 4760 10488 9008 16372 12909 13878 8203 13365 7616 13932 6595 882 9772 14217 11729 9513 4268 2309 2326 11794 9752 11224 5051 8836 9991 9154 6811 7366 8347 4934 11816 1733 3954 13982 2909 12333 1568 11998 359 13006 10973 11646 13817 13693 10984 961 8164 1173 11033 6491 90 408 11513 4688 9101 8465 3641 9833 12879 9539 11731 8202 8141 8688 224 9411 2602 14366 14662 13809 8745 5974 3253 4604 13431 5204 4152 14835 14633 16119 15008 1565 14555 14028 8306 5713 14199 7200 15426 12030 10232 1287 5100 10447 1829 2872 12286 10190 13518 4666 4229 8480 5223 13555 2423 2333 10807 14694 15534 7849 10125 385 15672 7233 13891 6674 14311 2433 6229 8195 6511 4608 6370 564 16296 6191 4655 7118 824 13831 4808 9637 14457 11221 15592 5842 3319 8338 8367 13259 14152 12035 10471 15877 15288 10415 13600 5862 13632 3005 12477 690 3940 16131 847 6510 866 4937 9841 760 11944 4295 5738 9122 4327 12718 14493 13570 9810 6479 16204 2763 5094 9819 249 891 14007 2713 4366 6658 11713 5004 131 6209 6539 11358 15094 3871 12674 4187 375 9631 1020 7952 16240 13893 5170 12344 1031 6991 7685 372 7522 3321 3157 3110 6583 6048 2745 13885 10523 2511 10113 6551 282 5575 14183 16209 15800 2958 16036 1021 15085 10635 12315 5210 6619 6009 1390 3622 4758 3210 9162 15128 5634 15809 11554 12244 8766 9254 1072 8077 14890 13592 2993 1016 1431 5080 10986 4033 4723 6793 4950 9438 7716 15344 15190 11153 11272 7640 10202 7824 634 2167 9531 7093 11099 3516 9904 14885 15884 5054 213 12353 10045 2694 11674 7090 7738 16355 13009 11137 14701 7574 16164 7944 11102 4380 8421 89 14067 9934 741 8393 392 2433 3556 9373 9804 1907 4418 9163 11387 9858 15514 11234 7817 168 2367 1132 9327 13051 9362 2056 16287 8736 13183 3731 8435 8038 8168 13748 912 8982 14308 196 9665 4916 15007 511 9738 9204 15830 4078 3453 14959 14121 5040 5651 16219 588 2362 4659 16102 814 15031 9698 2784 10364 5590 10007 1429 10311 710 5555 7733 4102 3033 6462 16084 5230 4892 7168 4874 15737 16053 8091 2042 13095 7268 8775 4157 13344 7659 13316 11914 6304 1667 11251 4025 8332 9270 15944 11030 6428 16281 14898 7391 125 966 12312 15406 11485 1298 2153 4493 11225 15044 3861 3139 5960 4129 7391 4769 12754 6068 2314 4686 10900 2612 14123 10552 8786 13396 11117 3766 14347 13106 3862 13385 8960 4684 15931 6237 12241 16122 15051 2984 8035 12612 1473 13322 10590 3515 3003 7766 11152 13529 12235 1503 4400 1907 12710 2355 14647 2086 10836 12851 5509 10333 4897 10632 1121 16301 5110 14961 5105 13224 4372 7419 15279 9426 11673 13272 9976 11747 14084 7902 12561 6395 4813 15629 8639 9679 6697 9869 11881 7188 12538 3615 8132 15946 9054 8553 14330 6107 8637 12526 2767 9240 12804 2102 6914 9429 7673 14155 7658 6744 3120 6008 3109 7313 14495 3242 7100 8104 11070 7309 638 10415 342 660 14573 7531 918 682 2140 13474 15502 911 11176 14597 5702 9005 4143 735 12728 2245 3037 14549 4502 5758 1164 9577 9344 10320 12275 9634 5323 4638 14287 10532 371 5462 10321 13069 8772 4302 1733 11330 14645 5215 3139 8852 3812 16034 11688 11556 1039 3635 8071 2780 1878 2808 1801 12371 131 1256 9217 6402 574 700 1839 8526 9160 9714 8989 2893 11683 3558 8930 4777 816 4765 4474 6823 13505 11826 106 15535 2044 5874 5456 11121 9802 14445 6084 6348 2948 15658 7171 9570 7980 10480 1970 4187 15802 12124 10117 1156 9730 14478 15278 13181 10708 14867 6118 6566 1499 10390 4818 6654 3523 10963 8893 1575 5781 904 15362 598 2204 13994 501 2250 11072 10587 7137 14851 10235 13006 9783 9088 4921 6665 15411 13023 4575 75 6928 7781 1529 5259 864 5000 9434 3718 9092 798 6126 2217 11925 15979 1524 10725 18 6804 7264 14013 4642 830 14954 12793 978 469 10020 1687 1873 4989 14089 7700 12144 5448 5095 14579 12769 5539 13761 5604 15957 11101 14265 15710 14190 11536 14543 4727 6012 7447 1492 6992 5648 5501 12397 10881 13835 1388 3636 14284 8816 11799 7172 771 14702 6487 7168 2745 6488 3751 7774 6877 2956 8244 8406 847 2577 874 10618 14174 11273 3477 13183 16307 7023 6710 11360 8299 223 7320 10907 4000 8184 12059 11054 1249 14427 1347 14565 7837 3737 10742 690 15514 5098 5192 677 11088 8502 11649 13196 16260 5073 13308 15344 796 9757 14017 12794 4124 8186 10844 1023 5454 7480 3546 15711 3934 14457 1680 12989 885 10725 12622 15827 7474 2995 5355 9995 9634 3572 7459 10982 9770 9603 1221 4544 13914 16048 7326 12355 11652 874 1533 576 6323 9746 13161 2673 880 4271 3803 8548 10779 14108 2028 7499 7309 9960 6030 4855 9668 16110 48 5042 12236 799 14773 4663 13923 13631 14789 7194 3576 7724 177 16275 6675 970 12614 16300 3021 12241 14433 5880 8011 8448 5618 7049 9018 3489 15240 6443 945 12379 3016 3376 12638 6069 13413 10696 16035 6322 16181 13468 9207 8020 8259 8985 2440 8585 16133 6981 8706 16021 5946 10852 12295 10462 9958 15766 12232 3815 15254 9933 12342 14022 15744 295 3015 6150 16360 8538 4384 11101 1952 9180 8847 10117 2609 8301 4225 5261 15811 15995 3825 8458 3925 3488 14871 7004 14788 1802 12756 11077 2564 6376 1578 15151 12095 11861 5174 3226 3140 1513 1453 8233 4866 5480 2481 4908 7204 9277 15125 10284 13912 2169 11867 5571 2338 14598 10309 6856 12419 5563 8205 10673 12473 1574 2286 10199 5495 8992 7286 14200 15228 3472 7595 4150 9200 7639 7624 12766 14069 1263 15497 4700 15889 1917 9912 15865 1724 15900 9770 851 8662 14840 7958 1444 15984 5305 11105 2771 8998 4875 2167 10811 15687 2933 5240 12396 7822 7479 9608 11776 7488 892 9226 6273 16035 15979 8327 12760 13473 14345 15873 15918 5000 7820 804 6402 2494 3600 6815 6205 5216 7093 8675 15841 15736 651 1171 12975 5182 3224 9085 8213 8465 1029 16179 3667 1331 4371 12752 8149 14640 13499 7161 14498 8033 13949 15162 16119 1160 1827 764 3246 13784 5027 14419 12849 31 5615 15129 15837 5538 9894 13711 2603 6739 15527 8352 4054 13800 5670 2448 1692 11834 7981 6585 11117 6245 6984 2878 15645 5425 12383 10268 1864 9505 8374 10935 15558 12374 9687 15901 12881 8121 6941 4067 3201 4857 1900 9240 15648 3705 8564 12559 13008 11083 10589 10052 8551 9716 8629 14651 7097 391 6054 7033 2256 3359 10666 3884 7917 11202 6333 10296 6771 6219 4630 13061 8806 12092 15644 11067 5469 15353 3354 10763 14169 12614 1525 10028 5409 11967 6898 14235 8157 5001 11069 15971 5435 14502 12362 16352 10604 8473 4497 12934 15011 3934 15057 4822 7363 9753 6678 4129 15974 5678 15204 8439 16099 9807 14365 1004 8739 4219 6679 12351 6848 4406 14429 9720 1631 264 13005 14937 7821 3789 16126 14518 227 10377 2520 14604 11218 11933 1307 12453 16280 7682 925 1461 5663 13841 11885 12032 13987 13233 7177 6617 11681 2049 12938 3955 6691 13500 1097 6840 6170 1667 11965 12367 7038 8277 9768 14311 15075 16352 10277 8119 10729 565 115 13212 12466 5029 172 16152 4817 424 9730 9311 13824 10278 6158 13881 14842 2271 325 1171 9688 13147 5991 6784 8674 3211 13427 13330 2047 14961 5211 11715 8887 9937 16192 1282 11258 14164 8127 2515 3706 10438 13217 12850 2812 15769 7804 3749 11424 11910 13141 9135 12748 12798 8324 7129 6943 5953 7643 10543 4828 12143 8295 10601 10165 12977 10380 14155 16021 11248 3740 16071 3572 16294 5481 6240 13008 3068 5811 3139 14518 2717 78 14458 15621 9795 7735 11398 26 6893 2380 2563 5795 987 6479 4884 3097 15893 11630 6323 603 1704 1491 14942 3421 9855 8773 10204 13004 9317 12515 13759 15972 5898 14945 12471 14686 5261 5503 11772 7366 5180 7772 7705 13627 14 6848 12100 14080 12428 6388 5718 13619 14719 9463 8034 11984 9936 13967 5960 781 13724 9677 9579 13395 485 5190 10508 14304 2950 579 9877 11049 10755 3554 4321 2490 15857 4836 7728 3325 15468 6162 1836 1778 2794 5843 14655 11550 12341 7958 16072 4297 12698 6240 4617 10021 12034 10981 3449 4403 205 13002 4649 5548 14821 8669 14855 6127 2021 6453 14639 5699 10695 15263 7165 7397 14376 1739 1487 13978 9584 3937 9297 15976 5949 13250 11442 5433 840 5014 8065 2666 10368 7748 401 5666 4578 1969 189 2049 14555 10443 1917 3417 7421 11675 2833 4976 12620 11484 15834 9852 12245 15595 1660 11719 470 14053 5936 10155 10554 9370 143 9630 1547 8581 10604 15016 2571 4041 4707 1743 15328 6732 4232 3664 7587 13246 4963 1887 5970 6996 11488 12958 8346 3260 14269 13437 6129 6074 1699 6413 4278 10237 9219 8559 10169 1449 4700 5015 3997 1531 424 2795 2931 2791 12101 12464 12907 10159 1824 13926 1204 8294 3119 1267 1604 5535 10542 14735 4384 4957 9834 2051 8297 2803 9622 494 7769 1945 13910 12944 2867 7544 2940 7883 4247

 
";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }

    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0