wkb97.java

package weekly;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class wkb97 {
    //ranking: 757 / 2631

    //模拟
    public int[] separateDigits(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            List<Integer> l = new ArrayList<>();
            while (num > 0) {
                l.add(num % 10);
                num /= 10;
            }
            for (int i = l.size() - 1; i >= 0; i--) {
                list.add(l.get(i));
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    //哈希
    public int maxCount(int[] banned, int n, int maxSum) {

        Set<Integer> set = new HashSet<>();
        for (int i : banned) {
            set.add(i);
        }
        int sum = 0;
        int res = 0;
        for (int i = 1; i <= n && sum < maxSum; i++) {
            if (!set.contains(i)) {
                if (sum + i <= maxSum) {
                    sum += i;
                    res++;
                } else {
                    break;
                }
            }
        }
        return res;
    }

   /* public int maximizeWin(int[] prizePositions, int k) {
        int n = prizePositions[prizePositions.length-1];
        int[] dp = new int[n + 1];
        for (int prizePosition : prizePositions) {
            dp[prizePosition]++;
        }
        int right = 1;
        int sum = 0;
        while (right < dp.length && right <= k+1) {
            sum += dp[right];
            right++;
        }
        for (int i = 1; i < prizePositions.length; i++) {
            int val=dp[i];
            dp[i] = sum;
            if (right < dp.length) {
                sum += dp[right++];
            }
            sum -= val;
        }
        int[] max = new int[n + 1];
        for (int i = max.length - 2; i >= 0; i--) {
            max[i]=dp[i];
            max[i] = Math.max(max[i], max[i + 1]);
        }
        int res = max[0];
        for (int i = k+1; i < dp.length; i++) {
            res=Math.max(dp[i-k]+(i+1<dp.length?max[i+1]:0),res);
        }
        return res;

    }*/


    //滑动窗口
    public int maximizeWin(int[] prizePositions, int k) {

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int prizePosition : prizePositions) {
            map.put(prizePosition, map.getOrDefault(prizePosition, 0) + 1);
        }
        int[][] arr = new int[map.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            arr[i][0] = entry.getKey();
            arr[i][1] = entry.getValue();
            i++;
        }

        int right = 0;
        int sum = 0;
        int max = 0;
        Map<Integer, Integer> M = new HashMap<>();
        int res = 0;
        for (i = 0; i < arr.length; i++) {
            while (right < arr.length && arr[right][0] <= arr[i][0] + k) {
                sum += arr[right][1];
                //求（截止到i-1 + 从i开始）的线段和
                max = Math.max(max, sum);
                //记录截止到right-1的最大线段和
                M.put(right , max);
                right++;
            }

            res = Math.max(res, sum + M.getOrDefault(i - 1, 0));
            sum -= arr[i][1];
        }
        return res;
    }

    public static void main(String[] args) {
        wkb97 w = new wkb97();
        w.maximizeWin(new int[]{42422, 42429, 42430, 42432, 42432, 42444, 42445, 42448, 42448, 42449, 42449, 42450, 42455, 42457, 42461, 42465, 42470, 42471, 42471, 42473, 42473, 42476, 42477, 42478, 42479, 42495, 42513, 42518, 42518, 42530, 42532, 42535, 42538, 42538, 42546, 42551, 42552, 42553, 42557, 42560, 42562, 42563, 42563, 42564, 42577, 42579, 42588, 42589, 42597, 42608, 42615, 42616, 42628, 42630, 42632, 42633, 42638, 42642, 42645, 42649, 42655, 42655, 42655, 42657, 42657, 42660, 42666, 42671, 42673, 42674, 42681, 42687, 42691, 42696, 42699, 42707, 42708, 42717, 42728, 42728, 42730, 42737, 42740, 42740, 42742, 42742, 42744, 42745, 42754, 42761, 42766, 42772, 42775, 42777, 42778, 42778, 42778, 42788, 42794, 42800, 42800, 42801, 42807, 42809, 42809, 42811, 42814, 42816, 42817, 42822, 42823, 42823, 42833, 42840, 42841, 42846, 42850, 42853, 42853, 42854, 42857, 42859, 42861, 42862, 42862, 42865, 42866, 42866, 42870, 42876, 42884, 42884, 42886, 42891, 42892, 42894, 42897, 42900, 42902, 42908, 42913, 42919, 42919, 42922, 42924, 42931, 42933, 42934, 42940, 42944, 42945, 42946, 42949, 42951, 42953, 42955, 42960, 42963, 42966, 42967, 42974, 42974, 42976, 42981, 42983, 42986, 42988, 42994, 42999, 43003, 43004, 43009, 43009, 43019, 43020, 43023, 43028, 43029, 43036, 43041, 43045, 43052, 43052, 43054, 43054, 43059, 43061, 43063, 43065, 43066, 43069, 43082, 43082, 43082, 43087, 43095, 43096, 43097, 43098, 43104, 43115, 43126, 43131, 43136, 43139, 43147, 43147, 43147, 43148, 43150, 43159, 43160, 43164, 43165, 43168, 43171, 43174, 43175, 43176, 43181, 43181, 43182, 43182, 43185, 43189, 43190, 43190, 43196, 43197, 43201, 43203, 43214, 43217, 43217, 43222, 43223, 43223, 43227, 43227, 43234, 43237, 43238, 43238, 43246, 43248, 43248, 43250, 43253, 43258, 43259, 43262, 43264, 43267, 43267, 43268, 43269, 43271, 43271, 43275, 43277, 43282, 43283, 43285, 43288, 43289, 43290, 43292, 43292, 43295, 43296, 43298, 43302, 43304, 43306, 43315, 43318, 43319, 43322, 43329, 43331, 43332, 43338, 43339, 43342, 43348, 43363, 43363, 43365, 43370, 43376, 43379, 43379, 43386, 43386, 43387, 43390, 43399, 43401, 43404, 43418, 43421, 43424, 43434, 43436, 43437, 43439, 43439, 43440, 43441, 43441, 43442, 43446, 43450, 43452, 43453, 43459, 43463, 43470, 43471, 43475, 43481, 43486, 43487, 43499, 43504, 43507, 43508, 43513, 43516, 43521, 43530, 43542, 43543, 43543, 43543, 43552, 43553, 43553, 43560, 43568, 43570, 43577, 43588, 43588, 43593, 43595, 43598, 43600, 43608, 43612, 43620, 43637, 43646, 43647, 43649, 43650, 43650, 43658, 43659, 43661, 43676, 43677, 43680, 43685, 43690, 43691, 43691, 43697, 43708, 43708, 43709, 43709, 43711, 43721, 43723, 43723, 43728, 43729, 43732, 43733, 43737, 43739, 43741, 43750, 43754, 43757, 43760, 43761, 43775, 43792, 43797, 43814, 43816, 43819, 43829, 43831, 43832, 43838, 43843, 43845, 43848, 43848, 43852, 43854, 43859, 43861, 43864, 43873, 43877, 43881, 43882, 43883, 43888, 43890, 43897, 43905, 43907, 43908, 43911, 43914, 43915, 43922, 43923, 43924, 43924, 43931, 43932, 43933, 43933, 43938, 43943, 43951, 43951, 43965, 43968, 43971, 43976, 43979, 43981, 43982, 43982, 43985, 43986, 43992, 44004, 44008, 44008, 44009, 44014, 44016, 44019, 44020, 44028, 44030, 44030, 44032, 44032, 44034, 44039, 44039, 44045, 44045, 44048, 44048, 44049, 44052, 44053, 44053, 44055, 44060, 44070, 44072, 44074, 44076, 44079, 44086, 44093, 44095, 44096, 44098, 44100, 44105, 44110, 44113, 44113, 44119, 44124, 44124, 44131, 44134, 44140, 44141, 44145, 44150, 44155, 44169, 44169, 44170, 44174, 44175, 44177, 44179, 44180, 44182, 44191, 44192, 44195, 44203, 44204, 44205, 44206, 44211, 44213, 44226, 44230, 44233, 44243, 44250, 44252, 44254, 44255, 44255, 44257, 44257, 44260, 44260, 44260, 44265, 44266, 44270, 44273, 44274, 44280, 44282, 44285, 44286, 44290, 44292, 44297, 44302, 44308, 44310, 44312, 44313, 44321, 44322, 44324, 44325, 44327, 44334, 44338, 44340, 44340, 44346, 44347, 44349, 44358, 44362, 44367, 44368, 44379, 44383, 44384, 44402, 44402, 44404, 44414, 44422, 44427, 44428, 44428, 44430, 44435, 44436, 44438, 44444, 44445, 44447, 44448, 44452, 44459, 44462, 44463, 44469, 44476, 44477, 44478, 44480, 44482, 44485, 44495, 44497, 44498, 44503, 44518, 44526, 44530, 44534, 44538, 44549, 44550, 44571, 44574, 44583, 44583, 44584, 44587, 44589, 44592, 44593, 44594, 44595, 44604, 44612, 44616, 44620, 44623, 44632, 44635, 44636, 44642, 44647, 44647, 44654, 44660, 44668, 44669, 44676, 44676, 44677, 44684, 44692, 44693, 44703, 44705, 44708, 44711, 44712, 44718, 44727, 44730, 44733, 44734, 44735, 44737, 44738, 44744, 44747, 44748, 44752, 44756, 44764, 44768, 44769, 44770, 44772, 44775, 44775, 44780, 44781, 44784, 44784, 44785, 44790, 44791, 44792, 44797, 44798, 44804, 44808, 44810, 44811, 44814, 44815, 44833, 44836, 44840, 44841, 44842, 44843, 44845, 44852, 44859, 44872, 44875, 44875, 44886, 44887, 44893, 44897, 44898, 44901, 44902, 44906, 44907, 44908, 44914, 44914, 44917, 44923, 44930, 44935, 44935, 44936, 44938, 44939, 44943, 44946, 44947, 44967, 44974, 44979, 44985, 44985, 44988, 44989, 44989, 44990, 44999, 44999, 45001, 45001, 45012, 45015, 45016, 45019, 45026, 45027, 45030, 45034, 45037, 45053, 45053, 45053, 45054, 45054, 45057, 45058, 45065, 45068, 45069, 45071, 45071, 45076, 45082, 45083, 45084, 45084, 45085, 45091, 45099, 45102, 45102, 45104, 45108, 45112, 45113, 45134, 45135, 45136, 45142, 45144, 45149, 45153, 45154, 45154, 45159, 45162, 45168, 45172, 45175, 45176, 45179, 45181, 45182, 45186, 45191, 45194, 45196, 45200, 45203, 45204, 45204, 45208, 45210, 45210, 45217, 45219, 45223, 45228, 45233, 45236, 45236, 45239, 45240, 45243, 45248, 45253, 45255, 45259, 45261, 45261, 45268, 45269, 45284, 45297, 45299, 45302, 45305, 45310, 45314, 45316, 45322, 45324, 45329, 45336, 45343, 45345, 45349, 45349, 45351, 45352, 45355, 45361, 45363, 45366, 45373, 45379, 45383, 45388, 45391, 45391, 45391, 45392, 45399, 45402, 45404, 45410, 45411, 45411, 45413, 45437, 45438, 45441, 45448, 45456, 45460, 45467, 45475, 45479, 45480, 45483, 45483, 45484, 45488, 45493, 45495, 45497, 45497, 45500, 45506, 45509, 45514, 45516, 45523, 45528, 45531, 45535, 45545, 45551, 45551, 45553, 45557, 45560, 45560, 45562, 45571, 45571, 45578, 45583, 45586, 45586, 45588, 45588, 45592, 45594, 45598, 45603, 45606, 45606, 45606, 45613, 45616, 45616, 45617, 45622, 45629, 45631, 45633, 45638, 45639, 45644, 45646, 45654, 45655, 45657, 45659, 45660, 45663, 45663, 45666, 45667, 45667, 45668, 45678, 45681, 45684, 45685, 45685, 45694, 45699, 45700, 45707, 45712, 45717, 45718, 45720, 45721, 45723, 45725, 45726, 45728, 45734, 45735, 45735, 45737, 45743, 45745, 45746, 45758, 45760, 45767, 45771, 45777, 45779, 45786, 45795, 45795, 45798, 45800, 45802, 45802, 45805, 45808, 45811, 45814, 45815, 45821, 45825, 45828, 45828, 45829, 45830, 45837, 45845, 45847, 45847, 45848, 45854, 45855, 45858, 45858, 45862, 45862, 45863, 45863, 45864, 45871, 45872, 45873, 45883, 45883, 45884, 45885, 45886, 45891, 45891, 45893, 45893, 45900, 45902, 45903, 45915, 45917, 45919, 45923, 45928, 45929, 45940, 45949, 45951, 45953, 45956, 45964, 45966, 45967, 45975, 45976, 45981, 45981, 45981, 45990, 45992, 45992, 45994, 46003, 46009, 46012, 46029, 46029, 46031, 46032, 46035, 46045, 46048, 46054, 46055, 46056, 46056, 46057, 46058, 46059, 46059, 46062, 46065, 46066, 46068, 46069, 46071, 46082, 46082, 46084, 46084, 46091, 46092, 46095, 46099, 46102, 46106, 46110, 46115, 46118, 46138, 46142, 46144, 46144, 46145, 46149, 46149, 46155, 46155, 46162, 46163, 46163, 46168, 46168, 46170, 46177, 46185, 46192, 46193, 46194, 46194, 46199, 46201, 46203, 46203, 46215, 46217, 46220, 46221, 46226, 46227, 46229, 46232, 46235, 46240, 46241, 46256, 46257, 46259, 46262, 46264, 46268, 46270, 46276, 46284, 46285, 46291, 46296, 46304, 46304, 46307, 46308, 46311, 46314, 46321, 46323, 46325, 46327, 46332, 46338, 46349, 46350, 46353, 46354, 46365, 46365, 46367, 46371, 46373, 46386, 46389, 46393, 46394, 46401, 46403, 46405, 46412, 46415, 46417, 46420, 46422, 46428, 46435, 46436, 46436, 46445, 46447, 46451, 46452, 46453, 46455, 46457, 46461, 46467, 46470, 46479, 46488, 46490, 46493, 46497, 46503, 46506, 46507, 46511, 46517, 46519, 46521, 46526, 46526, 46527, 46530, 46543, 46557, 46563, 46563, 46579, 46584, 46586, 46588, 46595, 46595, 46597, 46599, 46616, 46620, 46629, 46635, 46643, 46648, 46659, 46659, 46663, 46664, 46669, 46670, 46670, 46670, 46673, 46675, 46676, 46684, 46684, 46686, 46691, 46691, 46691, 46697, 46702, 46704, 46704, 46707, 46725, 46731, 46733, 46734, 46737, 46738, 46744, 46745, 46745, 46745, 46748, 46748, 46751, 46751, 46752, 46759, 46760, 46760, 46762, 46764, 46766, 46772, 46775, 46776, 46779, 46779, 46781, 46781, 46789, 46789, 46790, 46792, 46802, 46802, 46803, 46809, 46812, 46813, 46814, 46821, 46832, 46837, 46838, 46839, 46843, 46844, 46847, 46853, 46856, 46859, 46864, 46865, 46866, 46866, 46867, 46879, 46880, 46881, 46882, 46887, 46890, 46893, 46908, 46909, 46916, 46916, 46918, 46919, 46920, 46930, 46950, 46950, 46951, 46952, 46962, 46962, 46963, 46967, 46974, 46982, 46985, 46987, 46987, 46992, 46994, 46995, 46999, 47003, 47012, 47022, 47038, 47050, 47058, 47062, 47067, 47076, 47082, 47088, 47089, 47093, 47098, 47102, 47105, 47113, 47114, 47120, 47127, 47134, 47137, 47137, 47141, 47147, 47147, 47149, 47150, 47150, 47152, 47156, 47158, 47160, 47167, 47167, 47171, 47173, 47176, 47178, 47183, 47185, 47192, 47195, 47198, 47205, 47209, 47212, 47213, 47213, 47222, 47236, 47237, 47244, 47250, 47253, 47257, 47260, 47264, 47270, 47276, 47279, 47279, 47282, 47288, 47291, 47292, 47298, 47306, 47310, 47312, 47328, 47329, 47336, 47337, 47352, 47355, 47365, 47366, 47367, 47367, 47368, 47374, 47376, 47377, 47378, 47384, 47384, 47385, 47388, 47389, 47396, 47397, 47400, 47400, 47401, 47402, 47408, 47410, 47410, 47416, 47418, 47420, 47422, 47424, 47433, 47436, 47436, 47439, 47442, 47443, 47449, 47453, 47456, 47456, 47457, 47457, 47467, 47469, 47471, 47475, 47476, 47477, 47479, 47485, 47487, 47489, 47497, 47499, 47499, 47499, 47512, 47513, 47514, 47522, 47529, 47529, 47532, 47539, 47544, 47546, 47547, 47547, 47556, 47558, 47562, 47562, 47567, 47567, 47569, 47569, 47570, 47576, 47576, 47577, 47579, 47580, 47581, 47585, 47585, 47588, 47590, 47592, 47593, 47595, 47598, 47599, 47606, 47609, 47610, 47610, 47613, 47614, 47626, 47631, 47632, 47633, 47634, 47634, 47636, 47637, 47643, 47656, 47664, 47670, 47671, 47672, 47676, 47678, 47693, 47694, 47699, 47701, 47703, 47706, 47706, 47711, 47717, 47719, 47722, 47723, 47726, 47727, 47740, 47744, 47746, 47765, 47771, 47774, 47775, 47785, 47787, 47789, 47797, 47800, 47801, 47802, 47811, 47830, 47833, 47835, 47838, 47842, 47846, 47849, 47850, 47858, 47860, 47866, 47873, 47874, 47876, 47879, 47879, 47880, 47906, 47910, 47915, 47915, 47915, 47920, 47920, 47928, 47931, 47935, 47939, 47947, 47949, 47951, 47953, 47959, 47962, 47964, 47970, 47971, 47974, 47974, 47975, 47980, 47987, 47991, 47994, 48005, 48011, 48013, 48013, 48017, 48018, 48018, 48019, 48027, 48028, 48040, 48043, 48048, 48049, 48049, 48049, 48060, 48063, 48064, 48065, 48065, 48066, 48071, 48075, 48076, 48080, 48086, 48090, 48092, 48094, 48096, 48097, 48097, 48097, 48097, 48104, 48116, 48122, 48125, 48126, 48130, 48132, 48133, 48133, 48135, 48136, 48146, 48150, 48153, 48158, 48158, 48191, 48196, 48196, 48199, 48205, 48206, 48206, 48213, 48219, 48228, 48228, 48229, 48229, 48231, 48237, 48239, 48245, 48248, 48248, 48250, 48258, 48260, 48264, 48268, 48270, 48270, 48276, 48282, 48309, 48319, 48320, 48322, 48322, 48328, 48333, 48335, 48338, 48342, 48343, 48353, 48353, 48353, 48353, 48358, 48364, 48379, 48379, 48404, 48411, 48411, 48419, 48419, 48428, 48432, 48435, 48435, 48438, 48439, 48447, 48454, 48455, 48455, 48459, 48460, 48461, 48463, 48464, 48465, 48466, 48472, 48474, 48475, 48484, 48487, 48488, 48494, 48497, 48497, 48499, 48504, 48504, 48505, 48506, 48511, 48517, 48522, 48523, 48523, 48524, 48535, 48541, 48542, 48545, 48548, 48550, 48560, 48564, 48581, 48582, 48584, 48587, 48590, 48599, 48604, 48605, 48606, 48608, 48618, 48619, 48624, 48624, 48632, 48634, 48649, 48650, 48650, 48651, 48652, 48663, 48667, 48677, 48678, 48686, 48699, 48700, 48701, 48703, 48712, 48714, 48724, 48725, 48735, 48737, 48738, 48738, 48741, 48741, 48744, 48744, 48745, 48750, 48760, 48765, 48772, 48777, 48777, 48778, 48781, 48787, 48790, 48794, 48797, 48799, 48801, 48803, 48804, 48805, 48809, 48812, 48814, 48817, 48819, 48821, 48822, 48830, 48837, 48843, 48852, 48854, 48859, 48860, 48865, 48869, 48870, 48871, 48875, 48879, 48882, 48888, 48889, 48889, 48891, 48893, 48893, 48895, 48899, 48899, 48902, 48908, 48912, 48922, 48928, 48931, 48934, 48936, 48937, 48938, 48945, 48946, 48948, 48950, 48954, 48960, 48961, 48964, 48968, 48973, 48985, 49004, 49006, 49006, 49014, 49014, 49017, 49018, 49018, 49019, 49019, 49024, 49027, 49028, 49030, 49031, 49035, 49038, 49039, 49050, 49056, 49057, 49066, 49069, 49072, 49074, 49078, 49080, 49085, 49099, 49100, 49110, 49111, 49115, 49115, 49115, 49122, 49123, 49131, 49133, 49133, 49138, 49149, 49149, 49162, 49166, 49167, 49174, 49175, 49176, 49181, 49184, 49187, 49191, 49197, 49202, 49202, 49205, 49214, 49216, 49231, 49233, 49234, 49239, 49246, 49246, 49250, 49252, 49256, 49259, 49261, 49261, 49261, 49263, 49264, 49270, 49284, 49299, 49299, 49301, 49307, 49311, 49311, 49313, 49317, 49320, 49321, 49322, 49327, 49330, 49334, 49338, 49341, 49345, 49360, 49364, 49372, 49373, 49376, 49376, 49379, 49382, 49390, 49393, 49398, 49400, 49400, 49404, 49411, 49414, 49422, 49428, 49429, 49439, 49447, 49453, 49460, 49464, 49466, 49468, 49472, 49480, 49486, 49487, 49489, 49489, 49493, 49499, 49500, 49500, 49502, 49503, 49505, 49507, 49510, 49524, 49525, 49529, 49531, 49536, 49536, 49537, 49537, 49539, 49544, 49546, 49556, 49558, 49562, 49565, 49577, 49579, 49586, 49590, 49603, 49606, 49609, 49609, 49613, 49623, 49626, 49626, 49631, 49633, 49634, 49640, 49642, 49647, 49661, 49668, 49674, 49689, 49691, 49693, 49695, 49697, 49702, 49709, 49711, 49714, 49716, 49717, 49717, 49720, 49721, 49722, 49722, 49730, 49733, 49741, 49746, 49749, 49751, 49761, 49763, 49766, 49767, 49771, 49782, 49785, 49790, 49795, 49795, 49796, 49803, 49804, 49805, 49806, 49811, 49812, 49817, 49817, 49817, 49818, 49823, 49824, 49829, 49834, 49842, 49847, 49848, 49849, 49853, 49856, 49857, 49860, 49861, 49862, 49866, 49880, 49891, 49893, 49896, 49896, 49897, 49900, 49913, 49919, 49919, 49921, 49921, 49922, 49923, 49939, 49948, 49949, 49951, 49959, 49962, 49967, 49971, 49973, 49977, 49980, 50002, 50003, 50005, 50006, 50007, 50013, 50017, 50018, 50019, 50030, 50030, 50035, 50046, 50049, 50050, 50051, 50059, 50061, 50063, 50070, 50072, 50072, 50081, 50082, 50082, 50092, 50094, 50097, 50098, 50099, 50100, 50110, 50113, 50115, 50117, 50118, 50121, 50125, 50127, 50129, 50129, 50129, 50130, 50142, 50142, 50143, 50148, 50153, 50165, 50167, 50168, 50175, 50185, 50186, 50187, 50194, 50202, 50206, 50207, 50210, 50214, 50219, 50222, 50223, 50224, 50225, 50229, 50229, 50232, 50233, 50234, 50236, 50240, 50242, 50243, 50244, 50255, 50257, 50257, 50260, 50262, 50263, 50266, 50267, 50272, 50272, 50277, 50277, 50279, 50289, 50294, 50294, 50296, 50298, 50300, 50313, 50319, 50320, 50321, 50321, 50328, 50331, 50333, 50344, 50344, 50345, 50347, 50347, 50355, 50356, 50358, 50361, 50361, 50375, 50376, 50377, 50377, 50380, 50382, 50382, 50383, 50386, 50388, 50389, 50392, 50393, 50397, 50399, 50403, 50416, 50417, 50420, 50422, 50424, 50424, 50431, 50431, 50433, 50434, 50435, 50438, 50441, 50441, 50442, 50445, 50448, 50453, 50453, 50454, 50463, 50466, 50470, 50472, 50473, 50480, 50488, 50488, 50490, 50491, 50492, 50502, 50502, 50503, 50510, 50515, 50518, 50523, 50525, 50528, 50532, 50538, 50538, 50540, 50545, 50546, 50552, 50557, 50565, 50566, 50572, 50572, 50578, 50582, 50584, 50586, 50598, 50607, 50612, 50619, 50620, 50628, 50631, 50635, 50637, 50641, 50643, 50654, 50656, 50658, 50660, 50662, 50663, 50670, 50691, 50696, 50707, 50708, 50709, 50714, 50717, 50721, 50726, 50733, 50735, 50735, 50737, 50737, 50738, 50740, 50741, 50744, 50758, 50760, 50761, 50765, 50772, 50774, 50776, 50777, 50779, 50779, 50780, 50782, 50788, 50789, 50808, 50813, 50827, 50828, 50830, 50832, 50841, 50849, 50851, 50851, 50853, 50854, 50854, 50857, 50858, 50858, 50860, 50867, 50871, 50871, 50878, 50879, 50882, 50884, 50886, 50886, 50887, 50888, 50890, 50891, 50893, 50897, 50900, 50913, 50915, 50917, 50924, 50940, 50941, 50942, 50944, 50951, 50954, 50954, 50954, 50956, 50959, 50969, 50970, 50972, 50981, 50982, 50989, 50994, 50994, 50995, 50995, 50997, 51002, 51010, 51015, 51017, 51021, 51024, 51026, 51028, 51028, 51031, 51033, 51037, 51037, 51040, 51040, 51045, 51051, 51053, 51058, 51060, 51064, 51066, 51066, 51070, 51071, 51091, 51098, 51110, 51111, 51116, 51117, 51134, 51138, 51139, 51139, 51150, 51150, 51152, 51153, 51155, 51164, 51166, 51166, 51170, 51180, 51183, 51185, 51186, 51188, 51197, 51202, 51205, 51205, 51210, 51215, 51222, 51227, 51227, 51230, 51234, 51234, 51249, 51251, 51255, 51257, 51257, 51272, 51274, 51276, 51278, 51279, 51282, 51285, 51286, 51286, 51290, 51292, 51295, 51299, 51300, 51310, 51312, 51313, 51315, 51316, 51324, 51335, 51341, 51345, 51348, 51352, 51354, 51358, 51359, 51359, 51359, 51361, 51362, 51364, 51368, 51374, 51381, 51384, 51385, 51396, 51398, 51400, 51407, 51416, 51418, 51419, 51423, 51428, 51430, 51432, 51434, 51435, 51437, 51444, 51446, 51451, 51453, 51454, 51454, 51458, 51463, 51476, 51478, 51481, 51491, 51493, 51495, 51499, 51500, 51500, 51500, 51500, 51501, 51503, 51504, 51513, 51520, 51527, 51530, 51536, 51539, 51541, 51547, 51551, 51553, 51555, 51559, 51564, 51564, 51570, 51572, 51579, 51580, 51587, 51588, 51591, 51591, 51593, 51594, 51594, 51595, 51599, 51603, 51616, 51636, 51639, 51640, 51640, 51643, 51644, 51652, 51664, 51668, 51677, 51679, 51681, 51684, 51686, 51691, 51691, 51697, 51705, 51706, 51710, 51710, 51718, 51724, 51726, 51738, 51738, 51738, 51739, 51742, 51743, 51749, 51752, 51756, 51759, 51763, 51764, 51765, 51767, 51767, 51783, 51786, 51789, 51790, 51805, 51806, 51807, 51811, 51816, 51821, 51824, 51825, 51835, 51835, 51836, 51836, 51838, 51839, 51846, 51848, 51849, 51862, 51875, 51875, 51875, 51879, 51881, 51884, 51885, 51893, 51899, 51911, 51913, 51918, 51922, 51923, 51924, 51929, 51933, 51936, 51936, 51938, 51938, 51939, 51942, 51945, 51946, 51948, 51949, 51953, 51960, 51961, 51964, 51965, 51965, 51969, 51972, 51980, 51988, 51988, 51992, 51994, 51998, 52000, 52017, 52028, 52028, 52033, 52042, 52043, 52050, 52055, 52060, 52066, 52070, 52071, 52071, 52074, 52075, 52075, 52077, 52081, 52084, 52088, 52092, 52101, 52102, 52103, 52110, 52114, 52114, 52115, 52116, 52118, 52129, 52130, 52134, 52134, 52137, 52138, 52138, 52143, 52146, 52148, 52148, 52149, 52151, 52155, 52157, 52158, 52159, 52172, 52174, 52176, 52177, 52184, 52187, 52187, 52187, 52189, 52192, 52193, 52197, 52206, 52207, 52209, 52210, 52214, 52217, 52217, 52224, 52226, 52228, 52228, 52228, 52232, 52233, 52241, 52243, 52243, 52249, 52250, 52261, 52265, 52267, 52286, 52286, 52291, 52296, 52298, 52301, 52303, 52304, 52307, 52307, 52314, 52317, 52348, 52350, 52360, 52363, 52363, 52364, 52365, 52366, 52368, 52373, 52374, 52381, 52383, 52385, 52385, 52396, 52401, 52401, 52403, 52413, 52414, 52416, 52421, 52422, 52425, 52432, 52446, 52446, 52448, 52450, 52454, 52467, 52468, 52469, 52470, 52471, 52471, 52473, 52481, 52483, 52487, 52488, 52489, 52497, 52500, 52502, 52504, 52510, 52512, 52515, 52521, 52523, 52524, 52527, 52531, 52533, 52534, 52534, 52547, 52547, 52549, 52550, 52551, 52556, 52559, 52560, 52565, 52567, 52567, 52571, 52576, 52584, 52585, 52587, 52594, 52601, 52602, 52604, 52609, 52611, 52612, 52612, 52613, 52614, 52614, 52618, 52619, 52621, 52635, 52642, 52644, 52649, 52658, 52666, 52671, 52673, 52675, 52679, 52679, 52679, 52681, 52687, 52687, 52689, 52692, 52693, 52705, 52710, 52713, 52723, 52729, 52736, 52738, 52743, 52745, 52747, 52750, 52750, 52751, 52755, 52758, 52762, 52764, 52771, 52773, 52775, 52776, 52777, 52782, 52782, 52787, 52794, 52794, 52795, 52796, 52799, 52801, 52810, 52812, 52814, 52819, 52827, 52832, 52833, 52838, 52838, 52844, 52846, 52847, 52847, 52851, 52870, 52878, 52878, 52884, 52884, 52887, 52887, 52895, 52897, 52901, 52902, 52904, 52909, 52910, 52911, 52912, 52917, 52922, 52924, 52929, 52930, 52933, 52942, 52943, 52947, 52948, 52949, 52957, 52965, 52991, 52993, 52994, 52994, 52995, 53020, 53023, 53024, 53029, 53034, 53044, 53046, 53048, 53054, 53058, 53059, 53068, 53070, 53072, 53074, 53075, 53077, 53078, 53083, 53084, 53085, 53102, 53105, 53111, 53112, 53112, 53115, 53122, 53125, 53131, 53131, 53131, 53133, 53135, 53137, 53153, 53153, 53157, 53158, 53160, 53163, 53166, 53169, 53169, 53169, 53175, 53175, 53182, 53196, 53197, 53202, 53202, 53209, 53216, 53218, 53219, 53224, 53225, 53225, 53229, 53232, 53240, 53245, 53245, 53248, 53253, 53256, 53261, 53268, 53270, 53275, 53290, 53291, 53293, 53294, 53294, 53296, 53298, 53305, 53305, 53308, 53308, 53310, 53317, 53318, 53318, 53320, 53321, 53323, 53327, 53327, 53341, 53343, 53347, 53348, 53348, 53352, 53356, 53363, 53365, 53366, 53370, 53373, 53383, 53384, 53388, 53391, 53394, 53400, 53410, 53413, 53416, 53431, 53443, 53454, 53454, 53455, 53466, 53468, 53470, 53474, 53484, 53487, 53487, 53495, 53496, 53503, 53503, 53514, 53516, 53516, 53522, 53526, 53527, 53532, 53533, 53535, 53541, 53549, 53551, 53552, 53560, 53577, 53579, 53583, 53589, 53593, 53598, 53598, 53600, 53610, 53614, 53618, 53632, 53633, 53633, 53633, 53638, 53639, 53643, 53643, 53646, 53654, 53671, 53677, 53683, 53686, 53688, 53691, 53693, 53693, 53699, 53706, 53710, 53711, 53711, 53711, 53716, 53721, 53721, 53728, 53731, 53736, 53739, 53740, 53744, 53745, 53749, 53750, 53751, 53753, 53759, 53775, 53782, 53785, 53793, 53795, 53805, 53805, 53806, 53807, 53810, 53816, 53817, 53821, 53822, 53827, 53841, 53844, 53845, 53852, 53857, 53863, 53870, 53875, 53876, 53881, 53892, 53892, 53894, 53897, 53901, 53902, 53903, 53906, 53906, 53907, 53910, 53917, 53918, 53919, 53926, 53941, 53945, 53947, 53952, 53955, 53958, 53958, 53960, 53962, 53966, 53968, 53974, 53977, 53979, 53980, 53981, 53995, 53997, 54000, 54010, 54015, 54016, 54017, 54020, 54022, 54027, 54029, 54035, 54036, 54042, 54043, 54049, 54050, 54052, 54055, 54061, 54062, 54063, 54064, 54068, 54068, 54078, 54084, 54085, 54089, 54090, 54091, 54099, 54103, 54104, 54105, 54108, 54112, 54115, 54115, 54118, 54132, 54137, 54141, 54142, 54142, 54145, 54148, 54149, 54150, 54152, 54153, 54157, 54165, 54165, 54168, 54173, 54176, 54177, 54185, 54188, 54194, 54194, 54198, 54203, 54213, 54213, 54217, 54218, 54224, 54233, 54234, 54235, 54238, 54241, 54241, 54242, 54256, 54258, 54263, 54272, 54286, 54287, 54293, 54296, 54297, 54297, 54299, 54302, 54303, 54303, 54307, 54312, 54313, 54318, 54321, 54322, 54327, 54335, 54335, 54337, 54339, 54348, 54349, 54349, 54352, 54352, 54363, 54368, 54369, 54372, 54372, 54373, 54374, 54380, 54383, 54387, 54387, 54390, 54395, 54397, 54398, 54403, 54404, 54411, 54415, 54416, 54426, 54432, 54433, 54434, 54436, 54437, 54440, 54443, 54444, 54453, 54462, 54468, 54468, 54469, 54469, 54472, 54476, 54477, 54484, 54494, 54496, 54510, 54510, 54515, 54515, 54516, 54518, 54519, 54519, 54521, 54526, 54530, 54533, 54536, 54536, 54539, 54539, 54542, 54543, 54546, 54550, 54553, 54556, 54561, 54566, 54569, 54572, 54574, 54578, 54582, 54583, 54584, 54586, 54592, 54592, 54602, 54606, 54606, 54608, 54609, 54617, 54618, 54618, 54621, 54625, 54628, 54634, 54635, 54639, 54646, 54647, 54653, 54655, 54665, 54669, 54670, 54675, 54676, 54676, 54677, 54678, 54681, 54685, 54688, 54695, 54699, 54700, 54702, 54706, 54710, 54719, 54727, 54738, 54740, 54748, 54748, 54749, 54756, 54756, 54756, 54759, 54764, 54767, 54768, 54776, 54776, 54803, 54804, 54808, 54810, 54811, 54813, 54815, 54816, 54822, 54822, 54824, 54835, 54841, 54843, 54853, 54860, 54863, 54864, 54866, 54868, 54873, 54875, 54878, 54886, 54890, 54891, 54894, 54900, 54901, 54903, 54905, 54924, 54932, 54933, 54935, 54940, 54941, 54949, 54957, 54961, 54962, 54966, 54967, 54970, 54981, 54981, 54996, 54999, 55000, 55003, 55012, 55015, 55015, 55016, 55022, 55033, 55037, 55038, 55039, 55040, 55048, 55052, 55054, 55054, 55055, 55056, 55059, 55059, 55063, 55064, 55074, 55075, 55080, 55085, 55086, 55100, 55101, 55107, 55110, 55111, 55111, 55113, 55119, 55122, 55125, 55126, 55127, 55144, 55144, 55146, 55147, 55149, 55153, 55167, 55168, 55174, 55174, 55178, 55179, 55180, 55186, 55199, 55206, 55214, 55219, 55220, 55228, 55234, 55235, 55236, 55236, 55236, 55238, 55239, 55245, 55247, 55250, 55251, 55259, 55261, 55261, 55263, 55263, 55263, 55264, 55269, 55270, 55272, 55273, 55274, 55279, 55282, 55283, 55291, 55293, 55293, 55298, 55299, 55304, 55305, 55310, 55312, 55312, 55325, 55326, 55337, 55354, 55357, 55357, 55381, 55386, 55391, 55394, 55396, 55400, 55401, 55415, 55418, 55418, 55420, 55422, 55423, 55424, 55430, 55431, 55439, 55439, 55442, 55445, 55447, 55448, 55448, 55449, 55456, 55457, 55461, 55467, 55469, 55469, 55470, 55477, 55508, 55517, 55517, 55519, 55532, 55534, 55534, 55538, 55552, 55553, 55556, 55557, 55557, 55573, 55575, 55575, 55581, 55587, 55591, 55596, 55602, 55602, 55605, 55606, 55609, 55614, 55616, 55616, 55618, 55620, 55621, 55623, 55629, 55633, 55633, 55640, 55643, 55646, 55648, 55649, 55653, 55658, 55658, 55660, 55660, 55661, 55668, 55688, 55693, 55693, 55698, 55700, 55704, 55710, 55711, 55713, 55714, 55719, 55722, 55722, 55723, 55727, 55729, 55729, 55730, 55735, 55738, 55745, 55747, 55751, 55762, 55763, 55770, 55779, 55780, 55783, 55792, 55807, 55808, 55810, 55816, 55818, 55818, 55819, 55819, 55824, 55824, 55827, 55829, 55829, 55840, 55840, 55840, 55843, 55847, 55847, 55848, 55855, 55856, 55857, 55859, 55860, 55864, 55868, 55874, 55876, 55878, 55882, 55882, 55883, 55885, 55887, 55887, 55895, 55904, 55915, 55924, 55929, 55930, 55932, 55933, 55942, 55943, 55945, 55953, 55961, 55967, 55969, 55969, 55971, 55972, 55975, 55985, 55987, 55989, 55990, 55992, 55993, 55994, 55996, 55999, 56002, 56004, 56005, 56007, 56009, 56011, 56019, 56022, 56023, 56025, 56026, 56029, 56029, 56035, 56040, 56043, 56048, 56050, 56051, 56059, 56064, 56066, 56066, 56072, 56074, 56075, 56075, 56081, 56082, 56086, 56088, 56091, 56094, 56095, 56097, 56098, 56102, 56102, 56102, 56103, 56103, 56104, 56106, 56109, 56110, 56112, 56114, 56118, 56127, 56129, 56141, 56141, 56147, 56148, 56152, 56160, 56162, 56163, 56167, 56176, 56182, 56185, 56185, 56192, 56192, 56193, 56193, 56194, 56196, 56202, 56205, 56206, 56208, 56216, 56227, 56228, 56233, 56236, 56236, 56237, 56243, 56244, 56245, 56246, 56252, 56259, 56262, 56264, 56268, 56273, 56275, 56277, 56282, 56284, 56294, 56298, 56303, 56304, 56306, 56317, 56318, 56321, 56325, 56326, 56326, 56327, 56335, 56337, 56341, 56343, 56344, 56350, 56354, 56355, 56359, 56383, 56392, 56399, 56405, 56414, 56416, 56420, 56422, 56426, 56427, 56428, 56428, 56432, 56438, 56444, 56444, 56447, 56448, 56448, 56450, 56452, 56453, 56454, 56460, 56465, 56470, 56471, 56473, 56482, 56483, 56492, 56495, 56500, 56501, 56502, 56505, 56505, 56511, 56511, 56516, 56521, 56526, 56538, 56538, 56539, 56542, 56544, 56548, 56559, 56560, 56562, 56562, 56564, 56566, 56568, 56569, 56569, 56570, 56573, 56574, 56582, 56586, 56592, 56596, 56601, 56601, 56603, 56604, 56604, 56613, 56614, 56614, 56618, 56618, 56620, 56620, 56634, 56638, 56645, 56645, 56649, 56651, 56659, 56663, 56667, 56668, 56672, 56683, 56684, 56684, 56688, 56689, 56690, 56693, 56694, 56694, 56695, 56704, 56709, 56718, 56719, 56725, 56731, 56736, 56739, 56746, 56752, 56756, 56760, 56761, 56763, 56766, 56768, 56769, 56770, 56779, 56783, 56784, 56785, 56787, 56790, 56791, 56792, 56797, 56798, 56803, 56803, 56813, 56816, 56819, 56823, 56825, 56829, 56839, 56841, 56841, 56842, 56847, 56849, 56851, 56851, 56852, 56856, 56858, 56860, 56863, 56865, 56865, 56867, 56869, 56876, 56876, 56880, 56882, 56883, 56884, 56885, 56891, 56892, 56894, 56898, 56901, 56909, 56912, 56916, 56918, 56934, 56936, 56937, 56948, 56948, 56954, 56958, 56959, 56959, 56961, 56963, 56964, 56966, 56971, 56972, 56977, 56979, 56984, 56989, 56991, 56991, 56991, 56995, 56996, 57006, 57012, 57013, 57016, 57040, 57042, 57043, 57043, 57053, 57060, 57061, 57065, 57078, 57080, 57082, 57085, 57087, 57090, 57095, 57104, 57110, 57115, 57121, 57127, 57129, 57131, 57134, 57139, 57146, 57157, 57163, 57176, 57178, 57181, 57182, 57190, 57191, 57191, 57194, 57195, 57204, 57207, 57210, 57210, 57211, 57212, 57226, 57233, 57241, 57246, 57250, 57253, 57255, 57255, 57260, 57260, 57263, 57265, 57271, 57272, 57273, 57276, 57283, 57284, 57296, 57296, 57298, 57299, 57300, 57309, 57317, 57318, 57327, 57329, 57330, 57332, 57336, 57336, 57340, 57342, 57344, 57346, 57347, 57363, 57364, 57369, 57380, 57383, 57389, 57389, 57391, 57392, 57392, 57397, 57400, 57402, 57412, 57413, 57415, 57422, 57427, 57432, 57432, 57440, 57440, 57442, 57442, 57448, 57451, 57452, 57466, 57468, 57472, 57475, 57477, 57478, 57480, 57484, 57491, 57491, 57497, 57500, 57503, 57506, 57522, 57527, 57534, 57537, 57538, 57551, 57557, 57558, 57562, 57563, 57565, 57565, 57567, 57568, 57571, 57574, 57580, 57580, 57581, 57585, 57592, 57594, 57596, 57597, 57602, 57603, 57603, 57608, 57618, 57619, 57620, 57620, 57625, 57626, 57626, 57630, 57641, 57643, 57649, 57650, 57652, 57653, 57655, 57656, 57656, 57658, 57659, 57660, 57662, 57666, 57675, 57676, 57680, 57681, 57684, 57684, 57685, 57686, 57689, 57690, 57693, 57695, 57696, 57697, 57701, 57704, 57707, 57709, 57716, 57718, 57719, 57719, 57720, 57723, 57725, 57730, 57741, 57741, 57744, 57746, 57749, 57751, 57754, 57755, 57756, 57760, 57776, 57777, 57780, 57782, 57787, 57791, 57794, 57795, 57796, 57805, 57808, 57815, 57819, 57833, 57836, 57836, 57848, 57849, 57849, 57850, 57852, 57854, 57858, 57864, 57865, 57868, 57874, 57877, 57880, 57894, 57898, 57901, 57902, 57902, 57905, 57907, 57914, 57914, 57917, 57917, 57923, 57933, 57936, 57937, 57938, 57943, 57944, 57944, 57948, 57951, 57953, 57962, 57962, 57964, 57967, 57969, 57972, 57983, 57991, 57999, 58000, 58001, 58014, 58017, 58017, 58019, 58021, 58024, 58034, 58039, 58040, 58041, 58051, 58053, 58053, 58056, 58060, 58065, 58068, 58082, 58088, 58090, 58090, 58096, 58096, 58099, 58104, 58106, 58107, 58109, 58109, 58115, 58115, 58118, 58118, 58122, 58122, 58125, 58127, 58133, 58135, 58139, 58143, 58145, 58148, 58151, 58158, 58161, 58164, 58176, 58177, 58181, 58183, 58184, 58185, 58185, 58187, 58191, 58191, 58192, 58194, 58194, 58204, 58207, 58211, 58213, 58225, 58228, 58233, 58233, 58238, 58239, 58244, 58245, 58247, 58252, 58258, 58259, 58259, 58262, 58263, 58269, 58269, 58275, 58276, 58282, 58283, 58286, 58290, 58292, 58295, 58302, 58302, 58312, 58313, 58321, 58326, 58329, 58333, 58336, 58338, 58344, 58350, 58359, 58363, 58364, 58364, 58375, 58386, 58392, 58392, 58401, 58401, 58403, 58404, 58410, 58415, 58416, 58421, 58421, 58426, 58427, 58431, 58434, 58435, 58439, 58446, 58450, 58454, 58454, 58455, 58455, 58461, 58463, 58479, 58480, 58484, 58492, 58493, 58502, 58502, 58503, 58507, 58509, 58512, 58522, 58528, 58530, 58532, 58536, 58536, 58538, 58539, 58539, 58557, 58558, 58560, 58573, 58575, 58579, 58584, 58585, 58588, 58589, 58596, 58605, 58607, 58607, 58609, 58611, 58612, 58617, 58619, 58622, 58625, 58633, 58635, 58637, 58638, 58642, 58644, 58647, 58650, 58651, 58654, 58655, 58655, 58659, 58660, 58666, 58668, 58671, 58673, 58674, 58678, 58679, 58683, 58685, 58690, 58698, 58705, 58712, 58713, 58714, 58716, 58717, 58724, 58727, 58731, 58733, 58735, 58746, 58749, 58756, 58760, 58771, 58775, 58779, 58780, 58788, 58789, 58792, 58796, 58797, 58808, 58809, 58819, 58822, 58829, 58836, 58845, 58846, 58849, 58860, 58868, 58869, 58873, 58883, 58886, 58890, 58890, 58890, 58893, 58897, 58899, 58904, 58905, 58905, 58905, 58907, 58910, 58912, 58913, 58916, 58919, 58925, 58927, 58927, 58928, 58933, 58942, 58945, 58948, 58948, 58949, 58950, 58951, 58951, 58953, 58955, 58955, 58956, 58959, 58969, 58977, 58983, 58986, 58989, 58993, 58995, 58999, 59004, 59007, 59010, 59015, 59017, 59019, 59023, 59027, 59028, 59033, 59034, 59035, 59047, 59056, 59060, 59061, 59062, 59064, 59066, 59073, 59084, 59084, 59093, 59111, 59111, 59112, 59119, 59121, 59124, 59126, 59133, 59134, 59138, 59139, 59141, 59146, 59152, 59153, 59155, 59158, 59159, 59170, 59171, 59172, 59175, 59187, 59189, 59194, 59196, 59203, 59205, 59206, 59209, 59214, 59214, 59228, 59230, 59230, 59230, 59244, 59267, 59274, 59278, 59281, 59284, 59286, 59297, 59302, 59305, 59307, 59308, 59312, 59313, 59315, 59315, 59315, 59318, 59323, 59328, 59342, 59343, 59345, 59347, 59359, 59372, 59377, 59377, 59382, 59382, 59383, 59383, 59388, 59391, 59410, 59411, 59420, 59434, 59435, 59435, 59437, 59438, 59439, 59441, 59454, 59467, 59474, 59475, 59478, 59478, 59481, 59482, 59495, 59507, 59509, 59511, 59513, 59514, 59516, 59530, 59531, 59540, 59544, 59551, 59556, 59556, 59557, 59559, 59562, 59565, 59568, 59577, 59578, 59579, 59587, 59590, 59603, 59604, 59604, 59605, 59609, 59610, 59622, 59630, 59638, 59639, 59641, 59643, 59645, 59646, 59652, 59656, 59662, 59662, 59663, 59669, 59670, 59672, 59680, 59687, 59692, 59693, 59693, 59709, 59709, 59710, 59711, 59715, 59717, 59724, 59724, 59726, 59726, 59728, 59743, 59763, 59764, 59767, 59767, 59768, 59768, 59775, 59779, 59782, 59786, 59789, 59792, 59793, 59794, 59799, 59801, 59803, 59806, 59809, 59825, 59827, 59829, 59832, 59835, 59836, 59839, 59841, 59844, 59852, 59853, 59854, 59855, 59863, 59864, 59867, 59867, 59869, 59874, 59880, 59884, 59898, 59910, 59912, 59913, 59916, 59919, 59922, 59934, 59936, 59939, 59939, 59940, 59947, 59947, 59950, 59952, 59952, 59954, 59954, 59955, 59956, 59961, 59962, 59962, 59968, 59975, 59981, 59981, 59983, 59988, 59989, 59990, 59990, 59993, 59994, 60003, 60010, 60014, 60014, 60017, 60019, 60022, 60023, 60029, 60033, 60035, 60039, 60042, 60045, 60058, 60059, 60059, 60070, 60080, 60085, 60090, 60108, 60116, 60118, 60121, 60121, 60124, 60126, 60128, 60139, 60150, 60151, 60155, 60161, 60168, 60168, 60169, 60171, 60181, 60188, 60191, 60193, 60196, 60209, 60210, 60210, 60225, 60235, 60237, 60247, 60248, 60248, 60251, 60257, 60258, 60259, 60261, 60267, 60267, 60268, 60269, 60273, 60279, 60280, 60281, 60281, 60292, 60294, 60299, 60302, 60303, 60314, 60318, 60318, 60319, 60319, 60322, 60322, 60326, 60332, 60337, 60338, 60343, 60345, 60351, 60355, 60359, 60360, 60361, 60368, 60371, 60380, 60380, 60380, 60383, 60388, 60400, 60402, 60404, 60406, 60407, 60410, 60414, 60419, 60423, 60425, 60427, 60429, 60430, 60432, 60433, 60434, 60437, 60438, 60443, 60446, 60449, 60449, 60453, 60457, 60462, 60464, 60468, 60468, 60470, 60474, 60480, 60482, 60483, 60484, 60485, 60486, 60493, 60498, 60500, 60501, 60503, 60504, 60504, 60504, 60505, 60511, 60520, 60521, 60525, 60528, 60529, 60529, 60532, 60533, 60535, 60538, 60538, 60549, 60556, 60560, 60563, 60563, 60570, 60579, 60580, 60583, 60588, 60591, 60593, 60594, 60594, 60604, 60607, 60609, 60610, 60612, 60612, 60621, 60621, 60622, 60624, 60626, 60658, 60659, 60661, 60679, 60680, 60680, 60680, 60681, 60682, 60684, 60684, 60684, 60691, 60697, 60698, 60712, 60716, 60720, 60724, 60725, 60727, 60731, 60733, 60733, 60737, 60738, 60745, 60747, 60749, 60750, 60754, 60755, 60758, 60761, 60762, 60763, 60764, 60777, 60779, 60781, 60783, 60785, 60786, 60787, 60790, 60793, 60794, 60796, 60797, 60799, 60809, 60810, 60811, 60813, 60815, 60815, 60820, 60822, 60825, 60827, 60831, 60835, 60840, 60840, 60841, 60844, 60845, 60846, 60852, 60863, 60864, 60867, 60868, 60870, 60871, 60873, 60873, 60874, 60875, 60884, 60890, 60897, 60903, 60905, 60910, 60913, 60914, 60914, 60923, 60928, 60930, 60935, 60937, 60938, 60947, 60954, 60955, 60960, 60964, 60968, 60970, 60973, 60974, 60975, 60978, 60981, 60982, 60983, 60985, 60987, 60989, 60991, 60992, 60995, 61009, 61015, 61017, 61018, 61021, 61028, 61031, 61034, 61034, 61040, 61041, 61041, 61050, 61056, 61060, 61065, 61073, 61081, 61084, 61096, 61104, 61109, 61114, 61120, 61123, 61133, 61134, 61142, 61142, 61156, 61156, 61160, 61163, 61170, 61176, 61177, 61179, 61185, 61188, 61197, 61198, 61199, 61201, 61201, 61201, 61201, 61202, 61209, 61211, 61211, 61213, 61232, 61234, 61234, 61235, 61238, 61249, 61251, 61252, 61262, 61268, 61275, 61279, 61280, 61283, 61283, 61284, 61293, 61295, 61299, 61305, 61308, 61309, 61310, 61313, 61313, 61320, 61321, 61329, 61329, 61344, 61357, 61359, 61374, 61379, 61380, 61383, 61386, 61402, 61408, 61413, 61420, 61423, 61434, 61442, 61450, 61454, 61454, 61472, 61472, 61474, 61476, 61479, 61480, 61481, 61481, 61484, 61487, 61509, 61511, 61513, 61514, 61516, 61518, 61520, 61524, 61526, 61532, 61534, 61538, 61548, 61556, 61558, 61558, 61561, 61563, 61566, 61567, 61568, 61572, 61573, 61575, 61581, 61582, 61584, 61604, 61604, 61606, 61610, 61613, 61614, 61628, 61631, 61631, 61638, 61642, 61646, 61649, 61650, 61655, 61657, 61660, 61665, 61667, 61667, 61669, 61670, 61670, 61682, 61683, 61684, 61686, 61688, 61691, 61691, 61695, 61697, 61700, 61705, 61707, 61707, 61709, 61716, 61720, 61722, 61729, 61731, 61734, 61737, 61747, 61751, 61754, 61757, 61761, 61762, 61772, 61777, 61781, 61795, 61800, 61803, 61807, 61808, 61820, 61825, 61828, 61832, 61834, 61847, 61850, 61851, 61852, 61857, 61863, 61867, 61869, 61881, 61882, 61884, 61887, 61891, 61899, 61902, 61904, 61907, 61918, 61924, 61926, 61926, 61934, 61942, 61945, 61953, 61953, 61954, 61958, 61958, 61962, 61965, 61973, 61981, 61982, 61989, 62000, 62009, 62009, 62020, 62023, 62023, 62024, 62025, 62031, 62040, 62047, 62051, 62062, 62064, 62068, 62069, 62078, 62079, 62087, 62088, 62092, 62096, 62102, 62109, 62119, 62122, 62127, 62129, 62137, 62147, 62149, 62150, 62153, 62154, 62154, 62156, 62159, 62180, 62184, 62198, 62205, 62206, 62207, 62212, 62228, 62230, 62236, 62238, 62242, 62250, 62256, 62256, 62267, 62270, 62276, 62279, 62295, 62296, 62297, 62298, 62300, 62304, 62305, 62310, 62314, 62316, 62316, 62323, 62341, 62354, 62357, 62360, 62373, 62378, 62378, 62378, 62381, 62383, 62386, 62390, 62401, 62405, 62405, 62408, 62417, 62424, 62433, 62438, 62441, 62447, 62453, 62453, 62456, 62460, 62460, 62461, 62462, 62466, 62466, 62473, 62486, 62487, 62488, 62489, 62498, 62500, 62518, 62543, 62544, 62547, 62549, 62551, 62562, 62563, 62570, 62571, 62571, 62571, 62578, 62579, 62582, 62585, 62588, 62592, 62603, 62609, 62614, 62626, 62627, 62630, 62630, 62631, 62632, 62635, 62636, 62639, 62639, 62642, 62648, 62649, 62649, 62653, 62655, 62666, 62666, 62675, 62676, 62678, 62679, 62680, 62685, 62685, 62686, 62699, 62701, 62713, 62719, 62727, 62732, 62734, 62734, 62736, 62736, 62738, 62738, 62742, 62744, 62749, 62754, 62756, 62757, 62757, 62759, 62760, 62762, 62767, 62770, 62770, 62772, 62778, 62782, 62783, 62784, 62796, 62798, 62800, 62808, 62808, 62812, 62815, 62821, 62822, 62826, 62826, 62826, 62831, 62832, 62834, 62839, 62839, 62841, 62848, 62852, 62862, 62876, 62877, 62878, 62878, 62887, 62888, 62897, 62898, 62899, 62900, 62902, 62906, 62906, 62907, 62915, 62919, 62925, 62927, 62932, 62935, 62937, 62944, 62951, 62952, 62956, 62958, 62958, 62959, 62960, 62960, 62963, 62963, 62964, 62968, 62975, 62981, 62984, 62984, 62987, 62989, 62991, 62993, 62994, 62995, 62999, 63008, 63011, 63013, 63015, 63018, 63022, 63022, 63026, 63028, 63037, 63039, 63039, 63039, 63040, 63041, 63043, 63050, 63051, 63054, 63058, 63059, 63062, 63064, 63067, 63067, 63068, 63074, 63080, 63081, 63082, 63088, 63088, 63089, 63092, 63094, 63104, 63108, 63124, 63124, 63129, 63145, 63153, 63155, 63158, 63164, 63166, 63172, 63172, 63172, 63177, 63179, 63185, 63189, 63198, 63201, 63203, 63215, 63218, 63218, 63218, 63230, 63231, 63236, 63247, 63249, 63251, 63254, 63256, 63258, 63260, 63261, 63263, 63266, 63268, 63277, 63279, 63281, 63283, 63285, 63286, 63287, 63287, 63291, 63296, 63301, 63308, 63316, 63319, 63320, 63321, 63322, 63323, 63329, 63330, 63330, 63334, 63335, 63336, 63341, 63341, 63344, 63352, 63357, 63358, 63365, 63370, 63382, 63387, 63393, 63395, 63395, 63397, 63397, 63406, 63410, 63410, 63418, 63420, 63432, 63433, 63437, 63448, 63453, 63454, 63465, 63467, 63467, 63479, 63480, 63482, 63489, 63490, 63492, 63498, 63500, 63501, 63510, 63511, 63513, 63522, 63524, 63525, 63527, 63527, 63531, 63534, 63535, 63536, 63541, 63544, 63545, 63550, 63560, 63572, 63576, 63578, 63580, 63585, 63585, 63590, 63591, 63600, 63600, 63602, 63609, 63611, 63616, 63616, 63617, 63620, 63629, 63633, 63635, 63636, 63638, 63651, 63661, 63663, 63664, 63670, 63670, 63677, 63680, 63681, 63683, 63688, 63691, 63694, 63696, 63698, 63698, 63699, 63700, 63700, 63701, 63704, 63705, 63709, 63720, 63723, 63723, 63724, 63731, 63734, 63734, 63738, 63758, 63762, 63764, 63765, 63769, 63774, 63782, 63783, 63784, 63794, 63796, 63801, 63806, 63811, 63816, 63818, 63818, 63825, 63829, 63831, 63835, 63836, 63850, 63860, 63862, 63875, 63877, 63878, 63879, 63880, 63883, 63886, 63886, 63892, 63892, 63897, 63898, 63903, 63904, 63904, 63905, 63906, 63907, 63918, 63927, 63930, 63930, 63933, 63934, 63935, 63936, 63955, 63958, 63958, 63964, 63971
        }, 657);
    }
    private int[][] g;
    private int m, n;
    //找上下边缘
    public boolean isPossibleToCutPath(int[][] grid) {
        g = grid; m = g.length; n = g[0].length;
        return !dfs(0, 0) || !dfs(0, 0);
    }

    private boolean dfs(int x, int y) { // 返回能否到达终点
        if (x == m - 1 && y == n - 1) return true;
        g[x][y] = 0; // 直接修改
        return x < m - 1 && g[x + 1][y] > 0 && dfs(x + 1, y) ||
                y < n - 1 && g[x][y + 1] > 0 && dfs(x, y + 1);
    }

  /*  public boolean isPossibleToCutPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[m - 1][n - 1] == 0) return true;
        grid[0][0] = 1;
        int[][] in = new int[m][n];
        int[][] out = new int[m][n];
        dfs(0, 0, grid, in, out);
    }

    boolean dfs(int i, int j, int[][] grid, int[][] in, int[][] out) {
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return true;
        }
        if (grid[i][j] == 0) return false;
        boolean down = false, right = false;
        if (i + 1 < grid.length) {
            down = dfs(i + 1, j, grid, in, out);
            if (down) {
                in[i + 1][j]++;
                out[i][j]++;
            }
        }
        if (j + 1 < grid[0].length) {
            right = dfs(i, j + 1, grid, in, out);
            if (right) {
                in[i][j + 1]++;
                out[i][j]++;
            }
        }
        return down | right;
    }*/
}