// codesnip-guard: extgcd
#[cfg_attr(any(),rustfmt::skip)]pub fn extgcd(mut a:i64,mut b:i64)->(i64,i64,i64){let(mut u,mut v,mut x,mut y)=(1,0,0,1);while a!=0{let k=b/a;x-=k*u;y-=k*v;b-=k*a;std::mem::swap(&mut x,&mut u);std::mem::swap(&mut y,&mut v);std::mem::swap(&mut b,&mut a);}(b,x,y)}