Problem: There are N rabbits on a number line. The rabbits are conveniently numbered 1 through N. The coordinate of the initial position of rabbit i is x_i.

The rabbits will now take exercise on the number line, by performing sets described below. A set consists of M jumps. The j-th jump of a set is performed by rabbit a_j (2≤a_j≤N-1). For this jump, either rabbit a_j-1 or rabbit a_j+1 is chosen with equal probability (let the chosen rabbit be rabbit x), then rabbit a_j will jump to the symmetric point of its current position with respect to rabbit x.

The rabbits will perform K sets in succession. For each rabbit, find the expected value of the coordinate of its eventual position after K sets are performed.

Constraints

* 3≤N≤10^5
* x_i is an integer.
* |x_i|≤10^9
* 1≤M≤10^5
* 2≤a_j≤N-1
* 1≤K≤10^{18}

Input

The input is given from Standard Input in the following format:


N
x_1 x_2 ... x_N
M K
a_1 a_2 ... a_M


Output

Print N lines. The i-th line should contain the expected value of the coordinate of the eventual position of rabbit i after K sets are performed. The output is considered correct if the absolute or relative error is at most 10^{-9}.

Examples

Input

3
-1 0 2
1 1
2


Output

-1.0
1.0
2.0


Input

3
1 -1 1
2 2
2 2


Output

1.0
-1.0
1.0


Input

5
0 1 3 6 10
3 10
2 3 4


Output

0.0
3.0
7.0
8.0
10.0

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author daltao
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "daltao", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            TaskC solver = new TaskC();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class TaskC {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int[] xs = new int[n];
            int[] dx = new int[n];
            int[] swap = new int[n];
            for (int i = 0; i < n; i++) {
                xs[i] = in.readInt();
                if (i > 0) {
                    dx[i] = xs[i] - xs[i - 1];
                } else {
                    dx[0] = xs[0];
                }
                swap[i] = i;
            }

            int m = in.readInt();
            long k = in.readLong();
            for (int i = 0; i < m; i++) {
                int j = in.readInt() - 1;
                ArrayUtils.swap(swap, j, j + 1);
            }

            Permutations.PowerPermutation perm = new Permutations.PowerPermutation(swap);

            int[] results = new int[n + 1];
            results[0] = dx[0];
            for (int i = 1; i < n; i++) {
                results[i] = dx[perm.apply(i, k)];
            }

            long prefix = 0;
            for (int i = 0; i < n; i++) {
                prefix += results[i];
                out.println(prefix);
            }
        }

    }

    static class FastOutput implements AutoCloseable, Closeable {
        private StringBuilder cache = new StringBuilder(1 << 20);
        private final Writer os;

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput println(long c) {
            cache.append(c).append('\n');
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

    }

    static class Permutations {
        private static final long[] PERMUTATION_CNT = new long[21];

        static {
            PERMUTATION_CNT[0] = 1;
            for (int i = 1; i <= 20; i++) {
                PERMUTATION_CNT[i] = PERMUTATION_CNT[i - 1] * i;
            }
        }

        public static class PowerPermutation {
            int[] g;
            int[] idx;
            int[] l;
            int[] r;
            int n;

            public PowerPermutation(int[] p) {
                this(p, p.length);
            }

            public PowerPermutation(int[] p, int len) {
                n = len;
                boolean[] visit = new boolean[n];
                g = new int[n];
                l = new int[n];
                r = new int[n];
                idx = new int[n];
                int wpos = 0;
                for (int i = 0; i < n; i++) {
                    int val = p[i];
                    if (visit[val]) {
                        continue;
                    }
                    visit[val] = true;
                    g[wpos] = val;
                    l[wpos] = wpos;
                    idx[val] = wpos;
                    wpos++;
                    while (true) {
                        int x = p[g[wpos - 1]];
                        if (visit[x]) {
                            break;
                        }
                        visit[x] = true;
                        g[wpos] = x;
                        l[wpos] = l[wpos - 1];
                        idx[x] = wpos;
                        wpos++;
                    }
                    for (int j = l[wpos - 1]; j < wpos; j++) {
                        r[j] = wpos - 1;
                    }
                }
            }

            public int apply(int x, int p) {
                int i = idx[x];
                int dist = DigitUtils.mod((i - l[i]) + p, r[i] - l[i] + 1);
                return g[dist + l[i]];
            }

            public int apply(int x, long p) {
                int i = idx[x];
                int dist = DigitUtils.mod((i - l[i]) + p, r[i] - l[i] + 1);
                return g[dist + l[i]];
            }

            public String toString() {
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    builder.append(apply(i, 1)).append(' ');
                }
                return builder.toString();
            }

        }

    }

    static class ArrayUtils {
        public static void swap(int[] data, int i, int j) {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int mod(long x, int mod) {
            x %= mod;
            if (x < 0) {
                x += mod;
            }
            return (int) x;
        }

        public static int mod(int x, int mod) {
            x %= mod;
            if (x < 0) {
                x += mod;
            }
            return x;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
}