You are given an array a of n integers, and another integer k such that 2k ≤ n.

You have to perform exactly k operations with this array. In one operation, you have to choose two elements of the array (let them be a_i and a_j; they can be equal or different, but their positions in the array must not be the same), remove them from the array, and add ⌊ (a_i)/(a_j) ⌋ to your score, where ⌊ x/y ⌋ is the maximum integer not exceeding x/y.

Initially, your score is 0. After you perform exactly k operations, you add all the remaining elements of the array to the score.

Calculate the minimum possible score you can get.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 500) — the number of test cases.

Each test case consists of two lines. The first line contains two integers n and k (1 ≤ n ≤ 100; 0 ≤ k ≤ ⌊ n/2 ⌋).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5).

Output

Print one integer — the minimum possible score you can get.

Example

Input


5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
9 2
1 10 10 1 10 2 7 10 3


Output


2
16
0
6
16

Note

Let's consider the example test.

In the first test case, one way to obtain a score of 2 is the following one:

  1. choose a_7 = 1 and a_4 = 2 for the operation; the score becomes 0 + ⌊ 1/2 ⌋ = 0, the array becomes [1, 1, 1, 1, 3]; 
  2. choose a_1 = 1 and a_5 = 3 for the operation; the score becomes 0 + ⌊ 1/3 ⌋ = 0, the array becomes [1, 1, 1]; 
  3. choose a_1 = 1 and a_2 = 1 for the operation; the score becomes 0 + ⌊ 1/1 ⌋ = 1, the array becomes [1]; 
  4. add the remaining element 1 to the score, so the resulting score is 2. 



In the second test case, no matter which operations you choose, the resulting score is 16.

In the third test case, one way to obtain a score of 0 is the following one:

  1. choose a_1 = 1 and a_2 = 3 for the operation; the score becomes 0 + ⌊ 1/3 ⌋ = 0, the array becomes [3, 7]; 
  2. choose a_1 = 3 and a_2 = 7 for the operation; the score becomes 0 + ⌊ 3/7 ⌋ = 0, the array becomes empty; 
  3. the array is empty, so the score doesn't change anymore. 



In the fourth test case, no operations can be performed, so the score is the sum of the elements of the array: 4 + 2 = 6.
1
6 3
4 4 5 5 6 6
 1
6 3
1 1 1 1 2 2
 1
9 3
1 1 1 2 2 2 3 3 3
 1
10 5
3 3 3 4 4 4 5 5 5 1
 1
10 4
1 1 1 2 3 3 3 3 4 5
 1
77 9
9 8 10 5 8 20 17 19 14 16 7 6 15 16 6 13 10 13 14 12 5 6 12 14 12 8 13 12 17 8 12 17 2 11 8 18 17 2 13 2 1 19 9 8 10 20 8 12 15 1 3 15 6 19 4 11 12 8 3 2 1 20 15 14 6 10 11 1 5 11 10 6 20 6 14 16 6
 1
14 7
1 1 1 1 1 1 1 2 2 2 2 2 3 3
 1
88 38
9 143 135 72 74 12 120 27 108 183 18 24 163 122 140 155 166 188 197 14 134 66 188 161 79 100 40 55 161 118 121 18 72 141 136 31 39 187 2 98 16 118 120 196 127 66 135 186 49 16 17 50 107 192 50 23 62 110 83 124 197 127 185 129 131 182 45 147 174 115 89 109 177 7 70 43 75 5 157 93 59 26 176 105 32 89 65 6
 5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
2 0
4 2
10 5
3 3 3 4 4 4 5 5 5 1
 1
87 12
10 5 11 7 16 16 8 11 14 11 4 4 3 7 16 12 2 3 3 13 1 7 11 16 4 7 11 5 3 15 20 5 12 1 8 8 13 19 3 7 14 3 4 10 18 13 20 1 4 8 10 12 4 7 15 2 18 13 6 2 1 2 10 13 4 5 18 7 1 10 6 2 19 17 5 11 10 12 14 6 16 20 11 12 10 3 6
 1
16 8
1 1 2 2 3 3 3 3 3 3 3 3 3 4 5 5
 1
8 4
1 1 3 3 3 3 5 6
 1
12 6
1 1 1 8 8 8 8 8 8 10 10 10
 5
7 3
1 1 1 2 1 3 1
5 1
5 5 5 5 5
4 2
1 3 3 7
6 3
2 2 3 3 4 4
9 2
1 10 10 1 10 2 7 10 3
 1
12 6
1 1 1 1 1 2 2 2 2 3 3 3
 1
100 34
2 6 5 4 4 4 5 7 6 6 1 2 5 1 4 4 4 5 5 5 2 3 5 6 6 1 1 3 7 5 4 4 1 3 4 6 4 2 7 6 5 4 6 1 1 2 4 6 4 2 2 6 6 3 5 3 4 5 3 4 3 2 1 7 7 5 4 6 3 1 6 7 6 2 2 2 4 7 3 2 6 1 1 3 1 5 6 4 4 7 2 6 6 5 4 4 3 5 2 4
 1
85 3
43 17 34 67 14 7 80 48 36 95 48 68 86 4 17 46 51 87 41 90 100 56 57 42 9 8 27 23 16 14 99 22 13 98 89 24 77 59 15 94 25 81 4 71 24 43 97 88 97 10 6 8 3 86 28 61 100 98 76 85 32 18 79 66 51 44 28 99 87 56 80 93 89 76 7 57 96 39 46 25 4 67 6 51 39
 1
6 3
1 1 2 2 3 3
 1
6 3
2 3 3 3 4 4
 1
6 3
1 7 7 7 10 10
 1
10 3
1 7 4 3 2 2 6 7 4 7
 1
100 17
5 1 1 7 3 2 5 1 1 3 4 5 5 5 7 5 7 5 1 7 6 6 1 3 6 3 4 5 4 6 3 1 7 6 2 3 2 5 3 3 6 5 5 6 5 7 5 3 5 4 7 3 5 1 7 3 4 4 3 3 3 5 1 1 1 7 1 3 2 3 2 7 2 1 6 5 6 6 1 5 4 6 1 7 6 7 6 1 1 1 5 3 5 7 4 6 4 6 3 2
 1
7 3
1 1 1 2 2 3 3
 1
9 2
1 10 10 1 10 2 7 10 191919
 1
6 3
6 6 5 5 1 1
 1
8 3
1 1 6 6 6 6 2 2
 1
91 9
4 3 19 8 3 6 16 5 17 11 9 13 15 8 1 3 20 2 19 7 14 1 6 4 8 18 13 8 16 11 3 12 3 3 12 17 15 9 5 15 12 11 7 20 19 3 4 14 10 9 7 16 12 10 3 6 15 17 4 8 15 2 10 13 11 15 7 20 1 10 9 2 10 15 7 1 6 16 2 1 17 10 19 10 7 18 3 5 10 12 15
 1
67 22
83 41 94 76 47 33 20 51 98 48 92 72 24 51 15 17 35 70 83 95 79 65 80 17 72 7 97 14 74 98 55 63 45 79 42 92 85 24 84 30 29 77 64 68 68 71 89 18 82 68 20 91 84 52 45 23 65 95 83 84 18 81 63 11 89 41 69
 1
4 2
5 6 5 5
 1
6 3
3 3 4 4 7 7
 10
7 3
2 2 2 2 3 3 3
7 3
2 2 3 3 3 4 4
7 3
2 2 2 2 2 2 2
7 3
2 2 3 3 3 4 4
7 3
2 2 2 3 3 3 3
7 3
2 2 3 3 3 3 4
7 3
2 2 2 2 2 3 3
7 3
2 2 3 3 3 3 3
7 3
2 2 2 2 2 2 3
7 3
2 2 2 3 3 3 4
 1
7 3
2 2 2 2 7 8 2
 1
13 6
1 2 2 2 2 3 3 3 3 4 4 4 4
 1
10 3
1 1 1 1 1 1 2 2 3 3
 1
10 3
2 15 14 13 12 15 18 2 9 15
 1
8 4
1 2 2 2 2 3 3 3

0
 1
 3
 0
 2
 489
 0
 140
 2
16
0
6
0
 401
 1
 0
 0
 2
16
0
0
16
 0
 58
 3753
 0
 0
 0
 8
 192
 1
 22
 0
 3
 569
 616
 1
 0
 2
2
5
2
3
3
3
4
4
2
 3
 1
 4
 25
 0

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    static long MOD = 998244353l;
    int re = 0;
    int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        // FileInputStream fis = new FileInputStream(new
        // File("/Users/goudezhao/Public/JavaTest/1.txt"));
        var sc = new FastScanner();
        // var sc = new FastScanner(fis);
        // var pw = new FastPrintStream("/Users/goudezhao/Public/JavaTest/1.out");
        var pw = new FastPrintStream();
        solve(sc, pw);
        sc.close();
        pw.flush();
        pw.close();
    }

    public static void solve(FastScanner sc, FastPrintStream pw) {
        int t = sc.nextInt();
        for (int times = 0; times < t; times++) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int a[] = new int[n];
            Arrays.setAll(a, i->sc.nextInt());
            Arrays.sort(a);
            int count[] = new int[1000000];
            long re =0;
            for (int i=0;i<n-2*k;i++) {
                re+= a[i];
            }
            int maxcount =0;
            for (int i=0;i<k*2;i++) {
                count[a[n-1-i]]++;
                maxcount= Math.max(count[a[n-1-i]], maxcount);
            }
            if (maxcount>k) {
                re+= maxcount-k;
            }
            pw.println(re);
        }
    }

    public static long anothertoTen(long ano, int another) {
        long ten = 0;
        long now = 1;
        long temp = ano;
        while (temp > 0) {
            long i = temp % 10;
            ten += now * i;
            now *= another;
            temp /= 10;
        }
        return ten;
    }

    public static long tentoAnother(long ten, int another) {
        Stack<Long> stack = new Stack<Long>();
        while (ten > 0) {
            stack.add(ten % another);
            ten /= another;
        }
        long re = 0;
        while (!stack.isEmpty()) {
            long pop = stack.pop();
            re = re * 10 + pop;
        }
        return re;
    }

    // 2C5 = 5*4/(2*1)
    public static long XCY(long x, long y) {
        long temp = 1;
        for (int i = 0; i < x; i++) {
            temp = (temp * (y - i)) % MOD;
        }
        long tempx = 1;
        for (int i = 2; i <= x; i++) {
            tempx = (tempx * i) % MOD;
        }
        tempx = modpow(tempx, (long) MOD - 2);
        temp = (temp * tempx) % MOD;
        return temp;
    }

    static long modpow(long N, Long K) {
        return BigInteger.valueOf(N).modPow(BigInteger.valueOf(K), BigInteger.valueOf(MOD)).longValue();
    }

    static long modpow(long N, Long K, long mod) {
        return BigInteger.valueOf(N).modPow(BigInteger.valueOf(K), BigInteger.valueOf(mod)).longValue();
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        if (a < b) {
            return gcd(b, a);
        }
        return gcd(b, a % b);
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        if (a < b) {
            return gcd(b, a);
        }
        return gcd(b, a % b);
    }

}

class Range {
    long start = 0;
    long end = 0;
}

class Point implements Comparable {
    int x;
    int y;

    public int compareTo(Object p) {
        Point t = (Point) p;
        return t.y - this.y;
    }
}

class PointY implements Comparable {
    int index;
    long a;
    long b;

    public int compareTo(Object p) {
        PointY t = (PointY) p;
        if (this.a > t.a) {
            return -1;
        }
        if (this.a < t.a) {
            return 1;
        }
        return 0;
    }
}

class FastPrintStream implements AutoCloseable {
    private static final int BUF_SIZE = 1 << 15;
    private final byte[] buf = new byte[BUF_SIZE];
    private int ptr = 0;
    private final java.lang.reflect.Field strField;
    private final java.nio.charset.CharsetEncoder encoder;

    private java.io.OutputStream out;

    public FastPrintStream(java.io.OutputStream out) {
        this.out = out;
        java.lang.reflect.Field f;
        try {
            f = java.lang.String.class.getDeclaredField("value");
            f.setAccessible(true);
        } catch (NoSuchFieldException | SecurityException e) {
            f = null;
        }
        this.strField = f;
        this.encoder = java.nio.charset.StandardCharsets.US_ASCII.newEncoder();
    }

    public FastPrintStream(java.io.File file) throws java.io.IOException {
        this(new java.io.FileOutputStream(file));
    }

    public FastPrintStream(java.lang.String filename) throws java.io.IOException {
        this(new java.io.File(filename));
    }

    public FastPrintStream() {
        this(System.out);
        try {
            java.lang.reflect.Field f = java.io.PrintStream.class.getDeclaredField("autoFlush");
            f.setAccessible(true);
            f.set(System.out, false);
        } catch (IllegalAccessException | IllegalArgumentException | NoSuchFieldException e) {
            // ignore
        }
    }

    public FastPrintStream println() {
        if (ptr == BUF_SIZE)
            internalFlush();
        buf[ptr++] = (byte) '\n';
        return this;
    }

    public FastPrintStream println(java.lang.Object o) {
        return print(o).println();
    }

    public FastPrintStream println(java.lang.String s) {
        return print(s).println();
    }

    public FastPrintStream println(char[] s) {
        return print(s).println();
    }

    public FastPrintStream println(char c) {
        return print(c).println();
    }

    public FastPrintStream println(int x) {
        return print(x).println();
    }

    public FastPrintStream println(long x) {
        return print(x).println();
    }

    public FastPrintStream println(double d, int precision) {
        return print(d, precision).println();
    }

    private FastPrintStream print(byte[] bytes) {
        int n = bytes.length;
        if (ptr + n > BUF_SIZE) {
            internalFlush();
            try {
                out.write(bytes);
            } catch (java.io.IOException e) {
                throw new RuntimeException();
            }
        } else {
            System.arraycopy(bytes, 0, buf, ptr, n);
            ptr += n;
        }
        return this;
    }

    public FastPrintStream print(java.lang.Object o) {
        return print(o.toString());
    }

    public FastPrintStream print(java.lang.String s) {
        if (strField == null) {
            return print(s.getBytes());
        } else {
            try {
                return print((byte[]) strField.get(s));
            } catch (IllegalAccessException e) {
                return print(s.getBytes());
            }
        }
    }

    public FastPrintStream print(char[] s) {
        try {
            return print(encoder.encode(java.nio.CharBuffer.wrap(s)).array());
        } catch (java.nio.charset.CharacterCodingException e) {
            byte[] bytes = new byte[s.length];
            for (int i = 0; i < s.length; i++) {
                bytes[i] = (byte) s[i];
            }
            return print(bytes);
        }
    }

    public FastPrintStream print(char c) {
        if (ptr == BUF_SIZE)
            internalFlush();
        buf[ptr++] = (byte) c;
        return this;
    }

    public FastPrintStream print(int x) {
        if (x == 0) {
            if (ptr == BUF_SIZE)
                internalFlush();
            buf[ptr++] = '0';
            return this;
        }
        int d = len(x);
        if (ptr + d > BUF_SIZE)
            internalFlush();
        if (x < 0) {
            buf[ptr++] = '-';
            x = -x;
            d--;
        }
        int j = ptr += d;
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(long x) {
        if (x == 0) {
            if (ptr == BUF_SIZE)
                internalFlush();
            buf[ptr++] = '0';
            return this;
        }
        int d = len(x);
        if (ptr + d > BUF_SIZE)
            internalFlush();
        if (x < 0) {
            buf[ptr++] = '-';
            x = -x;
            d--;
        }
        int j = ptr += d;
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        return this;
    }

    public FastPrintStream print(double d, int precision) {
        if (d < 0) {
            print('-');
            d = -d;
        }
        d += Math.pow(10, -d) / 2;
        print((long) d).print('.');
        d -= (long) d;
        for (int i = 0; i < precision; i++) {
            d *= 10;
            print((int) d);
            d -= (int) d;
        }
        return this;
    }

    private void internalFlush() {
        try {
            out.write(buf, 0, ptr);
            ptr = 0;
        } catch (java.io.IOException e) {
            throw new RuntimeException(e);
        }
    }

    public void flush() {
        try {
            out.write(buf, 0, ptr);
            out.flush();
            ptr = 0;
        } catch (java.io.IOException e) {
            throw new RuntimeException(e);
        }
    }

    public void close() {
        try {
            out.close();
        } catch (java.io.IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static int len(int x) {
        int d = 1;
        if (x >= 0) {
            d = 0;
            x = -x;
        }
        int p = -10;
        for (int i = 1; i < 10; i++, p *= 10)
            if (x > p)
                return i + d;
        return 10 + d;
    }

    private static int len(long x) {
        int d = 1;
        if (x >= 0) {
            d = 0;
            x = -x;
        }
        long p = -10;
        for (int i = 1; i < 19; i++, p *= 10)
            if (x > p)
                return i + d;
        return 19 + d;
    }
}

class FastScanner implements AutoCloseable {
    private final java.io.InputStream in;
    private final byte[] buf = new byte[2048];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(java.io.InputStream in) {
        this.in = in;
    }

    public FastScanner() {
        this(System.in);
    }

    private boolean hasNextByte() {
        if (ptr < buflen)
            return true;
        ptr = 0;
        try {
            buflen = in.read(buf);
        } catch (java.io.IOException e) {
            throw new RuntimeException(e);
        }
        return buflen > 0;
    }

    private int readByte() {
        return hasNextByte() ? buf[ptr++] : -1;
    }

    public boolean hasNext() {
        while (hasNextByte() && !(32 < buf[ptr] && buf[ptr] < 127))
            ptr++;
        return hasNextByte();
    }

    private StringBuilder nextSequence() {
        if (!hasNext())
            throw new java.util.NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        for (int b = readByte(); 32 < b && b < 127; b = readByte()) {
            sb.appendCodePoint(b);
        }
        return sb;
    }

    public String next() {
        return nextSequence().toString();
    }

    public String next(int len) {
        return new String(nextChars(len));
    }

    public char nextChar() {
        if (!hasNextByte())
            throw new java.util.NoSuchElementException();
        return (char) readByte();
    }

    public char[] nextChars() {
        StringBuilder sb = nextSequence();
        int l = sb.length();
        char[] dst = new char[l];
        sb.getChars(0, l, dst, 0);
        return dst;
    }

    public char[] nextChars(int len) {
        if (!hasNext())
            throw new java.util.NoSuchElementException();
        char[] s = new char[len];
        int i = 0;
        int b = readByte();
        while (32 < b && b < 127 && i < len) {
            s[i++] = (char) b;
            b = readByte();
        }
        if (i != len) {
            throw new java.util.NoSuchElementException(
                    String.format("Next token has smaller length than expected.", len));
        }
        return s;
    }

    public long nextLong() {
        if (!hasNext())
            throw new java.util.NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b)
            throw new NumberFormatException();
        while (true) {
            if ('0' <= b && b <= '9') {
                n = n * 10 + b - '0';
            } else if (b == -1 || !(32 < b && b < 127)) {
                return minus ? -n : n;
            } else
                throw new NumberFormatException();
            b = readByte();
        }
    }

    public int nextInt() {
        return Math.toIntExact(nextLong());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public void close() {
        try {
            in.close();
        } catch (java.io.IOException e) {
            throw new RuntimeException(e);
        }
    }

}

/**
 * @verified https://atcoder.jp/contests/practice2/tasks/practice2_j
 */
class SegTree<S> {
    final int MAX;

    final int N;
    final java.util.function.BinaryOperator<S> op;
    final S E;

    final S[] data;

    @SuppressWarnings("unchecked")
    public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) {
        this.MAX = n;
        int k = 1;
        while (k < n)
            k <<= 1;
        this.N = k;
        this.E = e;
        this.op = op;
        this.data = (S[]) new Object[N << 1];
        java.util.Arrays.fill(data, E);
    }

    public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) {
        this(dat.length, op, e);
        build(dat);
    }

    private void build(S[] dat) {
        int l = dat.length;
        System.arraycopy(dat, 0, data, N, l);
        for (int i = N - 1; i > 0; i--) {
            data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]);
        }
    }

    public void set(int p, S x) {
        exclusiveRangeCheck(p);
        data[p += N] = x;
        p >>= 1;
        while (p > 0) {
            data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]);
            p >>= 1;
        }
    }

    public S get(int p) {
        exclusiveRangeCheck(p);
        return data[p + N];
    }

    public S prod(int l, int r) {
        if (l > r) {
            throw new IllegalArgumentException(String.format("Invalid range: [%d, %d)", l, r));
        }
        inclusiveRangeCheck(l);
        inclusiveRangeCheck(r);
        S sumLeft = E;
        S sumRight = E;
        l += N;
        r += N;
        while (l < r) {
            if ((l & 1) == 1)
                sumLeft = op.apply(sumLeft, data[l++]);
            if ((r & 1) == 1)
                sumRight = op.apply(data[--r], sumRight);
            l >>= 1;
            r >>= 1;
        }
        return op.apply(sumLeft, sumRight);
    }

    public S allProd() {
        return data[1];
    }

    public int maxRight(int l, java.util.function.Predicate<S> f) {
        inclusiveRangeCheck(l);
        if (!f.test(E)) {
            throw new IllegalArgumentException("Identity element must satisfy the condition.");
        }
        if (l == MAX)
            return MAX;
        l += N;
        S sum = E;
        do {
            l >>= Long.numberOfTrailingZeros(l);
            if (!f.test(op.apply(sum, data[l]))) {
                while (l < N) {
                    l = l << 1;
                    if (f.test(op.apply(sum, data[l]))) {
                        sum = op.apply(sum, data[l]);
                        l++;
                    }
                }
                return l - N;
            }
            sum = op.apply(sum, data[l]);
            l++;
        } while ((l & -l) != l);
        return MAX;
    }

    public int minLeft(int r, java.util.function.Predicate<S> f) {
        inclusiveRangeCheck(r);
        if (!f.test(E)) {
            throw new IllegalArgumentException("Identity element must satisfy the condition.");
        }
        if (r == 0)
            return 0;
        r += N;
        S sum = E;
        do {
            r--;
            while (r > 1 && (r & 1) == 1)
                r >>= 1;
            if (!f.test(op.apply(data[r], sum))) {
                while (r < N) {
                    r = r << 1 | 1;
                    if (f.test(op.apply(data[r], sum))) {
                        sum = op.apply(data[r], sum);
                        r--;
                    }
                }
                return r + 1 - N;
            }
            sum = op.apply(data[r], sum);
        } while ((r & -r) != r);
        return 0;
    }

    private void exclusiveRangeCheck(int p) {
        if (p < 0 || p >= MAX) {
            throw new IndexOutOfBoundsException(
                    String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX));
        }
    }

    private void inclusiveRangeCheck(int p) {
        if (p < 0 || p > MAX) {
            throw new IndexOutOfBoundsException(
                    String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX));
        }
    }

    // **************** DEBUG **************** //

    private int indent = 6;

    public void setIndent(int newIndent) {
        this.indent = newIndent;
    }

    @Override
    public String toString() {
        return toSimpleString();
    }

    public String toDetailedString() {
        return toDetailedString(1, 0);
    }

    private String toDetailedString(int k, int sp) {
        if (k >= N)
            return indent(sp) + data[k];
        String s = "";
        s += toDetailedString(k << 1 | 1, sp + indent);
        s += "\n";
        s += indent(sp) + data[k];
        s += "\n";
        s += toDetailedString(k << 1 | 0, sp + indent);
        return s;
    }

    private static String indent(int n) {
        StringBuilder sb = new StringBuilder();
        while (n-- > 0)
            sb.append(' ');
        return sb.toString();
    }

    public String toSimpleString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i < N; i++) {
            sb.append(data[i + N]);
            if (i < N - 1)
                sb.append(',').append(' ');
        }
        sb.append(']');
        return sb.toString();
    }
}

class DSU {
    private int n;
    private int[] parentOrSize;

    public DSU(int n) {
        this.n = n;
        this.parentOrSize = new int[n];
        Arrays.fill(parentOrSize, -1);
    }

    int merge(int a, int b) {
        if (!(0 <= a && a < n) || !(0 <= b && b < n)) {
            return -1;
        }
        int x = leader(a);
        int y = leader(b);
        if (x == y)
            return x;
        if (-parentOrSize[x] < -parentOrSize[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        parentOrSize[x] += parentOrSize[y];
        parentOrSize[y] = x;
        return x;
    }

    boolean same(int a, int b) {
        if (!(0 <= a && a < n) || !(0 <= b && b < n)) {
            return false;
        }
        return leader(a) == leader(b);
    }

    int leader(int a) {
        if (parentOrSize[a] < 0) {
            return a;
        } else {
            parentOrSize[a] = leader(parentOrSize[a]);
            return parentOrSize[a];
        }
    }

    int size(int a) {
        if (!(0 <= a && a < n)) {
            return -1;
        }
        return -parentOrSize[leader(a)];
    }

    ArrayList<ArrayList<Integer>> groups() {
        int[] leaderBuf = new int[n];
        int[] groupSize = new int[n];
        for (int i = 0; i < n; i++) {
            leaderBuf[i] = leader(i);
            groupSize[leaderBuf[i]]++;
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < n; i++) {
            result.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            result.get(leaderBuf[i]).add(i);
        }
        return result;
    }
}
