Problem: In this problem you will have to deal with a real algorithm that is used in the VK social network.

As in any other company that creates high-loaded websites, the VK developers have to deal with request statistics regularly. An important indicator reflecting the load of the site is the mean number of requests for a certain period of time of T seconds (for example, T = 60 seconds = 1 min and T = 86400 seconds = 1 day). For example, if this value drops dramatically, that shows that the site has access problem. If this value grows, that may be a reason to analyze the cause for the growth and add more servers to the website if it is really needed.

However, even such a natural problem as counting the mean number of queries for some period of time can be a challenge when you process the amount of data of a huge social network. That's why the developers have to use original techniques to solve problems approximately, but more effectively at the same time.

Let's consider the following formal model. We have a service that works for n seconds. We know the number of queries to this resource at at each moment of time t (1 ≤ t ≤ n). Let's formulate the following algorithm of calculating the mean with exponential decay. Let c be some real number, strictly larger than one.
    
    
      
    // setting this constant value correctly can adjust     
    // the time range for which statistics will be calculated  
    double c = some constant value;   
      
    // as the result of the algorithm's performance this variable will contain   
    // the mean number of queries for the last   
    // T seconds by the current moment of time  
    double mean = 0.0;   
      
    for t = 1..n: // at each second, we do the following:  
        // at is the number of queries that came at the last second;  
        mean = (mean + at / T) / c;  
    

Thus, the mean variable is recalculated each second using the number of queries that came at that second. We can make some mathematical calculations and prove that choosing the value of constant c correctly will make the value of mean not very different from the real mean value ax at t - T + 1 ≤ x ≤ t. 

The advantage of such approach is that it only uses the number of requests at the current moment of time and doesn't require storing the history of requests for a large time range. Also, it considers the recent values with the weight larger than the weight of the old ones, which helps to react to dramatic change in values quicker.

However before using the new theoretical approach in industrial programming, there is an obligatory step to make, that is, to test its credibility practically on given test data sets. Your task is to compare the data obtained as a result of the work of an approximate algorithm to the real data. 

You are given n values at, integer T and real number c. Also, you are given m moments pj (1 ≤ j ≤ m), where we are interested in the mean value of the number of queries for the last T seconds. Implement two algorithms. The first one should calculate the required value by definition, i.e. by the formula <image>. The second algorithm should calculate the mean value as is described above. Print both values and calculate the relative error of the second algorithm by the formula <image>, where approx is the approximate value, obtained by the second algorithm, and real is the exact value obtained by the first algorithm.

Input

The first line contains integer n (1 ≤ n ≤ 2·105), integer T (1 ≤ T ≤ n) and real number c (1 < c ≤ 100) — the time range when the resource should work, the length of the time range during which we need the mean number of requests and the coefficient c of the work of approximate algorithm. Number c is given with exactly six digits after the decimal point.

The next line contains n integers at (1 ≤ at ≤ 106) — the number of queries to the service at each moment of time.

The next line contains integer m (1 ≤ m ≤ n) — the number of moments of time when we are interested in the mean number of queries for the last T seconds.

The next line contains m integers pj (T ≤ pj ≤ n), representing another moment of time for which we need statistics. Moments pj are strictly increasing.

Output

Print m lines. The j-th line must contain three numbers real, approx and error, where:

  * <image> is the real mean number of queries for the last T seconds; 
  * approx is calculated by the given algorithm and equals mean at the moment of time t = pj (that is, after implementing the pj-th iteration of the cycle); 
  * <image> is the relative error of the approximate algorithm. 



The numbers you printed will be compared to the correct numbers with the relative or absolute error 10 - 4. It is recommended to print the numbers with at least five digits after the decimal point.

Examples

Input

1 1 2.000000
1
1
1


Output

1.000000 0.500000 0.500000


Input

11 4 1.250000
9 11 7 5 15 6 6 6 6 6 6
8
4 5 6 7 8 9 10 11


Output

8.000000 4.449600 0.443800
9.500000 6.559680 0.309507
8.250000 6.447744 0.218455
8.000000 6.358195 0.205226
8.250000 6.286556 0.237993
6.000000 6.229245 0.038207
6.000000 6.183396 0.030566
6.000000 6.146717 0.024453


Input

13 4 1.250000
3 3 3 3 3 20 3 3 3 3 3 3 3
10
4 5 6 7 8 9 10 11 12 13


Output

3.000000 1.771200 0.409600
3.000000 2.016960 0.327680
7.250000 5.613568 0.225715
7.250000 5.090854 0.297813
7.250000 4.672684 0.355492
7.250000 4.338147 0.401635
3.000000 4.070517 0.356839
3.000000 3.856414 0.285471
3.000000 3.685131 0.228377
3.000000 3.548105 0.182702

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

/**
 * @author master_j
 * @version 0.4
 * @since May 3, 2014
 */
public class Main {

    private void solve() throws IOException {
        int n = io.nI(), T = io.nI();
        double c = io.nD();
        long sum = 0;
        double[] real = new double[n];
        double[] approx = new double[n];
        double[] error = new double[n];
        double mean = 0.0d;
        int[] load = new int[n];

        for (int i = 0; i < n; i++){
            load[i] = io.nI();
            sum += load[i];
            if(0 <= i - T)
                sum -= load[i - T];
            real[i] = 1.0d*sum / T;
            mean = (mean + 1.0d * load[i] / T) / c;
            approx[i] = mean;
            error[i] = Math.abs(real[i] - approx[i]) / real[i];
        }

        String one = "%.9f", frm = String.format("%s %s %s", one, one, one);

        int m = io.nI();
        for (int i = 0; i < m; i++) {
            int j = io.nI() - 1;
            io.wln(String.format(frm, real[j], approx[j], error[j]));
        }
    }//2.2250738585072012e-308

    void trace(boolean[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++)
                io.w(map[i][j] ? '*' : '.');
            io.wln();
        }
    }

    boolean[][] rotate(boolean[][] map) {
        boolean[][] res = new boolean[map[0].length][map.length];
        for (int i = 0; i < res.length; i++)
            for (int j = 0; j < res[i].length; j++)
                res[i][j] = map[map.length - j - 1][i];
        return res;
    }

    boolean[][] upsidedown(boolean[][] map) {
        boolean[][] res = new boolean[map.length][map[0].length];
        for (int i = 0; i < map.length; i++)
            res[i] = map[map.length - i - 1].clone();
        return res;
    }

    boolean[][] rastaraschting(boolean[][] map) {//It's like Russian borscht but scale.
        boolean[][] res = new boolean[2 * map.length][2 * map[0].length];
        for (int i = 0; i < res.length; i++)
            for (int j = 0; j < res[i].length; j++)
                res[i][j] = map[i / 2][j / 2];
        return res;
    }

    public static void main(String[] args) throws IOException {
        IO.launchSolution(args);
    }

    Main(IO io) throws IOException {
        this.io = io;
        solve();
    }

    private final IO io;
}

class IO {
    static final String _localArg = "master_j";
    private static final String _problemName = "";
    private static final IO.Mode _inMode = Mode.STD_;
    private static final IO.Mode _outMode = Mode.STD_;
    private static final boolean _autoFlush = false;

    static enum Mode {STD_, _PUT_TXT, PROBNAME_}

    private final StreamTokenizer st;
    private final BufferedReader br;
    private final Reader reader;

    private final PrintWriter pw;
    private final Writer writer;

    static void launchSolution(String[] args) throws IOException {
        boolean local = (args.length == 1 && args[0].equals(IO._localArg));
        IO io = new IO(local);

        long nanoTime = 0;
        if (local) {
            nanoTime -= System.nanoTime();
            io.wln("<output>");
        }

        io.flush();
        new Main(io);
        io.flush();

        if(local){
            io.wln("</output>");
            nanoTime += System.nanoTime();
            final long D9 = 1000000000, D6 = 1000000, D3 = 1000;
            if(nanoTime >= D9)
                io.wf("%d.%d seconds\n", nanoTime/D9, nanoTime%D9);
            else if(nanoTime >= D6)
                io.wf("%d.%d millis\n", nanoTime/D6, nanoTime%D6);
            else if(nanoTime >= D3)
                io.wf("%d.%d micros\n", nanoTime/D3, nanoTime%D3);
            else
                io.wf("%d nanos\n", nanoTime);
        }

        io.close();
    }

    IO(boolean local) throws IOException {
        if(_inMode == Mode.PROBNAME_ || _outMode == Mode.PROBNAME_)
            if(_problemName.length() == 0)
                throw new IllegalStateException("You imbecile. Where's my <_problemName>?");

        if(_problemName.length() > 0)
            if(_inMode != Mode.PROBNAME_ && _outMode != Mode.PROBNAME_)
                throw new IllegalStateException("You imbecile. What's the <_problemName> for?");

        Locale.setDefault(Locale.US);

        if (local) {
            reader = new FileReader("input.txt");
            writer = new OutputStreamWriter(System.out);
        } else {
            switch (_inMode) {
                case STD_:
                    reader = new InputStreamReader(System.in);
                    break;
                case PROBNAME_:
                    reader = new FileReader(_problemName + ".in");
                    break;
                case _PUT_TXT:
                    reader = new FileReader("input.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _inMode.");
            }
            switch (_outMode) {
                case STD_:
                    writer = new OutputStreamWriter(System.out);
                    break;
                case PROBNAME_:
                    writer = new FileWriter(_problemName + ".out");
                    break;
                case _PUT_TXT:
                    writer = new FileWriter("output.txt");
                    break;
                default:
                    throw new NullPointerException("You imbecile. Gimme _outMode.");
            }
        }

        br = new BufferedReader(reader);
        st = new StreamTokenizer(br);

        pw = new PrintWriter(writer, _autoFlush);

        if(local && _autoFlush)
            wln("Note: auto-flush is on.");
    }

    void wln()          {pw.println(); }
    void wln(boolean x) {pw.println(x);}
    void wln(char x)    {pw.println(x);}
    void wln(char x[])  {pw.println(x);}
    void wln(double x)  {pw.println(x);}
    void wln(float x)   {pw.println(x);}
    void wln(int x)     {pw.println(x);}
    void wln(long x)    {pw.println(x);}
    void wln(Object x)  {pw.println(x);}
    void wln(String x)  {pw.println(x);}

    void wf(String f, Object...o){pw.printf(f, o);}

    void w(boolean x)   {pw.print(x);}
    void w(char x)      {pw.print(x);}
    void w(char x[])    {pw.print(x);}
    void w(double x)    {pw.print(x);}
    void w(float x)     {pw.print(x);}
    void w(int x)       {pw.print(x);}
    void w(long x)      {pw.print(x);}
    void w(Object x)    {pw.print(x);}
    void w(String x)    {pw.print(x);}

    int nI() throws IOException    {st.nextToken(); return (int)st.nval;}
    double nD() throws IOException {st.nextToken(); return st.nval;}
    float nF() throws IOException  {st.nextToken(); return (float)st.nval;}
    long nL() throws IOException   {st.nextToken(); return (long)st.nval;}
    String nS() throws IOException {st.nextToken(); return st.sval;}

    void wc(String x){ wc(x.toCharArray()); }
    void wc(char c1, char c2){for(char c = c1; c<=c2; c++)wc(c);}
    void wc(char x[]){
        for(char c : x)
            wc(c);
    }
    void wc(char x){st.ordinaryChar(x); st.wordChars(x, x);}

    public boolean eof() {return st.ttype == StreamTokenizer.TT_EOF;}
    public boolean eol() {return st.ttype == StreamTokenizer.TT_EOL;}

    void flush(){pw.flush();}
    void close() throws IOException{reader.close(); br.close(); flush(); pw.close();}
}