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:
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

import static java.lang.Math.min;

public class Main {

    void solve() throws Throwable {
        int n = readInt();
        long[] a = readLongArray(n);
        System.out.println("1 1");
        System.out.println(-a[0]);
        if (n == 1) {
            System.out.println("1 1");
            System.out.println("0");
            System.out.println("1 1");
            System.out.println("0");
            return;
        }
        a[0] = 0;
        System.out.println(2 + " " + n);
        for (int i = 1; i < n; i++) {
            long k = (((n - a[i]) % n) * rev(n - 1, n)) % n;
            long d = (n - 1) * k;
            System.out.print(d + " ");
            a[i] += d;
        }
        System.out.println();
        System.out.println(1 + " " + n);
        for (int i = 0; i < n; i++) {
            System.out.print(-a[i] + " ");
        }
    }

    long rev(long a, long mod) {
        return -1;
        //return binpow(a, mod - 2, mod);
    }

    //-------------------------------------------------

    final boolean ONLINE_JUDGE = !new File("input.txt").exists();

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok;

    public void run() {
        Runnable run = () -> {
            try {
                long startTime = System.currentTimeMillis();
                Locale.setDefault(Locale.US);
                if (ONLINE_JUDGE) {
                    in = new BufferedReader(new InputStreamReader(System.in));
                    out = new PrintWriter(System.out);
                } else {
                    in = new BufferedReader(new FileReader("input.txt"));
                    out = new PrintWriter("output.txt");
                }
                tok = new StringTokenizer("");
                solve();
                in.close();
                out.close();
                long endTime = System.currentTimeMillis();
                long totalMemory = Runtime.getRuntime().totalMemory();
                long freeMemory = Runtime.getRuntime().freeMemory();
                System.err.println();
                System.err.println("Time = " + (endTime - startTime) + " ms");
                //System.err.println("Memory = " + ((totalMemory - freeMemory) / 1024) + " KB");
            } catch (Throwable e) {
                e.printStackTrace(System.err);
                System.exit(-1);
            }
        };
        new Thread(null, run, "run", 256 * 1024 * 1024).start();
        min(0, 0);
    }

    String readString() {
        while (!tok.hasMoreTokens()) {
            String line;
            try {
                line = in.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            if (line == null) return null;
            tok = new StringTokenizer(line);
        }
        return tok.nextToken();
    }

    int readInt() {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    void debug(Object... o) {
        if (!ONLINE_JUDGE) {
            System.err.println(Arrays.deepToString(o));
        }
    }
 
    /*long binpow(long a, long n) {
        long r = 1;
        while (n > 0) {
            if ((n & 1) > 0) {
                r *= a;
            }
            a *= a;
            n /= 2;
        }
        return r;
    }/**/

    long binpow(long a, long n, long mod) {
        long r = 1;
        while (n > 0) {
            if ((n & 1) > 0) {
                r = (r * a) % mod;
            }
            a = (a * a) % mod;
            n /= 2;
        }
        return r;
    }/**/

    static long gcd(long x, long y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    private long[] readLongArray(int n) throws IOException {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = readLong();
        }
        return a;
    }

    private int[] readIntArray(int n) throws IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = readInt();
        }
        return a;
    }

    public static void main(String[] args) {
        new Main().run();
    }
}