結果
| 問題 | No.3070 ソラニン |
| ユーザー |
 43flyingcar
|
| 提出日時 | 2020-07-09 02:46:51 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 33,192 bytes |
| コンパイル時間 | 14,680 ms |
| コンパイル使用メモリ | 389,268 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-05 13:40:43 |
| 合計ジャッジ時間 | 15,480 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
コンパイルメッセージ
warning: unused import: `std::cmp::min`
--> src/main.rs:63:5
|
63 | use std::cmp::min;
| ^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `std::collections::BTreeMap`
--> src/main.rs:64:5
|
64 | use std::collections::BTreeMap;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::process`
--> src/main.rs:65:5
|
65 | use std::process;
| ^^^^^^^^^^^^
warning: unused import: `std::collections::HashSet`
--> src/main.rs:68:5
|
68 | use std::collections::HashSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unused import: `std::collections::BTreeSet`
--> src/main.rs:70:5
|
70 | use std::collections::BTreeSet;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: unnecessary parentheses around `while` condition
--> src/main.rs:287:10
|
287 | while(n>0){
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
287 - while(n>0){
287 + while n>0 {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:332:11
|
332 | if(self.par[x] == x){
| ^ ^
|
help: remove these parentheses
|
332 - if(self.par[x] == x){
332 + if self.par[x] == x {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:349:16
|
349 | if (self.rank[x] < self.rank[y]){
| ^ ^
|
help: remove these parentheses
|
349 - if (self.rank[x] < self.rank[y]){
349 + if self.rank[x] < self.rank[y] {
|
warning: unnecessary parentheses around `if` condition
--> src/main.rs:360:19
|
360 | if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;}
| ^ ^
|
help: remove these parentheses
|
360 - if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;}
360 +
ソースコード
#[allow(unused_macros)]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let mut $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, bytes) => {
read_value!($next, String).into_bytes()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
use std::cmp::Ordering;
use std::cmp;
use std::cmp::min;
use std::collections::BTreeMap;
use std::process;
use std::cmp::Ord;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::mem;
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};
// ---------- begin ModInt ----------
#[derive(Clone, Copy)]
struct ModInt(usize);
impl std::ops::Add for ModInt {
type Output = ModInt;
fn add(self, rhs: ModInt) -> Self::Output {
let mut d = self.0 + rhs.0;
if d >= MODu {
d -= MODu;
}
ModInt(d)
}
}
impl std::ops::AddAssign for ModInt {
fn add_assign(&mut self, rhs: ModInt) {
*self = *self + rhs;
}
}
impl std::ops::Sub for ModInt {
type Output = ModInt;
fn sub(self, rhs: ModInt) -> Self::Output {
let mut d = self.0 + MODu - rhs.0;
if d >= MODu {
d -= MODu;
}
ModInt(d)
}
}
impl std::ops::SubAssign for ModInt {
fn sub_assign(&mut self, rhs: ModInt) {
*self = *self - rhs;
}
}
impl std::ops::Mul for ModInt {
type Output = ModInt;
fn mul(self, rhs: ModInt) -> Self::Output {
ModInt((self.0 as u64 * rhs.0 as u64 % MODu as u64) as usize)
}
}
impl std::ops::MulAssign for ModInt {
fn mul_assign(&mut self, rhs: ModInt) {
*self = *self * rhs;
}
}
impl std::ops::Neg for ModInt {
type Output = ModInt;
fn neg(self) -> Self::Output {
ModInt(if self.0 == 0 {0} else {MODu - self.0})
}
}
impl std::fmt::Display for ModInt {
fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
impl std::str::FromStr for ModInt {
type Err = std::num::ParseIntError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let val = s.parse::<usize>()?;
Ok(ModInt::new(val))
}
}
impl PartialEq for ModInt {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0
}
}
impl Hash for ModInt {
fn hash<H: Hasher>(&self, state: &mut H) {
self.0.hash(state);
self.0.hash(state);
}
}
impl Eq for ModInt {}
#[allow(dead_code)]
impl ModInt {
pub fn new(n: usize) -> ModInt {
ModInt(n % MODu)
}
pub fn zero() -> ModInt {
ModInt(0)
}
pub fn one() -> ModInt {
ModInt(1)
}
pub fn pow(self, mut n: usize) -> ModInt {
let mut t = ModInt::one();
let mut s = self;
while n > 0 {
if n & 1 == 1 {
t *= s;
}
s *= s;
n >>= 1;
}
t
}
pub fn inv(self) -> ModInt {
self.pow(MODu - 2)
}
}
// ---------- end ModInt ----------
/// Equivalent to std::lowerbound and std::upperbound in c++
pub trait BinarySearch<T> {
fn lower_bound(&self, x:&T) -> usize;
fn upper_bound(&self, x:&T) -> usize;
}
impl<T: Ord> BinarySearch<T> for VecDeque<T>{
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}
impl<T: Ord> BinarySearch<T> for [T]{
fn lower_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less => {
low = mid + 1;
}
Ordering::Equal | Ordering::Greater => {
high = mid;
}
}
}
low
}
fn upper_bound(&self, x: &T) -> usize {
let mut low = 0;
let mut high = self.len();
while low != high {
let mid = (low + high) / 2;
match self[mid].cmp(x) {
Ordering::Less | Ordering::Equal => {
low = mid + 1;
}
Ordering::Greater => {
high = mid;
}
}
}
low
}
}
fn matmul(A:&Vec<Vec<i64>>, B:&Vec<Vec<i64>>) -> Vec<Vec<i64>>{
let mut C = vec![vec![0;B[0].len()];A.len()];
for i in 0..A.len(){
for k in 0..B.len(){
for j in 0..B[0].len(){
C[i][j] += A[i][k]*B[k][j];
C[i][j] %= MOD;
}
}
}
return C;
}
fn matpow(A:&mut Vec<Vec<i64>>, n:usize) -> Vec<Vec<i64>>{
let mut B = vec![vec![0;A.len()];A.len()];
for i in 0..A.len(){
B[i][i] = 1;
}
let mut n = n;
let mut tmp = A.clone();
while(n>0){
if n&1 == 1{B = matmul(&B, &tmp);}
tmp = matmul(&tmp, &tmp);
n>>=1;
}
return B;
}
fn divisor(n:usize) -> Vec<usize>{
let mut res:Vec<usize> = Vec::new();
for i in 1..n+1{
if i*i>n{break;}
if n%i == 0{
res.push(i);
if i != n/i{
res.push(n/i);
}
}
}
res
}
struct UnionFind{
par:Vec<usize>,
rank:Vec<usize>,
size:Vec<usize>,
size_edge:Vec<usize>,
}
impl UnionFind{
fn init(n:usize) -> UnionFind{
let mut par = vec![0;n];
for i in 0..n{
par[i] = i;
}
UnionFind{
par:par,
rank:vec![0;n],
size:vec![1;n],
size_edge:vec![0;n],
}
}
fn find(&mut self, x:usize) ->usize{
if(self.par[x] == x){
x
}
else{
let p = self.par[x];
let res = self.find(p);
self.par[x] = res;
res
}
}
fn same(&mut self, a:usize, b:usize)->bool{
self.find(a) == self.find(b)
}
fn unite(&mut self, a:usize, b:usize){
let x = self.find(a);
let y = self.find(b);
if x != y{
if (self.rank[x] < self.rank[y]){
self.par[x] = y;
self.size[y] += self.size[x];
self.size_edge[y] += self.size_edge[x];
self.size_edge[y] += 1;
}
else{
self.par[y] = x;
self.size[x] += self.size[y];
self.size_edge[x] += self.size_edge[y];
self.size_edge[x] += 1;
if(self.rank[x] == self.rank[y]){ self.rank[x]+=1;}
}
}
else{
self.size_edge[x] += 1;
}
}
fn check_size(&mut self, a:usize) -> usize{
let x = self.find(a);
let s = self.size[x];
s
}
}
pub struct Scanner<R> {
stdin: R,
}
impl<R: std::io::Read> Scanner<R> {
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.stdin
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
.collect::<Vec<_>>();
std::str::from_utf8(&buf).unwrap()
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}
struct LazySegTree<BiOp> {
n: usize,
val: Vec<i64>,
ma:Vec<i64>,
op: BiOp,
e: i64,
upe:i64,
inf:i64,
}
impl<BiOp> LazySegTree<BiOp>
where BiOp: Fn(i64, i64) -> i64{
pub fn new(n_: usize, op: BiOp, e: i64, upe:i64, inf:i64) -> Self {
let mut n = 1;
while n < n_ { n *= 2; } // n is a power of 2
LazySegTree {n: n, val: vec![e; 2 * n ], ma:vec![upe;2*n], op: op, e: e, upe:upe, inf:inf}
}
pub fn query(&self, x:usize, y:usize, l:usize, r:usize, k:usize) -> i64 {
if (r<=x || y<=l) {return self.inf;}
if (x<=l && r<=y) {return self.ma[k];}
let mut L = self.query(x,y,l,(l+r)/2, k*2);
let mut R = self.query(x,y,(l+r)/2,r, k*2+1);
return self.val[k] + (self.op)(L, R);
}
pub fn update(&mut self, x:usize, y:usize, v:i64, l:usize,r:usize, k:usize) {
if (l>=r) {return;}
if (x<=l && r<=y){
self.val[k]+=v;
self.ma[k]+=v;
}
else if(l<y && x<r){
self.update(x, y, v, l, (l+r)/2, k*2);
self.update(x,y,v,(l+r)/2,r, k*2+1);
self.ma[k] = self.val[k] + (self.op)(self.ma[k*2], self.ma[k*2+1]);
}
}
}
fn modinv(a:ModInt)->ModInt{
let mut a = a.0 as usize;
let mut b = MODu as i64;
let mut u = 1 as i64;
let mut v = 0 as i64;
let mut a = a as i64;
let mut m = MODu as i64;
while(b>0){
let mut t = a/b;
a -= t*b;
mem::swap(&mut a, &mut b);
u-=t*v;
mem::swap(&mut u, &mut v);
}
u%=m;
if u<0{u+=m;}
return ModInt(u as usize);
}
fn modinv2(a:usize)->usize{
let mut a = a as usize;
let mut b = MODu as i64;
let mut u = 1 as i64;
let mut v = 0 as i64;
let mut a = a as i64;
let mut m = MODu as i64;
while(b>0){
let mut t = a/b;
a -= t*b;
mem::swap(&mut a, &mut b);
u-=t*v;
mem::swap(&mut u, &mut v);
}
u%=m;
if u<0{u+=m;}
return u as usize;
}
fn modpow(x:ModInt, n:ModInt) -> ModInt{
let mut ans = ModInt(1);
let mut n = n.0 as usize;
let mut x = x;
while(n != 0){
if (n&1 == 1){ans = ans*x;}
x = x*x;
n = n>>1;
}
ans
}
fn comb(a:usize, b:usize, fac:&Vec<ModInt>, ifac:&Vec<ModInt>)->ModInt{
let mut a = a;
let mut b = b;
if a == 0 && b == 0{return ModInt(1);}
if a<b || a<0{return ModInt(0);}
let mut tmp = ifac[a-b]*ifac[b];
return tmp * fac[a];
}
fn invs()->(Vec<ModInt>, Vec<ModInt>){
let mut fac = vec![ModInt(0);600001];
let mut ifac = vec![ModInt(0);600001];
fac[0] = ModInt(1);
ifac[0] = ModInt(1);
for i in 0..600000{
fac[i+1] = fac[i] * ModInt(i+1);
ifac[i+1] = ifac[i] * modpow(ModInt(i+1), ModInt(MODu - 2));
}
(fac, ifac)
}
struct ConvexHallTrick {
Q: Vec<(i64, i64)>,
}
impl ConvexHallTrick{
pub fn new() -> Self {
ConvexHallTrick {Q: Vec::new()}
}
pub fn calc(&self, p:(i64, i64), x:i64)->i64{
return p.0 * x + p.1;
}
pub fn dodo(& self, A:(i64, i64), B:(i64, i64), C:(i64, i64)) -> bool{
//max or min
(A.1 - C.1) * (B.0 - A.0) <= (A.1 - B.1)*(C.0 - A.0)
}
pub fn add(&mut self, a:i64, b:i64){
self.Q.push((a, b));
let mut v = self.Q.len();
while(v >=3 && self.dodo(self.Q[v-3], self.Q[v-2], self.Q[v-1])){
self.Q[v-2] = self.Q[v-1];
self.Q.pop();
v = self.Q.len();
}
}
pub fn query(& self, x:i64) -> i64{
let mut L = -1;
let mut R = (self.Q.len() - 1) as i64;
while(R-L>1){
let mut m = (L+R)/2;
if self.calc(self.Q[m as usize], x)>=self.calc(self.Q[m as usize+1], x){
L=m;
}
else{
R=m;
}
}
return self.calc(self.Q[R as usize], x);
}
}
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);
impl<T: PartialOrd> PartialOrd for Rev<T> {
fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {
other.0.partial_cmp(&self.0)
}
}
impl<T: Ord> Ord for Rev<T> {
fn cmp(&self, other: &Rev<T>) -> Ordering {
other.0.cmp(&self.0)
}
}
fn sieve(n:usize) -> (Vec<bool>, Vec<usize>){
let mut p:usize = 0;
let mut is_prime = vec![false; n+1];
let mut prime = Vec::new();
for i in 0..n+1{
is_prime[i] = true;
}
is_prime[0] = false;
is_prime[1] = false;
for i in 2..n+1{
if is_prime[i]{
prime.push(i as usize);
let mut j = 2*i;
while(j<=n){
is_prime[j] = false;
j+=i;
}
}
}
(is_prime, prime)
}
fn nHr(n:usize, r:usize, fac:&Vec<ModInt>, ifac:&Vec<ModInt>) -> ModInt{
comb(n + r - 1, r, fac, ifac)
}
fn gcd(a:usize, b:usize)->usize{
if b==0{return a;}
return gcd(b, a%b);
}
fn lcm(a:usize, b:usize)->usize{
return (b/gcd(a, b))*a;
}
struct SegTree_MOD<BiOp> {
n: usize,
dat: Vec<i64>,
op: BiOp,
e: i64,
mod_:i64,
}
impl<BiOp> SegTree_MOD<BiOp>
where BiOp: Fn(i64, i64) -> i64
{
pub fn new(n_: usize, op: BiOp, e: i64, mod_:i64) -> Self {
let mut n = 1;
while n < n_ { n *= 2; } // n is a power of 2
SegTree_MOD {n: n, dat: vec![e; 2 * n - 1], op: op, e: e, mod_:mod_}
}
/* ary[k] <- v */
pub fn update(&mut self, idx: usize, v: i64) {
let mut k = idx + self.n - 1;
self.dat[k] = v;
while k > 0 {
k = (k - 1) / 2;
self.dat[k] = (self.op)(self.dat[2 * k + 1], self.dat[2 * k + 2]);
self.dat[k] %= self.mod_;
}
}
/* [a, b) (note: half-inclusive)
* http://proc-cpuinfo.fixstars.com/2017/07/optimize-segment-tree/ */
pub fn query(&self, mut a: usize, mut b: usize) -> i64 {
let mut left = self.e;
let mut right = self.e;
a += self.n - 1;
b += self.n - 1;
while a < b {
if (a & 1) == 0 {
left = (self.op)(left, self.dat[a]);
left %= self.mod_;
}
if (b & 1) == 0 {
right = (self.op)(self.dat[b - 1], right);
right %= self.mod_;
}
a = a / 2;
b = (b - 1) / 2;
}
let mut res = (self.op)(left, right);
res %= self.mod_;
res
}
}
fn modpow2(x:usize, n:usize) -> usize{
let mut ans = 1;
let mut n = n;
let mut x = x;
while(n != 0){
if (n&1 == 1){ans = ans*x%MODu;}
x = x*x%MODu;
n = n>>1;
}
ans
}
#[derive(Clone)]
struct PPUnionFind{
par:Vec<usize>,
rank:Vec<usize>,
time:Vec<usize>,
now:usize,
history:Vec<(usize, usize)>,
}
impl PPUnionFind{
fn init(n:usize) -> PPUnionFind{
let mut par = vec![0;n];
for i in 0..n{
par[i] = i;
}
PPUnionFind{
par:par,
rank:vec![0;n],
time:vec![INF as usize;n],
now:0,
history:vec![],
}
}
fn find(&mut self, t:usize, x:usize) ->usize{
if self.time[x] > t{return x;}
else { let tt = self.par[x]; return self.find(t, tt);}
}
fn unite(&mut self, x:usize, y:usize) -> usize{
self.now+=1;
let mut x = x;
let mut y = y;
let nc = self.now;
x = self.find(nc, x);
y = self.find(nc, y);
if x == y{return self.now;}
if self.par[x] < self.par[y] {mem::swap(&mut x, &mut y);}
self.par[x] += self.par[y];
self.history.push((self.now, self.par[x]));
self.par[y] = x;
self.time[y] = self.now;
return self.now;
}
}
fn prim(cost:&Vec<Vec<(usize, i64)>>, vs:usize)->i64{
let mut used = vec![false; vs];
let mut bh = BinaryHeap::new();
for j in 0..cost[0].len(){
bh.push((cost[0][j].1 * -1, cost[0][j].0));
}
used[0] = true;
let mut res = 0;
while(bh.len()!=0){
let mut m = bh.pop().unwrap();
if used[m.1]{continue;}
used[m.1] = true;
for e in 0..cost[m.1].len(){
if used[cost[m.1][e].0] == false{
bh.push((cost[m.1][e].1 * -1, cost[m.1][e].0));
}
}
res += m.0*-1;
}
return res;
}
fn kruscal(cost:&mut Vec<(i64, usize, usize)>, vs:usize)->i64{
cost.sort();
let mut uf = UnionFind::init(vs);
let mut res = 0;
for i in 0..cost.len(){
let e = cost[i].clone();
if uf.find(e.1) != uf.find(e.2){
uf.unite(e.1, e.2);
res += e.0;
}
}
return res;
}
fn kruscal3(cost:&mut Vec<(f64, usize, usize, usize)>, vs:usize)->(UnionFind, Vec<usize>) {
cost.sort_by(|a, b| (&a.0).partial_cmp(&b.0).unwrap());
let mut uf = UnionFind::init(vs);
let mut res = 0.0;
let mut rv = Vec::new();
let mut c = 0.0;
let mut t = 0.0;
for i in 0..cost.len(){
let e = cost[i].clone();
if uf.find(e.1) != uf.find(e.2){
uf.unite(e.1, e.2);
rv.push(e.3);
}
}
return (uf,rv);
}
fn kruscal2(cost:&mut Vec<(f64, usize, usize)>, vs:usize)->f64{
cost.sort_by(|a, b| (&a.0).partial_cmp(&b.0).unwrap());
let mut uf = UnionFind::init(vs);
let mut res = 0.0;
for i in 0..cost.len(){
let e = cost[i].clone();
if uf.find(e.1) != uf.find(e.2){
uf.unite(e.1, e.2);
res+= e.0;
}
}
return res;
}
struct segtree<I, Op>{
n: usize,
dat: Vec<I>,
op:Op,
e:I,
}
impl<I, Op> segtree<I, Op>
where Op: Fn(I, I) -> I, I:Copy{
pub fn new(n_:usize, op: Op, e:I)->Self{
let mut n = 1;
while(n<n_){n*=2;}
segtree{n: n, dat:vec![e; 2*n-1], op:op, e:e}
}
pub fn update(&mut self, k:usize, a:I){
let mut k = k;
k += self.n-1;
self.dat[k] = a;
while(k>0){
k = (k-1)/2;
self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]);
}
}
pub fn query(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{
if r<=a || b<=l{return self.e;}
if a<=l && r<=b{return self.dat[k];}
else{
let mut vl = self.query(a, b, k*2+1, l, (l+r)/2);
let mut vr = self.query(a, b, k*2+2, (l+r)/2, r);
return (self.op)(vl, vr);
}
}
}
struct BIT<I, Op>{
n:usize,
bit:Vec<I>,
op:Op,
e:I,
ini:I,
}
impl <I, Op> BIT<I, Op>
/* 1-index*/
where Op: Fn(I, I) -> I, I:Copy{
pub fn new(n_:usize, op:Op, e:I, ini:I)->Self{
BIT{n:n_, bit:vec![e;n_+1], op:op, e:e, ini:ini}
}
pub fn sum(&self, i:usize)->I{
let mut s = self.ini;
let mut i = i as i64;
while(i>0){
s = (self.op)(s, self.bit[i as usize]);
i -= i & -i;
}
return s;
}
pub fn add(&mut self, i:usize, x:I){
let mut i = i as i64;
while(i<=self.n as i64){
self.bit[i as usize] = (self.op)(self.bit[i as usize], x);
i += i & -i;
}
}
}
struct Dsegtree{
n: usize,
datA: Vec<i64>,
datB:Vec<i64>,
e:i64,
}
impl Dsegtree{
pub fn new(n_:usize, e:i64)->Self{
Dsegtree{n:n_, datA:vec![e; 1<<22 - 1], datB:vec![e;1<<22 - 1], e:e}
}
pub fn update(&mut self,a:usize, b:usize, x:i64, k:usize, l:usize, r:usize){
//println!("{} {} {} {} {} {}", a, b, x, k , l, r);
if a<=l && r<=b{
self.datA[k] += x;
}
else if (l<b && a<r){
self.datB[k] += (cmp::min(b, r) as i64 - cmp::max(a, l) as i64) * x;
self.update(a, b, x, k*2+1, l, (l+r)/2);
self.update(a, b, x, k*2+2, (l+r)/2, r);
}
}
pub fn query(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> i64{
if (b<=l || r<=a){
return 0;
}
else if (a<=l && r<=b){
return self.datA[k] * ((r as i64-l as i64)) + self.datB[k];
}
else{
let mut res = (cmp::min(b, r) as i64 - cmp::max(a, l) as i64)* self.datA[k];
res += self.query(a, b, k*2+1, l, (l+r)/2);
res += self.query(a, b, k*2+2, (l+r)/2, r);
return res;
}
}
}
/*
unwrap_or_else
*/
fn prime_factor(n:usize)->HashMap<usize, usize>{
let mut res = HashMap::new();
let mut n = n;
for i in 2..n{
if i*i>n{break;}
while(n%i==0){
*res.entry(i).or_insert(0)+=1;
n/=i;
}
}
if n != 1{
res.insert(n, 1);
}
res
}
struct rollinghash{
base:Vec<i64>,
Mod:Vec<i64>,
hash:Vec<Vec<i64>>,
power:Vec<Vec<i64>>,
}
impl rollinghash{
pub fn new(s:&Vec<usize>)->Self{
let mut n = s.len();
let mut base = vec![1007, 2009];
let mut hash = vec![vec![0;n+1];2];
let mut power = vec![vec![1;n+1];2];
let mut Mod = vec![1000000007, 1000000009];
for iter in 0..2{
let mut ht = vec![0;n+1];
let mut pt = vec![1;n+1];
for i in 0..n{
hash[iter][i+1] = (hash[iter][i] * base[iter] + s[i] as i64) % Mod[iter];
power[iter][i+1] = power[iter][i] * base[iter] % Mod[iter];
}
}
return rollinghash{base:base, Mod:Mod, hash:hash, power:power}
}
pub fn get(&self, l:usize, r:usize)->(i64, i64){
let mut res = self.hash[0][r] - self.hash[0][l] * self.power[0][r-l] % self.Mod[0];
if res<0{
res += self.Mod[0];
}
let mut res2 = self.hash[1][r] - self.hash[1][l] * self.power[1][r-l] % self.Mod[1];
if res2<0{
res2 += self.Mod[1];
}
return (res, res2);
}
}
struct LCA{
G:Vec<Vec<(usize, i64)>>,
depth:Vec<i64>,
len:Vec<i64>,
parent:Vec<Vec<usize>>,
V:usize,
logV:usize,
}
impl LCA{
pub fn new(V:usize, G:&Vec<Vec<(usize, i64)>>)->Self{
let mut logV = 0;
while(V>(1<<logV)){logV+=1;}
return LCA{G:G.clone(), logV:logV, V:V, depth:vec![0;V], len:vec![0;V], parent:vec![vec![INFu;V];logV]}
}
pub fn init(&mut self, v:usize, par:usize, d:i64, l:i64){
self.depth[v] = d;
self.parent[0][v] = par;
self.len[v] = l;
for i in 0..self.G[v].len(){
let mut w = self.G[v][i].0;
let mut lc = self.G[v][i].1;
if w == par{continue;}
self.init(w, v, d+1, lc+l);
}
}
pub fn build(&mut self, root:usize){
self.init(root, INFu, 0, 0);
for k in 0..(self.logV-1){
for v in 0..self.V{
if self.parent[k][v] == INFu{
self.parent[k+1][v] = INFu;
}
else{
self.parent[k+1][v] = self.parent[k][self.parent[k][v]];
}
}
}
}
pub fn lca(&self, u:usize, v:usize)->usize{
let mut u = u;
let mut v = v;
if self.depth[u]>self.depth[v]{
mem::swap(&mut u, &mut v);
}
for k in 0..self.logV{
if ((self.depth[v]-self.depth[u]) >> k) & 1 == 1{
v = self.parent[k][v];
}
}
if u == v{
return u;
}
for k in (0..self.logV).rev(){
if self.parent[k][u] != self.parent[k][v]{
u = self.parent[k][u];
v = self.parent[k][v];
}
}
return self.parent[0][u];
}
pub fn dist(&self, u:usize, v:usize)->i64{
let z = self.lca(u, v);
return self.len[u]+self.len[v]-2*self.len[z];
}
}
fn fast_prime_factor_table(ma:usize)->Vec<usize>{
let mut p = sieve(1001);
let mut minf = vec![0;ma];
for j in 0..p.1.len(){
let P = p.1[j];
let mut now = P;
for i in 2..ma{
if minf[now] ==0{
minf[now] = P;
}
now+=P;
if now>=ma{
break;
}
}
}
return minf;
}
fn area_rectanble(x1:f64, x2:f64, x3:f64, y1:f64, y2:f64, y3:f64)->f64{
let tmp = x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;
tmp.abs()/2.0
}
#[derive(PartialEq, Clone)]
struct FW(f64);
impl Eq for FW {}
impl PartialOrd for FW {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
self.0.partial_cmp(&other.0)
}
}
impl Ord for FW {
fn cmp(&self, other: &FW) -> Ordering {
other.partial_cmp(self).unwrap()
}
}
/* parsing
fn expr(s:&Vec<char>, i:&mut usize) -> Vec<usize>{
let mut val = term(s, i);
while(*i<s.len() && (s[*i] == '+' || s[*i] == '-')){
let mut op = encode(s[*i]);
*i+=1;
let mut val2 = term(s, i);
val = cal(val, val2, op);
}
return val;
}
fn term(s:&Vec<char>, i:&mut usize) -> Vec<usize>{
let mut val = factor(s, i);
while(*i<s.len() && s[*i] == '*'){
let mut op = encode(s[*i]);
*i+=1;
let mut val2 = factor(s, i);
val = cal(val, val2, op);
}
return val;
}
fn factor(s:&Vec<char>, i:&mut usize)->Vec<usize>{
if s[*i] == 'R' || s[*i] == 'S' || s[*i] == 'P' || s[*i] == '?'{
let mut res = encode(s[*i]);
*i+=1;
return res;
}
*i+=1;
let mut ret = expr(s, i);
*i+=1;
return ret;
}
*/
fn matmulf64(A:&Vec<Vec<f64>>, B:&Vec<Vec<f64>>) -> Vec<Vec<f64>>{
let mut C = vec![vec![0.0;B[0].len()];A.len()];
for i in 0..A.len(){
for k in 0..B.len(){
for j in 0..B[0].len(){
C[i][j] += A[i][k]*B[k][j];
}
}
}
return C;
}
//sort_by_key(|a| vec![a[0], -a[1]]);
//v.sort_by(|a, b| a.partial_cmp(b).unwrap());
fn fact_mod(n:usize)->usize {
let mut f = 1;
for i in 2..n+1{
f = f * (i % MODu) % MODu;
}
return f;
}
fn mod_pow(x:usize, n:usize) ->usize{
if(n == 0){ return 1;}
let mut res = mod_pow((x * x) % MODu, n / 2 );
if(n & 1 == 1){ res = (res * x) % MODu;}
return res;
}
fn comb2(n:usize, r:usize)->usize {
let mut n = n;
let mut r = r;
if(r > n-r) {r = n-r;}
if(r == 0) {return 1;}
let mut a = 1;
for i in 0..r{
a = a * ((n-i) % MODu) % MODu;
}
let mut b = mod_pow(fact_mod(r), MODu-2);
return (a % MODu) * (b % MODu) % MODu;
}
struct scc{
G:Vec<Vec<usize>>,
rG:Vec<Vec<usize>>,
vs:Vec<usize>,
used:Vec<bool>,
cmp:Vec<usize>,
}
impl scc{
pub fn new(N:usize, G:&Vec<Vec<usize>>, rG:&Vec<Vec<usize>>)->Self{
scc{G:G.clone(), rG:rG.clone(), vs:vec![], used:vec![false;N], cmp:vec![0;N]}
}
pub fn add_edge(&mut self, from:usize, to:usize){
self.G[from].push(to);
self.rG[to].push(from);
}
pub fn dfs(&mut self, v:usize){
self.used[v] = true;
for i in 0..self.G[v].len(){
let t = self.G[v][i];
if !self.used[t]{
self.dfs(t);
}
}
self.vs.push(v);
}
pub fn rdfs(&mut self, v:usize, k:usize){
self.used[v] = true;
self.cmp[v] = k;
for i in 0..self.rG[v].len(){
let t = self.rG[v][i];
if !self.used[t]{
self.rdfs(t, k);
}
}
}
pub fn scc(&mut self)->usize{
for v in 0..self.G.len(){
if !self.used[v]{
self.dfs(v);
}
}
self.used = vec![false;self.used.len()];
let mut k = 0;
for i in (0..self.vs.len()).rev(){
if !self.used[self.vs[i]]{
let t = self.vs[i];
self.rdfs(t, k);
k+=1;
}
}
k
}
}
#[macro_use]
fn modpow3(x:usize, n:usize,m:usize) -> usize{
let mut ans = 1;
let mut n = n;
let mut x = x;
x%=m;
while(n != 0){
if (n&1 == 1){ans = ans*x%m;}
x = x*x%m;
n = n>>1;
}
ans%m
}
fn cal1(x:usize, n:usize, m:usize, h:&mut HashMap<usize, usize>)->usize{
if h.contains_key(&n){
return h[&n];
}
if n == 1{
return x;
}
if n == 0{
return 0;
}
let mut res = 0;
let mut a = n/2;
let mut b = n-a;
res = cal1(x, b, m, h)%m;
res = ((res*modpow3((10)%m, a*x.to_string().len(), m)%m)%m + cal1(x, a, m, h)%m)%m;
h.insert(n, res);
return res;
}
fn cal2(x:usize, n:usize, m:usize, h:&mut HashMap<usize, usize>, l:usize)->usize{
if h.contains_key(&n){
return h[&n];
}
if n == 1{
return x;
}
if n == 0{
return 0;
}
let mut res = 0;
let mut a = n/2;
let mut b = n-a;
res = cal2(x, b, m, h, l)%m;
res = ((res*modpow3((10)%m, a*l, m)%m)%m + cal2(x, a, m, h, l)%m)%m;
h.insert(n, res);
return res;
}
fn modinv3(a:usize, m:usize)->usize{
let mut a = a as usize;
let mut b = m as i64;
let mut u = 1 as i64;
let mut v = 0 as i64;
let mut a = a as i64;
let mut m = m as i64;
while(b>0){
let mut t = a/b;
a -= t*b;
mem::swap(&mut a, &mut b);
u-=t*v;
mem::swap(&mut u, &mut v);
}
u%=m;
if u<0{u+=m;}
return u as usize;
}
fn dijkstra(s:usize, g:&Vec<Vec<(usize, i64)>>)->Vec<i64>{
let mut dist = vec![INF;g.len()];
dist[s] = 0;
let mut h = BinaryHeap::new();
h.push((0, s));
while(h.len() != 0){
let mut t = h.pop().unwrap();
let mut d = t.0 * -1;
let mut v = t.1;
if dist[v]<d{
continue;
}
for i in 0..g[v].len(){
let n = g[v][i].0;
let dd = g[v][i].1;
if dist[n]>d+dd{
dist[n] = d+dd;
h.push((dist[n]*-1, n));
}
}
}
return dist;
}
fn dijkstra2(s:usize, g:&Vec<Vec<(usize, i64)>>)->Vec<i64>{
let mut dist = vec![INF;g.len()];
dist[s] = 0;
let mut h = BinaryHeap::new();
h.push((0, s));
while(h.len() != 0){
let mut t = h.pop().unwrap();
let mut d = t.0 * -1;
let mut v = t.1;
if dist[v]<d{
continue;
}
for i in 0..g[v].len(){
let n = g[v][i].0;
let dd = g[v][i].1;
if dist[n]>d+dd{
dist[n] = d+dd;
h.push((dist[n]*-1, n));
}
}
}
return dist;
}
fn solve(){
let sssss = std::io::stdin();
let mut sc = Scanner { stdin: sssss.lock() };
println!("77115 4651");
}
fn main(){
solve();
}
const PI:f64 = std::f64::consts::PI;
pub static MOD:i64 = 1000000007;
pub static MODu:usize = 1000000007;
pub static MODi32:i32 = 1000000007;
pub static eps:f64 = 1e-6;
const INF: i64 = 1 << 62;
const INFu:usize = 1<<62;