Problem: You are given an array a of n integers.

You want to make all elements of a equal to zero by doing the following operation exactly three times:

  * Select a segment, for each number in this segment we can add a multiple of len to it, where len is the length of this segment (added integers can be different). 



It can be proven that it is always possible to make all elements of a equal to zero.

Input

The first line contains one integer n (1 ≤ n ≤ 100 000): the number of elements of the array.

The second line contains n elements of an array a separated by spaces: a_1, a_2, ..., a_n (-10^9 ≤ a_i ≤ 10^9).

Output

The output should contain six lines representing three operations.

For each operation, print two lines:

  * The first line contains two integers l, r (1 ≤ l ≤ r ≤ n): the bounds of the selected segment.

  * The second line contains r-l+1 integers b_l, b_{l+1}, ..., b_r (-10^{18} ≤ b_i ≤ 10^{18}): the numbers to add to a_l, a_{l+1}, …, a_r, respectively; b_i should be divisible by r - l + 1.

Example

Input


4
1 3 2 4


Output


1 1 
-1
3 4
4 2
2 4
-3 -6 -6

Solution (in JAVA):

Solution:
// Author : AMIT KUMAR BARMAN (gearman_0712)
import java.io.*;
import java.util.*;

public class MultipleLength{
    static final long modp =1000000007;
    static long x_ec=1,y_ec=0,d_ec =1;
    static long maxi=0;
    static boolean v1 =false ,v2 = false;
    static InputReader in = new InputReader(System.in);
    static OutputStream outputStream = System.out;
    static OutputWriter out = new OutputWriter(outputStream);

    
   
   
    public static void main (String args[]) throws IOException {
        int n= in.readInt();
        int arr[]= new int[n+1];
        for(int i=1;i<=n ;i++)
        { arr[i] = in.readInt();

        }
   if(n==1)
   {  out.println("1 1");
        out.println(0);
        out.println("1 1");
        out.println(0);
        out.println("1 1");
        out.println(-arr[1]);

   }
   else
   {out.println(1 +" "+n);
    for(int i= 1;i<=n ;i++)
    { out.print((-(long)arr[i] * n)+" ");
    }
    out.println("");
    out.println(1 +" "+(n-1));
    for(int i= 1;i<n ;i++)
    { out.print(((long)arr[i] * (n-1))+" ");
    }
    out.println("");
    out.println(n +" "+n);
    out.println(((long)arr[n] * (n-1)));
   }

    out.close();
}
    /*
    static Node lca(Node root,int x,int y)
    {if(root==null)
        return null;
        if(root.value>x &&root.value>y )
        return lca(root.left, x, y);
         if(root.value<x &&root.value<y )
        return lca(root.right, x, y);
    
        return root;
    }
    
    
    
    
    static Node common(Node root,int x,int y)
    {  if(root==null)
        return null;
        Node temp=null;
        if(root.value ==x)
        { v1= true;
            temp =new Node(x);
    
        }
        else if(root.value ==y)
        { v2= true;
            temp =new Node(y);
    
        }
      Node  lef =common(root.left, x, y);
     Node rig =common(root.right, x, y);
       if(temp!=null)
       return temp;
       if(lef ==null)
       return rig;
       if(rig==null)
       return lef;
       return root;
    }
    
    // static class Node {
    //     int value;
    //     Node left;
    //     Node right;
        
    //     Node(int value){
    //         this.value =value;
    //         right =null;
    //         left =null;
    //     }
    // }
    static Node insert(Node root,int v)
      { if(root==null)
        return new Node(v);
          if( v<=root.value)
          root.left =insert(root.left, v);
          else
          root.right =insert(root.right,v);
    
          return root;
    
        }
      
      static int minvalue(Node root)
        {
            while(root.left!=null)
              root =root.left;
              return root.value;
    
            
    
        }
 static int[] computeLPSArray(String patt)
  {   int m=  patt.length();
      int Lps[]= new int[m];
      int i=1 ,len=0;
      Lps[0]=0;
      while( i<m)
      { if(patt.charAt(i)==patt.charAt(len))
        { len++;
            Lps[i]=len;
           i++;
        }
        else 
        {  if(len!=0)
            {len =Lps[len-1];

            }
            else //len=0
             Lps[i++]=len;


        }



      }

    return Lps;

  }
        static Node delete(Node root ,int val)
     { if(root ==null)
        return root;
        if(val<root.value)
        root.left=delete(root.left, val);
       else if(val>root.value)
       root.right =delete(root.right,val);
       else {
       if(root.left==null)
         return root.right;
         else if(root.right==null)
         return root.left;
         root.value= minvalue(root.right);
         root.right =delete(root.right, root.value);
       
    
       }
       return root;
    
    
     }
     */
    /*
     static void inorder(Node root,OutputWriter out)
     { if(root!=null)
       {inorder(root.left ,out);
          out.print(root.value+" ");
          inorder(root.right, out);
    
       }
     }
     static void preorder(Node root ,OutputWriter out)
     { if(root!=null)
       { out.println(root.value+" ");
          preorder(root.left, out);
          preorder(root.right,out);
    
       }
    
     }
     static void postorder(Node root,OutputWriter out)
     { if(root!=null)
       { postorder(root.left, out);
           postorder(root.right ,out);
           out.print(root.value+" ");
       }
    
     }
     */
    // Input: Indices Range [0..size]
    // Invariant: A[l] <= key and A[r] > key 
    static long modExponential(long x,long n)
        {long result =1l;
            while(n>0l)
            { if(n%2==1)
                result =(x*result)%modp;
                x= (x*x)%modp;
             n=n/2;
            }
            return result;
        }
      /*
    static int GetRightPosition(int A[], int l, int r, int key) 
    { 
        int m; 
    
        while( r - l > 1 ) 
        { 
            m = l + (r - l)/2; 
    
            if( A[m] <= key ) 
                l = m; 
            else
                r = m; 
        } 
    
        return l; 
    } 
    
    // Input: Indices Range -1 to size-1
    // Invariant: A[r] >= key and A[l] > key 
    static int GetLeftPosition(int A[], int l, int r, int key) 
    { 
        int m; 
    
        while( r - l > 1 ) 
        { 
            m = l + (r - l)/2; 
    
            if( A[m] >= key ) 
                r = m; 
            else
                l = m; 
        } 
    
        return r; 
    } 
    
    */
    
    public static long gcd(long a,long b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static int gcd(int a,int b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    public static int abs(int a,int b)
    {
        return (int)Math.abs(a-b);
    }
    public static long abs(long a,long b)
    {
        return (long)Math.abs(a-b);
    }
    public static int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    public static int min(int a,int b)
    {
        if(a>b)
            return b;
        else 
            return a;
    }
    public static long max(long a,long b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
    public static long min(long a,long b)
    {
        if(a>b)
            return b;
        else 
            return a;
    }
     
    /*
    void countsort(int arr[],int n,int place)
    {
            int i,freq[range]={0};         //range for integers is 10 as digits range from 0-9
            int output[n];
            for(i=0;i<n;i++)
                    freq[(arr[i]/place)%range]++;
            for(i=1;i<range;i++)
                    freq[i]+=freq[i-1];
            for(i=n-1;i>=0;i--)
            {
                    output[freq[(arr[i]/place)%range]-1]=arr[i];
                    freq[(arr[i]/place)%range]--;
            }
            for(i=0;i<n;i++)
                    arr[i]=output[i];
    }
    void radixsort(ll arr[],int n,int maxx)            //maxx is the maximum element in the array
    {
            int mul=1;
            while(maxx)
            {
                    countsort(arr,n,mul);
                    mul*=10;
                    maxx/=10;
            }
    }*/
    
    /* BufferedReader bf =new BufferedReader (new InputStreamReader(System.in));
            int t= Integer.parseInt(bf.readLine());
            StringBuffer gh =new StringBuffer("");
            StringTokenizer  tk=new StringTokenizer(bf.readLine());
            long a= Long.parseLong(tk.nextToken());
    */
    
    
    static class Pair implements Comparable<Pair>
    {
        int a,b;
        Pair (int a,int b)
        {
            this.a=a;
            this.b=b;
        }
     
        public int compareTo(Pair o) {
            
            if(this.a!=o.a)
            return -Integer.compare(this.a,o.a);
            else
                return Integer.compare(this.b, o.b);
            //return 0;
        }
        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.a == a && p.b == b;
            }
            return false;
        }
    
    
        public int hashCode(Object o) {
            Pair p = (Pair)o;
            return p.a* 31 +p.b;
        }
    
    } 
    
    static class Pair1 implements Comparable<Pair1>
    {
       char a;
       int b;
        Pair1 (char a,int b)
        {
            this.a=a;
            this.b=b;
        }
     
        public int compareTo(Pair1 o) {
            
            if(this.a!=o.a)
            return Integer.compare(this.a,o.a);
            else
                return Integer.compare(this.b, o.b);
            //return 0;
        }
        public boolean equals(Object o) {
            if (o instanceof Pair1) {
                Pair1 p = (Pair1)o;
                return p.a == a && p.b == b;
            }
            return false;
        }
    
    
        public int hashCode(Object o) {
            Pair1 p = (Pair1)o;
            return (int)p.a* 31 +(int)p.b;
        }
    
    } 
    /*
    //public void solve(int testNumber, InputReader in, OutputWriter out) 
    
    // in case u want to print And take input inside and static method
    static void extendedEuclid( long A,  long B) {
        if(B==0)
        {d_ec=A;
          x_ec =1;
          y_ec=0;
      
        }
        else{
            extendedEuclid(B, A%B);
             long temp =x_ec;
            x_ec = y_ec;
            y_ec =temp -(A/B)*y_ec;
        }
          
      }
      static long modInverse( long A,  long M) //A and M are coprime i.e. Ax+My=1. In the extended Euclidean algorithm, x is the modular multiplicative inverse of A under modulo M.
      {
          extendedEuclid(A,M);
          return (x_ec%M+M)%M;    //x may be negative
      }
      
      static boolean checkprime(int N) {
          int count = 0;
          for( int i = 1;i * i <=N;++i ) {
               if( N % i == 0) {
                   if( i * i == N )
                           count++;
                   else       // i < sqrt(N) and (N / i) > sqrt(N)
                           count += 2;
                }
          }
          if(count == 2)
               return true;
          else
            return false;
      }
      static void factorize (long a,HashMap<Long,Long> map)
        {
          long i=2;
          for( i=2;i*i<=a;i++)
          {
            if(a%i==0){
                long f=0;  
            while((a>0)&&(a%i==0))
            { 
                a= a/i;
                f++;
            }
            map.put(i, f);
          
            }
          }
          if(a>1l)
            map.put(a, 1l);
    
        }*/
    
    /*static class DSU
    {
    int parent[];
    int rank[];
    int state[];
    DSU(int n)
    {parent=new int[n];
    rank=new int[n];
    state=new int[n+1];
        
    }
    void makeset(int n)
    {
    for(int i=0;i<n;i++)
    {
    parent[i]=i;
    rank[i]=1;
    state[i]=0;// for jamboard question
    }
    }
    void decP(int x)// for jamboard question
    {
    if(state[x]>0)
    state[x]--;
    }
    void incP(int x)// for jamboard question
    {
    state[x]++;
    }
    boolean getP(int x)// for jamboard question
    {
    return (state[x]!=0);
    }
    int find(int x)
    {
    if(x==parent[x])
    return x;
    parent[x]=find(parent[x]);
    return parent[x];
    }
    void union(int x,int y)
    {
    int xRoot=find(x);
    int yRoot=find(y);
    if(xRoot==yRoot)
    return;
    if(rank[xRoot]>rank[yRoot])
    {
    parent[yRoot]=xRoot;
    state[xRoot]+=state[yRoot];// for jamboard question
    }
    else if(rank[xRoot]<rank[yRoot])
    {
    parent[xRoot]=yRoot;
    state[yRoot]+=state[xRoot];// for jamboard question
    }
    else
    {
    parent[xRoot]=yRoot;
    rank[yRoot]++;
    state[yRoot]+=state[xRoot];// for jamboard question
    }
    }
    }
    */    

}/*
class DSU
{
int parent[];
int rank[];
int diff[];
DSU(int sd){
parent=new int[sd];
rank=new int[sd];
diff=new int[sd];
}
void makeset(int n)
{

for(int i=0;i<n;i++)
{
parent[i]=i;
rank[i]=1;
diff[i]=0;
}
}

int find (int x) {
    if (x == parent [x]) return x;
    int t = parent [x];
    parent [x] = find (parent [x]);
    diff [x] ^= diff [t];
    return parent [x];
}
boolean union(int x,int y,int w)
{
int xRoot=find(x); 
int yRoot=find(y);
if(xRoot==yRoot)
{ if(w != (diff[x]^diff[y]))
         return false;
}

else if(rank[xRoot]>rank[yRoot])
{
parent[yRoot]=xRoot;
diff[yRoot]= diff[x]^diff[y]^w;
}
else if(rank[xRoot]<rank[yRoot])
{
parent[xRoot]=yRoot;
diff[xRoot]= diff[x]^diff[y]^w;

}
else
{
parent[xRoot]=yRoot;
rank[yRoot]++;
diff[xRoot]= diff[x]^diff[y]^w;
}
return true;
}
}*/
class Gnode{
    int value;
    List<Gnode> neighbours;
    Gnode(int x)
   {value=x;
    neighbours =new ArrayList<>();
   }
   
   }
 class Node{
       int value;
       Node left;
       Node right;
       Node(int qw){
           this.value = qw;
           this.left = null;
           this.right = null;
       }
   }
   
   class SegTree{
       long[] seg;
       int[] map;
       long[] arr;
       SegTree(int n,long[] a){
           seg=new long[4*n];
           arr=a;
           map=new int[n+1];
       }
       void build(int low,int high, int pos) {
           if(low==high) {
               map[low]=pos;
               seg[pos]=arr[low];
           }
           else {
               int middle=(low+high)/2;
               build(low,middle,2*pos+1);
               build(middle+1,high,2*pos+2);
               seg[pos]=Math.max(seg[2*pos+1], seg[2*pos+2]);
           }
       }
       void update(int low,int high, int pos,int elpos, long value) {
           if(low==high) {
               seg[pos]=value;
           }
           else {
               int middle=(low+high)/2;
               if(elpos<=middle) {
                   update(low,middle,2*pos+1,elpos,value);
               }
               else update(middle+1,high,2*pos+2,elpos,value);
               seg[pos]=Math.max(seg[2*pos+1], seg[2*pos+2]);
           }
       }
   }

class MinHeap {
   int size;
   int maxsize;
   int heap[];
   MinHeap(int maxsize,int size)           //size = capacity
   {this.size=size;
    this.maxsize= maxsize;
    heap = new int[maxsize];

   }
   boolean isEmpty()
   {return size==0;
}
   int peek()
   {if(isEmpty())
     return -99999;
     return heap[0];

   }
   int remove()
   {if(isEmpty())
    return -99999;
    int minItem = heap[1];
    heap[1]= heap[size];
    size --;
    heapifyDown(1);
    return minItem;
   }
    void print()
    {
      System.out.println(Arrays.toString(heap)); 
    }
   boolean add( int item)
   {  if(size>= maxsize)
          return false;
          heap[size+1]= item;
          size++;
          heapifyUp(size);
          return true;

   }
    void heapifyDown( int i)
    { int left = 2*i;
        int right = 2*i +1;
        int smallest =i;
        if(left<= size  && heap[left]<heap[smallest])
          smallest =left;
          if(right<= size  && heap[right]<heap[smallest])
          smallest =right;
          if(smallest!=i)
          {  int temp =heap[i];
             heap[i]= heap[smallest];
             heap[smallest]=temp;
             heapifyDown(smallest);

          }

    }
    void heapifyUp( int i)
    {
        int parent = i/2;
        if( parent>0 && heap[parent]>heap[i])
        { int temp =heap[parent];
            heap[parent]= heap[i];
            heap[i]=temp;
            heapifyUp(parent);

        }
    }}
    class MaxHeap {
        int size;
        int maxsize;
        int heap[];
        MaxHeap(int maxsize,int size)           //size = capacity
        {this.size=size;
         this.maxsize= maxsize;
         heap = new int[maxsize];
     
        }
        void buildHeap(int arr[])
        {size = arr.length+1;
         for(int i=0;i<arr.length;i++)
        heap[i+1]= arr[i];
        for( int i=size/2;i>=1;i--)
        {heapifyDown(i);
            
        }

         
        }
        boolean isEmpty()
        {return size==0;
     }
        int peek()
        {if(isEmpty())
          return -99999;
          return heap[0];
     
        }
        int remove()
        {if(isEmpty())
         return -99999;
         int minItem = heap[1];
         heap[1]= heap[size];
         size --;
         heapifyDown(1);
         return minItem;
        }
         void print()
         {
           System.out.println(Arrays.toString(heap)); 
         }
        boolean add( int item)
        {  if(size>= maxsize)
               return false;
               heap[size+1]= item;
               size++;
               heapifyUp(size);
               return true;
     
        }
         void heapifyDown( int i)
         { int left = 2*i;
             int right = 2*i +1;
             int largest =i;
             if(left<= size  && heap[left]>heap[largest])
               largest =left;
               if(right<= size  && heap[right]>heap[largest])
               largest =right;
               if(largest!=i)
               {  int temp =heap[i];
                  heap[i]= heap[largest];
                  heap[largest]=temp;
                  heapifyDown(largest);
     
               }
     
         }
         void heapifyUp( int i)
         {
             int parent = i/2;
             if( parent>0 && heap[parent]<heap[i])
             { int temp =heap[parent];
                 heap[parent]= heap[i];
                 heap[i]=temp;
                 heapifyUp(parent);
     
             }
         }







}
 class InputReader
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream)
    {
        this.stream = stream;
    }
 
    public int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read(buf);
            } catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int readInt ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public String readString ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    public String readLine() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
    
 
    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    public boolean isSpaceChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    public String next()
    {
        return readString();
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
}
class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void println(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}