using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; //using nint=System.Int32; static class Program{ const int mod=(int)1e9+7; const double eps=1e-11; static void Main(){ Sc sc=new Sc(); var s=sc.Ia; var h=new int[s[1]][]; Uf uf=new Uf(s[0]+1); for(int i = 0;i{ g[x]=k; k++; }); for(int i = 0;i=0){p+=dat[q];q=(q-1)>>1;} return p; } public void Ud2(int a,int b,long d){Hn(a,b,0,0,m-1,d);} private void Hn(int a,int b,int k,int l,int r,long d){ if(a<=l&&r<=b){dat[k]+=d;} else if(l<=b&&a<=r){ Hn(a,b,k*2+1,l,(l+r)>>1,d); Hn(a,b,k*2+2,(l+r+1)>>1,r,d); } } } public class Uf{ public class Nd{ public int n; public Nd ne; public Nd(int n){this.n=n;} } private int[] arr,hi; public Nd[] f,l; public int all; public Uf(int n){ arr=new int[n]; hi=new int[n]; f=new Nd[n]; l=new Nd[n]; all=n; for(int i=0;i fu){ var e=f[a]; for(int j = 0;j(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i