Problem: As you know, the most intelligent beings on the Earth are, of course, cows. This conclusion was reached long ago by the Martian aliens, as well as a number of other intelligent civilizations from outer space. 

Sometimes cows gather into cowavans. This seems to be seasonal. But at this time the cows become passive and react poorly to external stimuli. A cowavan is a perfect target for the Martian scientific saucer, it's time for large-scale abductions, or, as the Martians say, raids. Simply put, a cowavan is a set of cows in a row. 

If we number all cows in the cowavan with positive integers from 1 to n, then we can formalize the popular model of abduction, known as the (a, b)-Cowavan Raid: first they steal a cow number a, then number a + b, then — number a + 2·b, and so on, until the number of an abducted cow exceeds n. During one raid the cows are not renumbered. 

The aliens would be happy to place all the cows on board of their hospitable ship, but unfortunately, the amount of cargo space is very, very limited. The researchers, knowing the mass of each cow in the cowavan, made p scenarios of the (a, b)-raid. Now they want to identify the following thing for each scenario individually: what total mass of pure beef will get on board of the ship. All the scenarios are independent, in the process of performing the calculations the cows are not being stolen. 

<image>

Input

The first line contains the only positive integer n (1 ≤ n ≤ 3·105) — the number of cows in the cowavan.

The second number contains n positive integer wi, separated by spaces, where the i-th number describes the mass of the i-th cow in the cowavan (1 ≤ wi ≤ 109).

The third line contains the only positive integer p — the number of scenarios of (a, b)-raids (1 ≤ p ≤ 3·105).

Each following line contains integer parameters a and b of the corresponding scenario (1 ≤ a, b ≤ n).

Output

Print for each scenario of the (a, b)-raid the total mass of cows, that can be stolen using only this scenario.

Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams of the %I64d specificator.

Examples

Input

3
1 2 3
2
1 1
1 2


Output

6
4


Input

4
2 3 5 7
3
1 3
2 3
2 2


Output

9
3
10

Solution (in JAVA):

Solution:
import java.util.NavigableSet;
import java.util.Map;
import java.util.Collections;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.math.BigInteger;
import java.util.*;
import java.util.Collection;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.io.*;
import java.util.Iterator;
import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * Generated by Contest helper plug-in
 * Actual solution is at the bottom
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new StreamInputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		run(in, out);
	}

	public static void run(InputReader in, PrintWriter out) {
		Solver solver = new TaskD();
		solver.solve(1, in, out);
		Exit.exit(in, out);
	}
}

abstract class InputReader {
	private boolean finished = false;

	public abstract int read();

	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 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 String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public void setFinished(boolean finished) {
		this.finished = finished;
	}

	public abstract void close();
}

class StreamInputReader extends InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar, numChars;

	public StreamInputReader(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 void close() {
		try {
			stream.close();
		} catch (IOException ignored) {
		}
	}
}

class Exit {
	private Exit() {
	}

	public static void exit(InputReader in, PrintWriter out) {
		in.setFinished(true);
		in.close();
		out.close();
	}
}

interface Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out);
}

class ArrayUtils {
	public static Integer[] generateOrder(int size) {
		Integer[] order = new Integer[size];
		for (int i = 0; i < size; i++)
			order[i] = i;
		return order;
	}

	public static Integer[] order(int size, Comparator<Integer> comparator) {
		Integer[] order = generateOrder(size);
		Arrays.sort(order, comparator);
		return order;
	}

	}

abstract class ReadOnlyIterator<T> implements Iterator<T>  {
	public final void remove() {
		throw new UnsupportedOperationException();
	}
}

abstract class AbstractSequence<T> implements Sequence<T> {

	public Iterator<T> iterator() {
		return new ReadOnlyIterator<T>() {
			private int index = 0;

			public boolean hasNext() {
				return index != size();
			}

			public T next() {
				if (!hasNext())
					throw new NoSuchElementException();
				return get(index++);
			}
		};
	}

	}

abstract class AbstractWritableSequence<T> extends AbstractSequence<T> implements WritableSequence<T> {

	}

abstract class ArrayWrapper<T> extends AbstractWritableSequence<T> {

	public static WritableSequence<Integer> wrap(int...array) {
		return new IntArrayWrapper(array);
	}

	protected static class IntArrayWrapper extends ArrayWrapper<Integer> {
		protected final int[] array;

		protected IntArrayWrapper(int[] array) {
			this.array = array;
		}

		public int size() {
			return array.length;
		}

		public Integer get(int index) {
			return array[index];
		}

		}

	}

interface Sequence<T> extends Iterable<T> {
	public int size();
	public T get(int index);
}

class SequenceUtils {

	public static Integer[] order(final Sequence<? extends Comparable<?>>...sequences) {
		return ArrayUtils.order(sequences[0].size(), new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				for (Sequence<? extends Comparable> sequence : sequences) {
					//noinspection unchecked
					int value = sequence.get(o1).compareTo(sequence.get(o2));
					if (value != 0)
						return value;
				}
				return 0;
			}
		});
	}

	}

interface WritableSequence<T> extends Sequence<T> {
	}

class IOUtils {

	public static long[] readLongArray(InputReader in, int size) {
		long[] array = new long[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readLong();
		return array;
	}

	public static void readIntArrays(InputReader in, int[]... arrays) {
		for (int i = 0; i < arrays[0].length; i++) {
			for (int j = 0; j < arrays.length; j++)
				arrays[j][i] = in.readInt();
		}
	}

	}

class TaskD implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
		int count = in.readInt();
		long[] weights = IOUtils.readLongArray(in, count);
		int queryCount = in.readInt();
		int[] a = new int[queryCount];
		int[] b = new int[queryCount];
		IOUtils.readIntArrays(in, a, b);
		Integer[] order = SequenceUtils.order(ArrayWrapper.wrap(b));
		int lastB = 0;
		long[] temp = new long[count];
		long[] answer = new long[queryCount];
		int max = (int) (Math.sqrt(count) + .5);
		for (int i : order) {
			if (b[i] != lastB) {
				if (b[i] > max) {
					for (int j = a[i] - 1; j < count; j += b[i])
						answer[i] += weights[j];
					continue;
				} else {
					for (int j = count - 1; j >= 0; j--) {
						if (j >= count - b[i])
							temp[j] = weights[j];
						else
							temp[j] = weights[j] + temp[j + b[i]];
					}
					lastB = b[i];
				}
			}
			answer[i] = temp[a[i] - 1];
		}
		for (long value : answer)
			out.println(value);
	}
}