template<class S>inlinevoid arrInsert(constint k, int&sz, S a[], const S aval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i]= a[i-1];
}
a[k]= aval;
}
template<class S, class T>inlinevoid arrInsert(constint k, int&sz, S a[], const S aval, T b[], const T bval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i]= a[i-1];
}
for(i=sz-1;i>k;i--){
b[i]= b[i-1];
}
a[k]= aval;
b[k]= bval;
}
template<class S, class T, class U>inlinevoid arrInsert(constint k, int&sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i]= a[i-1];
}
for(i=sz-1;i>k;i--){
b[i]= b[i-1];
}
for(i=sz-1;i>k;i--){
c[i]= c[i-1];
}
a[k]= aval;
b[k]= bval;
c[k]= cval;
}
template<class S, class T, class U, class V>inlinevoid arrInsert(constint k, int&sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i]= a[i-1];
}
for(i=sz-1;i>k;i--){
b[i]= b[i-1];
}
for(i=sz-1;i>k;i--){
c[i]= c[i-1];
}
for(i=sz-1;i>k;i--){
d[i]= d[i-1];
}
a[k]= aval;
b[k]= bval;
c[k]= cval;
d[k]= dval;
}
template<class T>int coordcomp_L(int n, T arr[], int res[]=NULL, void*mem = wmem){
int i;
int k =0;
pair<T,int>*r;
walloc1d(&r, n, &mem);
for(i=(0);i<(n);i++){
r[i].first= arr[i];
r[i].second= i;
}
sort(r, r+n);
if(res !=NULL){
for(i=(0);i<(n);i++){
if(i && r[i].first!= r[i-1].first){
k++;
}
res[r[i].second]= k;
}
}
else{
for(i=(0);i<(n);i++){
if(i && r[i].first!= r[i-1].first){
k++;
}
arr[r[i].second]= k;
}
}
return k+1;
}
template<class T>struct DijkstraHeap{
int*hp;
int*place;
int size;
char*visited;
T *val;
voidmalloc(int N){
hp =(int*)std::malloc(N*sizeof(int));
place =(int*)std::malloc(N*sizeof(int));
visited =(char*)std::malloc(N*sizeof(char));
val =(T*)std::malloc(N*sizeof(T));
}
voidfree(){
std::free(hp);
std::free(place);
std::free(visited);
std::free(val);
}
void walloc(int N, void**mem=&wmem){
walloc1d(&hp, N, mem);
walloc1d(&place, N, mem);
walloc1d(&visited, N, mem);
walloc1d(&val, N, mem);
}
void init(int N){
int i;
size =0;
for(i=(0);i<(N);i++){
place[i]=-1;
}
for(i=(0);i<(N);i++){
visited[i]=0;
}
}
void up(int n){
int m;
while(n){
m=(n-1)/2;
if(val[hp[m]]<=val[hp[n]]){
break;
}
swap(hp[m],hp[n]);
swap(place[hp[m]],place[hp[n]]);
n=m;
}
}
void down(int n){
int m;
for(;;){
m=2*n+1;
if(m>=size){
break;
}
if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
m++;
}
if(val[hp[m]]>=val[hp[n]]){
break;
}
swap(hp[m],hp[n]);
swap(place[hp[m]],place[hp[n]]);
n=m;
}
}
void change(int n, T v){
if(visited[n]||(place[n]>=0&&val[n]<=v)){
return;
}
val[n]=v;
if(place[n]==-1){
place[n]=size;
hp[size++]=n;
up(place[n]);
}
else{
up(place[n]);
}
}
int pop(void){
int res=hp[0];
place[res]=-1;
size--;
if(size){
hp[0]=hp[size];
place[hp[0]]=0;
down(0);
}
visited[res]=1;
return res;
}
}
;
struct graph{
int N;
int*es;
int**edge;
void setDirectEdge(int N__, int M, int A[], int B[], void**mem =&wmem){
int i;
N = N__;
walloc1d(&es, N, mem);
walloc1d(&edge, N, mem);
walloc1d(&edge[0], M, mem);
for(i=(0);i<(N);i++){
es[i]=0;
}
for(i=(0);i<(M);i++){
es[A[i]]++;
}
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], mem);
}
for(i=(0);i<(N);i++){
es[i]=0;
}
for(i=(0);i<(M);i++){
edge[A[i]][es[A[i]]++]= B[i];
}
}
void getDist(int root, int res[], void*mem = wmem){
int i;
int j;
int k;
int*q;
int s;
int z;
walloc1d(&q, N, &mem);
for(i=(0);i<(N);i++){
res[i]=-1;
}
res[root]=0;
s=0;
z=1;
q[0]=root;
while(z){
i=q[s++];
z--;
for(j=(0);j<(es[i]);j++){
k=edge[i][j];
if(res[k]>=0){
continue;
}
res[k]=res[i]+1;
q[s+z++]=k;
}
}
}
}
;
template<class T>struct wgraph{
int N;
int*es;
int**edge;
T **cost;
graph g;
void setDirectEdge(int N__, int M, int A[], int B[], T C[], void**mem =&wmem){
int i;
N = N__;
walloc1d(&es, N, mem);
for(i=(0);i<(N);i++){
es[i]=0;
}
for(i=(0);i<(M);i++){
es[A[i]]++;
}
walloc1d(&edge, N, mem);
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], mem);
}
walloc1d(&cost, N, mem);
for(i=(0);i<(N);i++){
walloc1d(&cost[i], es[i], mem);
}
for(i=(0);i<(N);i++){
es[i]=0;
}
for(i=(0);i<(M);i++){
edge[A[i]][es[A[i]]]= B[i];
cost[A[i]][es[A[i]]++]= C[i];
}
g.N= N;
g.es= es;
g.edge= edge;
}
template<class S>void getDist(int root, S res[], S unreachable =-1, void*mem = wmem){
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status