ashiato45

mod nary_exp{
    struct NaryExpander{
        n: i64,
        base: i64,
        powered: i64
    }

    impl NaryExpander{
        fn new(n: i64, base: i64) -> NaryExpander{
            let mut powered = (0..).map(|i|{base.pow(i)}).find(|i|{*i > n}).unwrap();

ashiato45

mod arith_util{
    pub fn div(a: i64, b: i64) -> (i64, i64){
        let q = a/b;
        let r = a % b;
        if r < 0{
            return (q-1, r + b);
        }else{
            return (q, r);
        }
    }

ashiato45

#[derive(Eq, PartialEq)]
struct Item {
    date: usize,
    cost: usize,
}

macro_rules! easy_ord {
    ($y:ident, $x:expr) => {
        impl Ord for $y {
            fn cmp(&self, other: &Self) -> std::cmp::Ordering {

ashiato45

        match s[i-1].as_str(){
            "AND" => {
            },
            "OR" => {
                res = 2i64.pow(i as u32) + res;
            },
            _ => panic!()
        }

ashiato45

fn divmod(a: i64, b: i64) -> (i64, i64){
    let (q, r) = (a/b, a%b);
    if r < 0{
        return (q-1, r+b);
    }else{
        return (q, r);
    }
}

fn divdown(a: i64, b: i64) -> i64{

ashiato45

mod fenwick{
    pub struct Fenwick{
        data: Vec<i64>,
        n_leaves: usize
    }

    impl Fenwick{
        pub fn new(n: usize) -> Self{
            // n以上の最小の2羃をさがす
            let n_leaves = (0..).map(|i| 2usize.pow(i)).find(|&i| {i >= n}).unwrap();

ashiato45

mod inf_num{
    use std::fmt;
    use std::ops::*;
    
    pub trait Base: Ord + std::fmt::Display + Add<Output=Self> + Neg<Output=Self> + Mul<Output=Self> + Sized + Clone + fmt::Debug {
        fn zero() -> Self;
    }

    impl Base for i64{

ashiato45

mod bv_util{
    pub fn fill(n: usize) -> u64{
        return (1 << n) - 1;
    }

    pub fn subtract(a: u64, b: u64) -> u64{
        return a & (!b);
    }

    pub fn is_on(a: u64, pos: usize) -> bool{

ashiato45

#[derive(Eq, PartialEq,)]
struct Item{
    dist: INF64,
    pos: usize
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        if self.dist < other.dist{
            std::cmp::Ordering::Greater

ashiato45

use proconio::input;
use proconio::marker::Usize1;
use num::integer::gcd;
use std::collections::{HashMap, HashSet, BinaryHeap};


fn main() {
    let mut n: usize;
    input!{
        n: usize,