Problem: This is the hard version of the problem. The difference between the versions is in the number of possible operations that can be made. You can make hacks if and only if you solved both versions of the problem.

You are given a binary table of size n × m. This table consists of symbols 0 and 1.

You can make such operation: select 3 different cells that belong to one 2 × 2 square and change the symbols in these cells (change 0 to 1 and 1 to 0).

Your task is to make all symbols in the table equal to 0. You are allowed to make at most nm operations. You don't need to minimize the number of operations.

It can be proved, that it is always possible.

Input

The first line contains a single integer t (1 ≤ t ≤ 5000) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains two integers n, m (2 ≤ n, m ≤ 100).

Each of the next n lines contains a binary string of length m, describing the symbols of the next row of the table.

It is guaranteed, that the sum of nm for all test cases does not exceed 20000.

Output

For each test case print the integer k (0 ≤ k ≤ nm) — the number of operations.

In the each of the next k lines print 6 integers x_1, y_1, x_2, y_2, x_3, y_3 (1 ≤ x_1, x_2, x_3 ≤ n, 1 ≤ y_1, y_2, y_3 ≤ m) describing the next operation. This operation will be made with three cells (x_1, y_1), (x_2, y_2), (x_3, y_3). These three cells should be different. These three cells should belong to some 2 × 2 square.

Example

Input


5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101


Output


1
1 1 2 1 2 2
2 
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2 
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2 
1 4 1 5 2 5 
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

Note

In the first test case, it is possible to make only one operation with cells (1, 1), (2, 1), (2, 2). After that, all symbols will be equal to 0.

In the second test case:

  * operation with cells (2, 1), (3, 1), (3, 2). After it the table will be: 
    
          
    011  
    001  
    000  
    

  * operation with cells (1, 2), (1, 3), (2, 3). After it the table will be: 
    
          
    000  
    000  
    000  
    




In the fifth test case:

  * operation with cells (1, 3), (2, 2), (2, 3). After it the table will be: 
    
          
    010  
    110  
    

  * operation with cells (1, 2), (2, 1), (2, 2). After it the table will be: 
    
          
    000  
    000  
    

Solution (in JAVA):

Solution:
// Don't place your source in a package
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*; 
 

 
 
 
 
// Please name your class Main
public class Main {
	
	//static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
 
    /*static int read() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
    static String readString() throws IOException {
        in.nextToken();
        return in.sval;
	}*/
	
	
	static Scanner in = new Scanner(System.in);
	
	public static void main (String[] args) throws java.lang.Exception {
	    
		//InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
 
		int T=Int();
		
		for(int t=0;t<T;t++){
			int n=Int();
			int m=Int();
			int A[][]=new int[n][m];
			
			
			for(int i=0;i<n;i++){
				String s=Str();
				for(int j=0;j<m;j++){
					A[i][j]=s.charAt(j)-'0';
				}
			}
			
			Solution sol=new Solution();
			sol.solution(out,A);
		}
 
		out.flush();
	}
	
	
	
	public static long Long(){
		return in.nextLong();
	}
	public static int Int(){
		return in.nextInt();
	}
	public static String Str(){
		return in.next();
	}
}
 
class Solution{
	//constant variable
	final int MAX=Integer.MAX_VALUE;
	final int MIN=Integer.MIN_VALUE;
	//Set<Integer>adjecent[];
	//////////////////////////////
 
	public void fastprint(PrintWriter out,String s){
		out.print(s);
	}
	
	public void fastprintln(PrintWriter out,String s){
		out.println(s);
	}

	
	
	
	
	

	
	List<int[]>res=new ArrayList<>();
	public void solution(PrintWriter out,int A[][]){
		
		
		int n=A.length;
		int m=A[0].length;
		
		for(int i=0;i<n-1;i++){
			for(int j=0;j<m-1;j++){
				if(i==n-2&&j==m-2)break;//last square,special treat
				process(A,i,j);
			}
		}
		last(A,n-2,m-2);
		
		
		
		
		//print2(A);
		out.println(res.size());
		for(int B[]:res){
			for(int i:B){
				out.print((i+1)+" ");
			}
			out.println();
		}
	}
	
	public void last(int A[][],int i,int j){
		//print2(A);
		//msg(" ");
		
		List<int[]>ones=new ArrayList<>();
		if(A[i][j]==1)ones.add(new int[]{i,j});
		if(A[i][j+1]==1)ones.add(new int[]{i,j+1});
		if(A[i+1][j]==1)ones.add(new int[]{i+1,j});
		if(A[i+1][j+1]==1)ones.add(new int[]{i+1,j+1});
		
		if(ones.size()==0)return;
		
		if(ones.size()==1){
			int B[]=new int[6];
			int pair[]=ones.get(0);
			int index=0;
			
			for(int I=i;I<i+2;I++){
				for(int J=j;J<j+2;J++){
					if(A[I][J]==0){
						A[I][J]=1;
						B[index++]=I;
						B[index++]=J;
					}
					if(index==4)break;
				}
				if(index==4)break;
			}
			
			A[pair[0]][pair[1]]=0;
			B[4]=pair[0];
			B[5]=pair[1];
			res.add(B);
			
		}
		else if(ones.size()==2){
			int index=0;
			int B[]=new int[6];
			int pair[]=ones.get(0);
			for(int I=i;I<i+2;I++){
				for(int J=j;J<j+2;J++){
					if(A[I][J]==0){
						A[I][J]=1;
						B[index++]=I;
						B[index++]=J;
					}
					if(index==4)break;
				}
				if(index==4)break;
			}
			A[pair[0]][pair[1]]=0;
			B[4]=pair[0];
			B[5]=pair[1];
			res.add(B);
		}
		
		else if(ones.size()==3){
			int index=0;
			int B[]=new int[6];
			for(int p[]:ones){
				A[p[0]][p[1]]=0;
				B[index++]=p[0];
				B[index++]=p[1];
			}
			res.add(B);
		}
		else if(ones.size()==4){
			A[i][j]=(A[i][j]+1)%2;
			A[i+1][j]=(A[i+1][j]+1)%2;
			A[i][j+1]=(A[i][j+1]+1)%2;
			res.add(new int[]{i,j,i+1,j,i,j+1});
		}
		
		last(A,i,j);
		
		
	}
	
	public void process(int A[][],int i,int j){
		List<int[]>ones=new ArrayList<>();
		
		if(A[i][j]==1)ones.add(new int[]{i,j});
		if(A[i][j+1]==1)ones.add(new int[]{i,j+1});
		if(A[i+1][j]==1)ones.add(new int[]{i+1,j});
		if(A[i+1][j+1]==1)ones.add(new int[]{i+1,j+1});
		
		
		if(j==A[0].length-2){
			if(ones.size()==4){
				A[i][j]=0;
				A[i+1][j]=0;
				A[i][j+1]=0;
				res.add(new int[]{i,j,i+1,j,i,j+1});
			}
			else if(ones.size()==3){
				int index=0;
				int B[]=new int[6];
				for(int p[]:ones){
					A[p[0]][p[1]]=0;
					B[index++]=p[0];
					B[index++]=p[1];
				}
				res.add(B);
			}
			
			else if(ones.size()==2){
				if(A[i][j]==1&&A[i][j+1]==1){
					A[i][j]=(A[i][j]+1)%2;
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j]=(A[i+1][j]+1)%2;
					res.add(new int[]{i,j,i,j+1,i+1,j});
				}
				else if(A[i][j]==1){
					A[i][j]=(A[i][j]+1)%2;
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i,j,i+1,j,i+1,j+1});
				}
				else if(A[i][j+1]==1){
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i,j+1,i+1,j,i+1,j+1});
				}
				else{
					//can skip 
				}
				
				
			}
			else if(ones.size()==1){
				if(A[i][j]==1){
					A[i][j]=(A[i][j]+1)%2;
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i,j,i+1,j,i+1,j+1});
				}
				else if(A[i][j+1]==1){
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i,j+1,i+1,j,i+1,j+1});
				}
				
			}
			else{
				//nothing to do
			}
		}
		
		else{
			if(ones.size()==4){
				A[i][j]=0;
				A[i+1][j]=0;
				A[i][j+1]=0;
				res.add(new int[]{i,j,i+1,j,i,j+1});
			}
			else if(ones.size()==3){
				int index=0;
				int B[]=new int[6];
				for(int p[]:ones){
					A[p[0]][p[1]]=0;
					B[index++]=p[0];
					B[index++]=p[1];
				}
				res.add(B);
			}
			else if(ones.size()==2){
				if(A[i][j]==1&&A[i+1][j]==1){
					A[i][j]=(A[i][j]+1)%2;
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i][j+1]=(A[i][j+1]+1)%2;
					res.add(new int[]{i,j,i+1,j,i,j+1});
				}
				else if(A[i][j]==1){
					A[i][j]=(A[i][j]+1)%2;
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i,j,i,j+1,i+1,j+1});
				}
				else if(A[i+1][j]==1){
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i+1,j,i,j+1,i+1,j+1});
				}
				else{
					//can skip 
				}
				
				
			}
			else if(ones.size()==1){
				if(A[i][j]==1){
					A[i][j]=(A[i][j]+1)%2;
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i,j,i,j+1,i+1,j+1});
				}
				else if(A[i+1][j]==1){
					A[i+1][j]=(A[i+1][j]+1)%2;
					A[i][j+1]=(A[i][j+1]+1)%2;
					A[i+1][j+1]=(A[i+1][j+1]+1)%2;
					res.add(new int[]{i+1,j,i,j+1,i+1,j+1});
				}
				
			}
			else{
				//nothing to do
			}
			
			
		}
		
		

	}
	
	
	
	
	

	

    



	


	
	
	
	/*class LCA{
		int p1,p2;
		boolean visit[];
		int res=-1;
		boolean good=false;
		public LCA(int p1,int p2){
			this.p1=p1;this.p2=p2;
			visit=new boolean[adjecent.length];
		}
		
		public boolean dfs(int root){
			visit[root]=true;
			List<Integer>next=adjecent[root];
			boolean ans=false;
			
			if(root==p1||root==p2){
				ans=true;
			}
			int cnt=0;
			for(int c:next){
				if(visit[c])continue;
				boolean v=dfs(c);
				ans|=v;
				if(v)cnt++;
			}
			
			if(cnt==2){
				if(!good){
					good=true;
					res=root;
				}
			}
			else if(cnt==1){
				if(!good&&(root==p1||root==p2)){
					good=true;
					res=root;
				}
			}
			return ans;
		}
	}*/
	
	
	
	
	
	/*public void delete(Dnode node){
		Dnode pre=node.pre;
		Dnode next=node.next;
		pre.next=next;
		next.pre=pre;
		map.remove(node.v);
	}
	
	public void add(int v){
		Dnode node=new Dnode(v);
		Dnode pre=tail.pre;
		pre.next=node;
		node.pre=pre;
		node.next=tail;
		tail.pre=node;
		map.put(v,node);
	}
	
	class Dnode{
		Dnode next=null;
		Dnode pre=null;
		int v;
		public Dnode(int v){
			this.v=v;
		}
		
	}*/
	public String tobin(int i){
		return Integer.toBinaryString(i);
	}
 
	public void reverse(int A[]){
		List<Integer>l=new ArrayList<>();
		for(int i:A)l.add(i);
		Collections.reverse(l);
		for(int i=0;i<A.length;i++){
			A[i]=l.get(i);
		}
	}
 
	public void sort(int A[]){
		Arrays.sort(A);
	}
	
	public void swap(int A[],int l,int r){
		int t=A[l];
		A[l]=A[r];
		A[r]=t;
	}
	
 
	
	
	public long C(long fact[],int i,int j){ // C(20,3)=20!/(17!*3!)
		// take   a/b     where a=20!  b=17!*3!
		if(j>i)return 1;
		if(j<=0)return 1;
		long mod=998244353;
		long a=fact[i];
		long b=((fact[i-j]%mod)*(fact[j]%mod))%mod;
		BigInteger B= BigInteger.valueOf(b);
		long binverse=B.modInverse(BigInteger.valueOf(mod)).longValue();
		return ((a)*(binverse%mod))%mod;
	}
	
	public long gcd(long a, long b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b%a, a); 
    } 
	
	 
	
	//map operation
	public void put(Map<Integer,Integer>map,int i){
		if(!map.containsKey(i))map.put(i,0);
		map.put(i,map.get(i)+1);
	}
	
	public void delete(Map<Integer,Integer>map,int i){
		map.put(i,map.get(i)-1);
		if(map.get(i)==0)map.remove(i);
	}
 
 
 
 
 
	
 
 
	/*public void tarjan(int p,int r){
		if(cut)return;
		List<Integer>childs=adjecent[r];
		dis[r]=low[r]=time;
		time++;
		
		//core for tarjan
		int son=0;
		for(int c:childs){
			if(ban==c||c==p)continue;
			if(dis[c]==-1){
				son++;
				tarjan(r,c);
				low[r]=Math.min(low[r],low[c]);
				if((r==root&&son>1)||(low[c]>=dis[r]&&r!=root)){
					cut=true;
					return;
				}
			}else{
				if(c!=p){
					low[r]=Math.min(low[r],dis[c]);
				}
			}
		}
		
	}*/
	
	
 
	
	//helper function I would use
	public void remove(Map<Integer,Integer>map,int i){
		map.put(i,map.get(i)-1);
		if(map.get(i)==0)map.remove(i);
	}
	
	
	
	public void ascii(String s){
		for(char c:s.toCharArray()){
			System.out.print((c-'a')+"  ");
		}
		msg("");
	}
	
	public int flip(int i){
		if(i==0)return 1;
		else return 0;
	}
	
	public boolean[] primes(int n){
		boolean A[]=new boolean[n+1];
		for(int i=2;i<=n;i++){
			if(A[i]==false){
				for(int j=i+i;j<=n;j+=i){
					A[j]=true;
				}
			}
		}
		return A;
	}
	
	public void msg(String s){
		System.out.println(s);
	}
	
	public void msg1(String s){
		System.out.print(s);
	}
	
	public int[] kmpPre(String p){
		int pre[]=new int[p.length()];
		int l=0,r=1;
		while(r<p.length()){
			if(p.charAt(l)==p.charAt(r)){
				pre[r]=l+1;
				l++;r++;
			}else{
				if(l==0)r++;
				else l=pre[l-1];
			}
		}
		return pre;
	}
	
	public boolean isP(String s){
		int l=0,r=s.length()-1;
		while(l<r){
			if(s.charAt(l)!=s.charAt(r))return false;
			l++;r--;
		}
		return true;
	}
	
	public int find(int nums[],int x){//union find => find method
		if(nums[x]==x)return x;
		int root=find(nums,nums[x]);
		nums[x]=root;
		return root;
	}
	
 
	
	
	public int[] copy1(int A[]){
		int a[]=new int[A.length];
		for(int i=0;i<a.length;i++)a[i]=A[i];
		return a;
	}
	
	
	public void printd1(double A[]){
		for(double i:A)System.out.print(i+"  ");
		System.out.println();
	}
	
	public void print1(long A[]){
		for(long i:A)System.out.print(i+"  ");
		System.out.println();
	}
	public void print2(int A[][]){
		for(int i=0;i<A.length;i++){
			for(int j=0;j<A[0].length;j++){
				System.out.print(A[i][j]+"   ");
			}System.out.println();
		}
	}
	
	public int min(int a,int b){
		return Math.min(a,b);
	}
	
	
	public int[][] matrixdp(int[][] grid) {
        if(grid.length==0)return new int[][]{};
        int res[][]=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                res[i][j]=grid[i][j]+get(res,i-1,j)+get(res,i,j-1)-get(res,i-1,j-1);
            }
        }
        return res;
    }
    
    public int get(int grid[][],int i,int j){
        if(i<0||j<0||i>=grid.length||j>=grid[0].length)return 0;
        return grid[i][j];
    }
	
	public int[] suffixArray(String s){
		int n=s.length();
		Suffix A[]=new Suffix[n];
		
		for(int i=0;i<n;i++){
			A[i]=new Suffix(i,s.charAt(i)-'a',0);
		}
		
		for(int i=0;i<n;i++){
			if(i==n-1){
				A[i].next=-1;
			}else{
				A[i].next=A[i+1].rank;
			}
		}
		Arrays.sort(A);
		
		for(int len=4;len<A.length*2;len<<=1){
			int in[]=new int[A.length];
			int rank=0;
			int pre=A[0].rank;
			A[0].rank=rank;
			in[A[0].index]=0;
			for(int i=1;i<A.length;i++){//rank for the first two letter
				if(A[i].rank==pre&&A[i].next==A[i-1].next){
					pre=A[i].rank;
					A[i].rank=rank;
				}else{
					pre=A[i].rank;
					A[i].rank=++rank;
				}
				in[A[i].index]=i;
			}
			
			for(int i=0;i<A.length;i++){
				int next=A[i].index+len/2;
				if(next>=A.length){
					A[i].next=-1;
				}else{
					A[i].next=A[in[next]].rank;
				}
			}
			
			
			Arrays.sort(A);
		}
		
		
		int su[]=new int[A.length];
		for(int i=0;i<su.length;i++){
			su[i]=A[i].index;
		}
		return su;
	}
	
}
 
//suffix array Struct
class Suffix implements Comparable<Suffix>{
	int index;
	int rank;
	int next;
	public Suffix(int i,int rank,int next){
		this.index=i;
		this.rank=rank;
		this.next=next;
	}
	
	@Override
	public int compareTo(Suffix other) {
		if(this.rank==other.rank){
			return this.next-other.next;
		}
		return this.rank-other.rank;
	}
	
	public String toString(){
		return this.index+"   "+this.rank+"   "+this.next+"  ";
	}
}
 
 
 
class Wrapper implements Comparable<Wrapper>{
	int spf;int cnt;
	public Wrapper(int spf,int cnt){
		this.spf=spf;
		this.cnt=cnt;
	}
		
	@Override
	public int compareTo(Wrapper other) {
		return this.spf-other.spf;
	}
}
 
 
 
    class Node{//what the range would be for that particular node
		boolean state=false;
        int l=0,r=0;
		int ll=0,rr=0;
        public Node(boolean state){
            this.state=state;
        }
    }
	
	
	
	
	class Seg1{
			int A[];
			public Seg1(int A[]){
				this.A=A;
			}
			
			public void update(int left,int right,int val,int s,int e,int id){
				if(left<0||right<0||left>right)return;
				if(left==s&&right==e){
					
					A[id]+=val;
					return;
				}
				int mid=s+(e-s)/2; //[s,mid] [mid+1,e]
				
				if(left>=mid+1){
					update(left,right,val,mid+1,e,id*2+2);
				}else if(right<=mid){
					update(left,right,val,s,mid,id*2+1);
				}else{
					update(left,mid,val,s,mid,id*2+1);
					update(mid+1,right,val,mid+1,e,id*2+2);
				}
			}
			
			public int query(int i,int add,int s,int e,int id){
				
				if(s==e&&i==s){
					return A[id]+add;
				}
				
				int mid=s+(e-s)/2; //[s,mid] [mid+1,e]
				
				if(i>=mid+1){
					return query(i,A[id]+add,mid+1,e,id*2+2);
				}else{
					return query(i,A[id]+add,s,mid,id*2+1);
				}
			}
	}
 
 
	 class MaxFlow{
		
 
		  public static List<Edge>[] createGraph(int nodes) {
			List<Edge>[] graph = new List[nodes];
			for (int i = 0; i < nodes; i++)
			  graph[i] = new ArrayList<>();
			return graph;
		  }
 
		  public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
			graph[s].add(new Edge(t, graph[t].size(), cap));
			graph[t].add(new Edge(s, graph[s].size() - 1, 0));
		  }
 
		  static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
			Arrays.fill(dist, -1);
			dist[src] = 0;
			int[] Q = new int[graph.length];
			int sizeQ = 0;
			Q[sizeQ++] = src;
			for (int i = 0; i < sizeQ; i++) {
			  int u = Q[i];
			  for (Edge e : graph[u]) {
				if (dist[e.t] < 0 && e.f < e.cap) {
				  dist[e.t] = dist[u] + 1;
				  Q[sizeQ++] = e.t;
				}
			  }
			}
			return dist[dest] >= 0;
		  }
 
		  static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
			if (u == dest)
			  return f;
			for (; ptr[u] < graph[u].size(); ++ptr[u]) {
			  Edge e = graph[u].get(ptr[u]);
			  if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
				int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
				if (df > 0) {
				  e.f += df;
				  graph[e.t].get(e.rev).f -= df;
				  return df;
				}
			  }
			}
			return 0;
		  }
 
		  public static int maxFlow(List<Edge>[] graph, int src, int dest) {
			int flow = 0;
			int[] dist = new int[graph.length];
			while (dinicBfs(graph, src, dest, dist)) {
			  int[] ptr = new int[graph.length];
			  while (true) {
				int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
				if (df == 0)
				  break;
				flow += df;
			  }
			}
			return flow;
		  }
		 
	 }
	 
	 	 class Edge {
			int t, rev, cap, f;
 
			public Edge(int t, int rev, int cap) {
			  this.t = t;
			  this.rev = rev;
			  this.cap = cap;
			}
		  }
		  
	  /*class Seg{
        int l,r;
        int min=Integer.MAX_VALUE;
        Seg left=null,right=null;
		int tree[];
        public Seg(int l,int r){
            this.l=l;
            this.r=r;
            if(l!=r){
                int mid=l+(r-l)/2;
                if(l<=mid)left=new Seg(l,mid);
                if(r>=mid+1)right=new Seg(mid+1,r);
                if(left!=null)min=Math.min(left.min,min);
                if(right!=null)min=Math.min(right.min,min);
            }else{
                min=tree[l];
            }
        }
        public int query(int s,int e){
            if(l==s&&r==e){
                return min;
            }
            int mid=l+(r-l)/2; //left :  to mid-1,
            if(e<=mid){
                return left.query(s,e);
            }
            else if(s>=mid+1){
                return right.query(s,e);
            }else{
                return Math.min(left.query(s,mid),right.query(mid+1,e));
            }
        }

        public void update(int index){
            if(l==r){
                min=tree[l];
                return;
            }
            int mid=l+(r-l)/2;
            if(index<=mid){
                left.update(index);
            }else{
                right.update(index);
            }
            this.min=Math.min(left.min,right.min);
        }
    }*/
	
	class Fenwick {
        int tree[];//1-index based
        int A[];
        int arr[];
        public Fenwick(int[] A) {
            this.A=A;
            arr=new int[A.length];
            tree=new int[A.length+1];
            int sum=0;
            for(int i=0;i<A.length;i++){
                update(i,A[i]);
            }
        }

        public void update(int i, int val) {
            arr[i]+=val;
			
			
            i++;
            while(i<tree.length){
                tree[i]+=val;
                i+=(i&-i);
            }
            
        }

        public int sumRange(int i, int j) {
			if(i>j)return 0;
            return pre(j+1)-pre(i);
        }

        public int pre(int i){
            int sum=0;
            while(i>0){
                sum+=tree[i];
                i-=(i&-i);
            }
            return sum;
        }
    }