Planeetat

warning: unused import: `std::collections::BinaryHeap`
 --> input/code.rs:3:5
  |
3 | use std::collections::BinaryHeap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `n`
   --> input/code.rs:301:13
    |
301 | fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) {
    |             ^ help: consider prefixing with an underscore: `_n`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `k`
   --> input/code.rs:301:23
    |
301 | fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) {
    |                       ^ help: consider prefixing with an underscore: `_k`

warning: unused variable: `max_s`
   --> input/code.rs:301:33
    |
301 | fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) {
    |                                 ^^^^^ help: consider prefixing with an unders...

use std::cmp::Reverse;
use std::collections::BTreeMap;
use std::collections::BinaryHeap;
use std::io::BufRead;

const MOD: usize = 1_000_000_007;

fn print_iter<I: Iterator>(iter: I)
where
    <I as Iterator>::Item: std::fmt::Display,
{
    let mut iter = iter;
    if let Some(v) = iter.next() {
        print!("{}", v);
        for v in iter {
            print!(" {}", v);
        }
    }
    println!();
}

struct UnionFind {
    links: Vec<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> Self {
        Self {
            links: (0..n).collect(),
        }
    }

    pub fn find(&mut self, n: usize) -> usize {
        if self.links[n] == n {
            n
        } else {
            self.links[n] = self.find(self.links[n]);
            self.links[n]
        }
    }

    pub fn union(&mut self, a: usize, b: usize) {
        let a = self.find(a);
        let b = self.find(b);
        self.links[a] = b;
    }
}

fn modpow(b: usize, e: usize) -> usize {
    if e == 0 {
        1
    } else if e % 2 == 0 {
        let p = modpow(b, e / 2);
        (p * p) % MOD
    } else {
        (b * modpow(b, e - 1)) % MOD
    }
}
fn modfac(n: usize) -> usize {
    if n == 0 {
        1
    } else {
        (n * modfac(n - 1)) % MOD
    }
}
fn modbin(k: usize, n: usize) -> usize {
    (modfac(n) * modpow((modfac(k) * modfac(n - k)) % MOD, MOD - 2)) % MOD
}

static mut stats: Option<BTreeMap<(usize, usize, usize), usize>> = None;

fn super_binomial(k: usize, max_s: usize, s_count: usize) -> usize {
    assert!(max_s >= 1);

    std::thread_local! {
        static mem: std::cell::RefCell<BTreeMap<(usize, usize, usize), usize>> = std::cell::RefCell::new(BTreeMap::new());
    }

    let saved = mem.with(|m| m.borrow().get(&(k, max_s, s_count)).copied());
    if let Some(saved) = saved {
        saved
    } else {
        if k == 0 {
            return 1;
        }

        let mut sum = 0;
        // Try all possible sizes for the next subset
        for s in 1..=max_s {
            if k < s {
                break;
            }
            let new_s_count = if s == max_s { s_count + 1 } else { 1 };
            sum += (super_binomial(
                k - s,       // k
                s,           // max_s
                new_s_count, // s_count
            ) * component_count(s))
                % MOD
                * modpow(modfac(s) * new_s_count, MOD - 2);
            sum %= MOD;
        }

        mem.with(|m| m.borrow_mut().insert((k, max_s, s_count), sum));
        sum
    }
}

/// Compute the number of ways in which n planets can belong to 1 component
fn component_count(n: usize) -> usize {
    // These take a couple of minutes to compute, so just return cached values
    let cache = vec![
        0, 1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 660215659, 920608908, 836504326,
        639554500, 466620985, 872046927, 308717370, 502812808, 646301526, 985602096, 8033007,
        199948617, 265123234, 963316760, 97012001, 520509077, 963089188, 609109590, 475681640,
        268714573, 138142320, 659323185, 432287876, 833911481, 580044808, 724047794, 752488773,
        369844336, 411404305, 966444867, 966304277, 670002988, 356672355, 499497440, 858083915,
        849461059, 699627096, 696125320, 569657991, 589455080, 637699856, 159331976, 253230028,
        126065421, 190780359, 657860743, 35914725, 627548423, 786042624, 88732365, 595484631,
        907204844, 310896156, 654434332, 999859588, 891860619, 760802640, 321240817, 284705446,
        581193655, 540500946, 828699763, 86377965, 299422367, 636989116, 804687707, 341628824,
        969661800, 493359322, 269113227, 2788545, 136045625, 319856162, 734688215, 933443980,
        548820306, 844116817, 949670148, 893770986, 562714601, 464787503, 785661356, 27520011,
        33434941, 651969158, 596069751, 447474780, 454137267, 430168215, 427270537, 894456323,
        432736565, 541462563, 580395437, 926815786, 263023838, 779713525, 129353767, 254646934,
        327058306, 318061585, 873404148, 546897006, 256895690, 845805366, 521993981, 151412543,
        452233370, 169107595, 352810726, 932989581, 82660203, 144142246, 7983114, 841762719,
        398368184, 36362596, 5939420, 621718875, 180998347, 89322205, 709123956, 45239813,
        623512817, 592243835, 375742205, 13182108, 741093354, 954650126, 632161601, 323889231,
        855586538, 576541114, 402077493, 420399764, 23768284, 168259101, 986206037, 639024795,
        827219225, 972138947, 118660280, 935496148, 260619316, 568756388, 474316106, 90646046,
        327256160, 906940925, 61315684, 100123479, 904812330, 341615294, 269531078, 100088684,
        608203198, 84183940, 718793427, 269849284, 338624606, 60645067, 579226929, 140045143,
        723080187, 393278301, 585228375, 59206357, 101985982, 672040685, 139906388, 744500615,
        662412691, 158778780, 73399837, 332041241, 281105866, 957970313, 29966196, 815538417,
        292300246, 570909748, 771503216, 214191103, 101730853, 63227600, 308932805, 811045900,
        464333632, 357992660, 77607798, 507287768, 341677483, 72934014, 46989119, 114936355,
        602267494, 906589693, 582034332, 895922440, 156857108, 618036646, 157634170, 761405010,
        817859847, 467337486, 632543264, 517776051, 994834897, 687965083, 457907638, 825497422,
        243467865, 14399121, 407258784, 98570234, 748959757, 297443300, 406918679, 871245292,
        252946284, 452320327, 942393032, 318555470, 766642481, 981668534, 724552884, 301298708,
        142719827, 453758144, 985372383, 718141077, 18615310, 590242901, 715391284, 471018736,
        571254190, 833968271, 832120869, 945980567, 722309937, 54672675, 115490430, 187087627,
        626363638, 686555146, 318156532, 972513131, 167214298, 90260614, 306880672, 32986840,
        478943540, 672206708, 393818545, 416131966, 388360852, 956022816, 146560536, 392214273,
        327393841, 526526895, 175253967, 352945422, 306638803, 941328742, 230321990, 570405207,
        35763767, 385325705, 457471115, 680333391, 913022330, 507476085, 625156383, 460862378,
        719762476, 612136402, 543142329, 910689236, 864620931, 94770086, 124023110, 936801504,
        312536722, 840866722, 550990595, 847033780, 9264261, 210329044, 369392790, 722084766,
        940376498, 107971898, 858413915, 472976473, 311774094, 267458901, 145925718, 338817999,
        630914080, 579431167, 386296719, 138838078, 585741448, 847119734, 643211690, 268683825,
        351931792, 735656552, 8097207, 868683252, 134721277, 751435055, 835490594, 768101286,
        361829871, 395204061, 571729313, 121053572, 334933401, 823546703, 791822392, 196085636,
        914631844, 921218256, 269969740, 960245594, 308426560, 50228312, 203517952, 816105383,
        292189633, 32732523, 666262122, 437188886, 72215308, 918176539, 415978508, 85324969,
        769013382, 647852341, 689378978, 613167392, 340915335, 831071843, 565517411, 255908828,
        91838622, 605127507, 57150948, 686992820, 685954022, 342552285, 849812665, 260415783,
        694407779, 131097970, 232078836, 790843917, 602509046, 136064185, 155679521, 958411398,
        943708467, 206313402, 358630277, 411970955, 489455840, 988325815, 978309818, 166561041,
        394433021, 617840127, 693970966, 995469520, 143162639, 766345048, 552437316, 141371172,
        32069679, 516006699, 884187788, 608358064, 219163692, 387670703, 175148085, 17199999,
        180488480, 660440926, 864052274, 765128850, 483638267, 499688410, 640750115, 524434952,
        827157815, 514841947, 891119953, 537621015, 892118064, 928120221, 364674640, 992761107,
        724302220, 924628854, 760255237, 179981576, 235556227, 244177714, 854964962, 259182566,
        77503409, 507837049, 779838104, 423943877, 886744385, 958705993, 455048970, 824356123,
        713721861, 331904766, 623348072, 897891320, 902610163, 946917405, 630933809, 683877164,
        640836005, 535209373, 166585714, 161480461, 455967117, 252642116, 897912756, 319743887,
        916746661, 702589733, 778455519, 547659731, 289013415, 557947707, 955879877, 505371826,
        707573819, 803154268, 969112213, 221690942, 226656978, 735346391, 982277351, 592777469,
        447310232, 172403391, 748268363, 696182473, 52336674, 694374706, 788244971, 937988296,
        79919141, 145294051, 52674283, 265392050, 996188166, 381465305, 372742716, 485059689,
        315704434, 844900882, 764763714, 551996787, 961793773, 365663110, 538922989, 601146238,
        25707931, 555697561, 878705277, 319447511, 428853013, 742394955, 53270809, 647847019,
        542010010, 434050460, 439016902, 973744116, 662776175, 977629798, 900768919, 129073991,
        76026409, 498192056, 215123369, 777607783, 826637623, 435940858, 632532526, 979699864,
        273969950, 918223569, 797914606, 282218800, 216770185, 381331949, 326172660, 120803564,
        853670387, 682492038, 972664354, 284139447, 315944240, 800436189, 46026170, 412249526,
        683709489, 832181317, 394745079, 28240146, 163080658, 90324747, 780658649, 40050836,
        753363258, 490090701, 507159728, 175535065, 880542882, 601405007, 875042173, 622572015,
        624703488, 609933868, 870319039, 519399753, 237139139, 171461911, 722145611, 176534686,
        748791413, 777888894, 189895535, 776214576, 62907885, 838377878, 93453694, 917533875,
        810336630, 609416452, 888415765, 393387753, 513394863, 223454100, 439177115, 473459974,
        622286412, 444809364, 970826379, 277126519, 793591686, 566696364, 524560088, 518622823,
        740934331, 615919709, 233608104, 444215291, 445025848, 856961685, 923580922, 185212905,
        392675418, 727388601, 865839801, 76975614, 920825987, 676444158, 68254115, 754592218,
        324465365, 841768008, 273959910, 326575287, 547731766, 319188450, 611633037, 901608514,
        588206840, 732761621, 715062417, 742160893, 339850593, 508303398, 393630144, 829399774,
        404455930, 437595436, 84921880, 613757541, 683956864, 584483785, 227026419, 418559713,
        401523829, 185477490, 249706231, 327552152, 770760761, 378607522, 394710363, 763322048,
        628614375, 939574117, 900466080, 643974820, 674683595, 842164179, 895649271, 202668486,
        109169255, 296830144, 371897295, 625604906, 869773593, 833554505, 306574822, 818243912,
        654193167, 960565833, 804819530, 647238123, 885855615, 215870028, 964455102, 92443932,
        559430472, 23511463, 264092633, 260000328, 79622179, 474381606, 554791439, 330903508,
        511020268, 932195757, 352156109, 733558674, 294113392, 142386392, 964997788, 528074716,
        830312898, 163010932, 863889744, 102244077, 676493916, 912089702, 24225168, 465021266,
        603765333, 103120244, 784797374, 893623207, 595340442, 425658649, 291577723, 670989044,
        79022991, 21873737, 425688347, 89846397, 488428951, 746805572, 248666732, 241174360,
        684601776, 236729218, 422757346, 364668703, 293549644, 380351742, 772661211, 276677051,
        501793049, 880460037, 883830717, 379239787, 307979260, 751943962, 510752702, 744824767,
        442457467, 362155826, 489422317, 536111619, 914573030, 747095783, 884906140, 884441968,
        733653555, 146854917, 937116871, 163855877, 779645110, 709087432, 19492549, 147701829,
        364984477, 953983272, 567675621, 706105104, 157113580, 513338758, 653488931, 868545818,
        937865416, 255354491, 424337212, 586865979, 617557895, 111291906, 81586380, 569226029,
        722531365, 497424224, 114733014, 797099698, 225894714, 90394372, 447007271, 10245498,
        898128017, 766053818, 530349910, 882939708, 729004111, 108441817, 872910612, 705372057,
        995052453, 130708566, 269715702, 758342226, 348077669, 325709455, 866705688, 910469462,
        386447238, 115474755, 759928927, 272731632, 965099577, 72891374, 77737598, 502245864,
        685947101, 826847537, 819513705, 190633932, 555472343, 88760039, 762976966, 402514248,
        839207200, 779254057, 705559546, 562644196, 350626583, 9509184, 126888328, 152195603,
        132081101, 676239633, 458726032, 589898338, 148686953, 885348268, 801459787, 139572747,
        673185038, 991695943, 862630555, 366760847, 80076634, 966502459, 821571988, 21572279,
        721384935, 734870723, 218142410, 199368873, 604049970, 825401160, 507527461, 513100735,
        948791033, 203154030, 58041031, 640367423, 318384869, 77570129, 824194966, 825656956,
        77368019, 11306670, 106866672, 492360111, 943360649, 406075975, 779083698, 310454415,
        342169482, 803327115, 807386468, 255782051, 440244031, 950122691, 232360024, 101541391,
        865866499, 288404715, 96301762, 746211745, 673942807, 915823587, 417570436, 598672851,
        160322947, 244425439, 789934672, 618584932, 214979299, 860921706, 107319155, 316165313,
        965981656, 871166204, 841585452, 464957002, 668310812, 444833369, 849040138, 686345409,
        528113576, 983914180, 541311807, 848006220, 419529610, 171694617, 659806304, 279589304,
        208134673, 783769758, 974670184, 355188677, 141562686, 300791432, 842665724, 650736657,
        422159400, 50567611, 947382007, 87673516, 55967662, 261441709, 661131710, 755028429,
        841985974, 201632612, 945517170, 164980904, 817773860, 82055469, 445290969, 706944415,
        725447477, 664136292, 389817602, 780086779, 622797299, 148415442, 5708337, 666556057,
        224133097, 366882575, 914194185, 882014633, 978575769, 90170576, 471762897, 542460155,
        514096839, 701614974, 60312755, 917231767, 964520213, 358490848, 81057698, 247832532,
        341219882, 100102824, 341934238, 114183004, 209145178, 923964885, 435124520, 365469193,
        120384141, 56549158, 152602509, 361071024, 978731849, 532938250, 594199322, 752806852,
        456440644, 567440735, 988054619, 827866096, 699153707, 608834898, 362641723, 328571157,
        127445368, 597814206, 973349517, 892205335, 417582204, 988281451, 517534077, 352254670,
        336896544, 306733391, 748107970, 745916046, 607322378, 242269963, 451617315, 135967883,
        547822253, 313317750, 161488653, 301469277, 962913750, 674210017, 871684984, 846374473,
        601268294, 272544856, 214984956, 749089551, 450324802, 794618905, 329197003, 720425508,
        718926483, 494961133, 175588666, 199464056, 495851296, 10433899, 109859248, 258634838,
        147733353, 337233802, 299746629, 867784754, 831913393, 916124868, 415567211, 362520882,
        687700843, 108480217, 487643969, 798885287, 164330043, 141392377, 326198123, 395941595,
        161694806, 818547955, 461145285, 306055730, 597316323, 933967768, 13002237, 119645725,
        513592965, 196084977, 337595660, 887375487,
    ];
    if n < cache.len() {
        cache[n]
    } else if n == 1 {
        1
    } else {
        (modpow(n, n) + MOD - (modfac(n) * super_binomial(n, n - 1, 0)) % MOD) % MOD
    }
}

fn next_configuration(conf: &mut [usize]) -> bool {
    let n = conf.len();
    for i in 0..n {
        if conf[i] != n - 1 {
            conf[i] += 1;
            return false;
        } else {
            conf[i] = 0;
        }
    }
    true
}

fn brute(n: usize) -> Vec<usize> {
    let mut res = vec![0; n];
    let mut conf = vec![0; n];

    // fn find_component(i: usize, conf: &[usize]) -> usize {
    //     if conf[i] == i {
    //         i
    //     } else {
    //         find_component(conf[i], conf)
    //     }
    // }

    let mut last = 0;
    loop {
        if conf[n - 2] == last {
            println!("{}, {}", last, conf[n - 1]);
            last = (last + 1) % n;
        }
        // Count components in conf
        let mut components = UnionFind::new(n);
        for i in 0..n {
            components.union(i, conf[i]);
        }
        let mut component_list = Vec::new();
        for i in 0..n {
            component_list.push(components.find(i));
        }
        component_list.sort();
        component_list.dedup();
        res[n - component_list.len()] += 1;

        if next_configuration(&mut conf) {
            break;
        }
    }

    res
}

// n planets, of which k are not used, subset has at most max_s elements, there are already parts subsets
fn subsolve(n: usize, k: usize, max_s: usize, mul: usize, parts: usize, res: &mut [usize]) {
    // assert!(max_s >= 1);
    // if k == 0 {
    //     // No planets left.
    //     res[parts - 1] += mul;
    //     return;
    // }

    // // Try all possible sizes for the next subset
    // for s in 1..=max_s {
    //     if k < s {
    //         break;
    //     }
    //     subsolve(
    //         n,
    //         k - s,
    //         s,
    //         mul * binomial(s, k) * component_count(s),
    //         parts + 1,
    //         res,
    //     );
    // }

    // todo!()
}

fn subsolve2(k: usize, max_s: usize, components: usize, tot: usize, res: &mut [usize]) {
    // println!(
    //     "subsolve2(k={}, max_s={}, s_count={}, components={}, tot={})",
    //     k, max_s, s_count, components, tot
    // );

    if k == 0 {
        res[components - 1] = (res[components - 1] + tot) % MOD;
        return;
    }

    // Try all possible sizes for the next subset
    for s in 1..=max_s {
        // Try to repeat s many times
        let mut extra = 1;
        for i in 1.. {
            if k < i * s {
                break;
            }
            // let mut extra = 1;
            extra = (extra * ((component_count(s) * modbin(s, k - s * (i - 1))) % MOD)) % MOD;
            extra = (extra * modpow(i, MOD - 2)) % MOD;
            subsolve2(k - i * s, s - 1, components + i, (tot * extra) % MOD, res);
        }
    }
}

fn solve(n: usize) -> Vec<usize> {
    let mut res = vec![0; n];

    let mut calls = BTreeMap::new();
    calls.insert(Reverse((n, n, 0)), 1);
    while let Some(call) = calls.iter().next() {
        let (Reverse((k, max_s, components)), tot) = call;
        let (k, max_s, components, tot) = (*k, *max_s, *components, *tot);
        // Remove the call from the stack
        calls.remove(&Reverse((k, max_s, components)));

        if k == 0 {
            res[components - 1] = (res[components - 1] + tot) % MOD;
            continue;
        }

        for s in 1..=max_s {
            // Try to repeat s many times
            let mut extra = 1;
            for i in 1.. {
                if k < i * s {
                    break;
                }
                // let mut extra = 1;
                extra = (extra * ((component_count(s) * modbin(s, k - s * (i - 1))) % MOD)) % MOD;
                extra = (extra * modpow(i, MOD - 2)) % MOD;
                // subsolve2(k - i * s, s - 1, components + i, (tot * extra) % MOD, res);
                let e = calls
                    .entry(Reverse((k - i * s, s - 1, components + i)))
                    .or_insert(0);
                *e = (*e + tot * extra) % MOD;
            }
        }
    }

    // let mut res = vec![0; n];
    // // subsolve(n, n, n, 1, 0, &mut res);
    // subsolve2(n, n, 0, 1, &mut res);
    res.reverse();
    res
    // brute(n)
    // presolved(n)
}

fn main() {
    // unsafe {
    //     cc_int_v.push(0);
    // };
    // for i in 1..=1000 {
    //     unsafe {
    //         cc_int_v.push(component_count(i));
    //     };
    //     println!("{}", i);
    // }
    // println!("{:?}", unsafe { &cc_int_v });
    // println!("{:#?}", unsafe { &stats });

    // println!("{:?}", solve(4));
    // return;

    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for v in solve(n).into_iter().rev() {
        println!("{}", v);
    }
}

// These are correct!
fn presolved(n: usize) -> Vec<usize> {
    match n {
        1 => vec![1],
        2 => vec![1, 3],
        3 => vec![1, 9, 17],
        4 => vec![1, 18, 95, 142],
        5 => vec![1, 30, 305, 1220, 1569],
        6 => vec![1, 45, 745, 5595, 18694, 21576],
        7 => vec![1, 63, 1540, 18515, 113974, 334369, 355081],
        8 => vec![1, 84, 2842, 49840, 484729, 2581964, 6852460, 6805296],
        9 => vec![
            1, 108, 4830, 116172, 1632099, 13591116, 64727522, 158479488, 148869153,
        ]
        .into_iter()
        .map(|v| v % MOD)
        .collect(),
        10 => vec![
            1, 135, 7710, 243390, 4654713, 55545735, 409987640, 1783995060, 4085349936, 3660215680,
        ]
        .into_iter()
        .map(|v| v % MOD)
        .collect(),
        _ => unimplemented!(),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_component_count() {
        assert_eq!(component_count(1), 1);
        assert_eq!(component_count(2), 3);
        assert_eq!(component_count(3), 17);
        assert_eq!(component_count(4), 142);
        assert_eq!(component_count(5), 1569);
        assert_eq!(component_count(6), 21576);
    }

    #[test]
    fn test_samples() {
        assert_eq!(solve(1), vec![1]);
        assert_eq!(solve(2), vec![1, 3]);
        assert_eq!(solve(3), vec![1, 9, 17]);
        assert_eq!(solve(4), vec![1, 18, 95, 142]);
        assert_eq!(solve(5), vec![1, 30, 305, 1220, 1569]);
        assert_eq!(solve(6), vec![1, 45, 745, 5595, 18694, 21576]);
        assert_eq!(solve(7), vec![1, 63, 1540, 18515, 113974, 334369, 355081]);
        assert_eq!(
            solve(8),
            vec![1, 84, 2842, 49840, 484729, 2581964, 6852460, 6805296]
        );
        assert_eq!(
            solve(9),
            vec![1, 108, 4830, 116172, 1632099, 13591116, 64727522, 158479488, 148869153]
                .into_iter()
                .map(|v| v % MOD)
                .collect::<Vec<_>>()
        );
        assert_eq!(
            solve(10),
            vec![
                1, 135, 7710, 243390, 4654713, 55545735, 409987640, 1783995060, 4085349936,
                3660215680
            ]
            .into_iter()
            .map(|v| v % MOD)
            .collect::<Vec<_>>()
        );
        assert_eq!(
            solve(40),
            vec![
                966304277, 901371771, 759195442, 790481422, 122682607, 392000511, 435273028,
                966862670, 519723765, 30990597, 409125383, 2747902, 991199820, 296158387,
                176180602, 705066532, 401482496, 729626017, 207125017, 370405201, 417625468,
                45251194, 43175771, 793569343, 636114057, 198624360, 60099897, 166113870,
                925098106, 822029583, 434471173, 494653166, 760704585, 478566338, 96374759,
                235711347, 903105353, 2635490, 2340, 1
            ]
            .into_iter()
            .rev()
            .collect::<Vec<_>>()
        );
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED