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.io.BufferedInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main
{	
	/********************************************** a list of common variables **********************************************/
	private MyScanner scan = new MyScanner();
	private PrintWriter out = new PrintWriter(System.out);
	private final double PI = Math.PI;
	private final int INF = (int)(1e9);
	private final double EPS = 1e-6;
	private final int SIZEN = (int)(1e5);
	private final int MOD = (int)(1e9 + 7);
	private final long MODH = 10000000007L, BASE = 10007;
	private final int[] DX = {0, 1, 0, -1}, DY = {-1, 0, 1, 0};

  	public void foo()
  	{
  		int n = scan.nextInt();
  		int[] w = new int[n];
  		for(int i = 0;i < n;++i) w[i] = scan.nextInt();
  		int p = scan.nextInt();
  		Query[] q = new Query[p];
  		for(int i = 0;i < p;++i)
  		{
  			q[i] = new Query(scan.nextInt() - 1, scan.nextInt(), i);
  		}
  		Arrays.sort(q);
  		long[] ans = new long[p];
  		long[] dp = new long[n];
  		int thr = (int)Math.sqrt((double)n);
  		for(int i = 0;i < p;++i)
  		{
  			if(q[i].d > thr)
  			{
  				for(int j = q[i].left;j < n;j += q[i].d) ans[q[i].index] += w[j];
  			}
  			else
  			{
  				if(0 == i || i > 0 && q[i].d != q[i - 1].d)
  				{
  					for(int j = n - 1;j >= 0;--j)
  					{
  						if(j + q[i].d >= n) dp[j] = w[j];
  						else dp[j] = dp[j + q[i].d] + w[j];
  					}
  				}
  				ans[q[i].index] = dp[q[i].left];
  			}
  		}
  		for(int i = 0;i < p;++i) out.println(ans[i]);
    } 

	public static void main(String[] args)
	{
		Main m = new Main();
		m.foo();
		m.out.close();
	}
	
	class Query implements Comparable<Query>
	{
		private int left, d, index;
		public Query(int aLeft, int aD, int aIndex)
		{
			left = aLeft;
			d = aD;
			index = aIndex;
		}
		public int compareTo(Query q)
		{
			return q.d - d;
		}
	}

	/********************************************** a list of common algorithms **********************************************/
	/**
	 * 1---Get greatest common divisor
	 * @param a :	first number
	 * @param b :	second number
	 * @return		greatest common divisor
	 */
	public long gcd(long a, long b)
	{
		return 0 == b ? a : gcd(b, a % b);
	}
	
	/**
	 * 2---Get the distance from a point to a line
	 * @param x1	the x coordinate of one endpoint of the line
	 * @param y1	the y coordinate of one endpoint of the line
	 * @param x2	the x coordinate of the other endpoint of the line
	 * @param y2	the y coordinate of the other endpoint of the line
	 * @param x		the x coordinate of the point 
	 * @param y		the x coordinate of the point
	 * @return		the distance from a point to a line
	 */
	public double getDist(long x1, long y1, long x2, long y2, long x, long y)
	{
		long a = y2 - y1;
		long b = x1 - x2;
		long c = y1 * (x2 - x1) - x1 * (y2 - y1);
		return Math.abs(a * x + b * y + c) / Math.sqrt(a * a + b * b);
	}
	
	/**
	 * 3---Get the distance from one point to a segment (not a line)
	 * @param x1	the x coordinate of one endpoint of the segment
	 * @param y1	the y coordinate of one endpoint of the segment
	 * @param x2	the x coordinate of the other endpoint of the segment
	 * @param y2	the y coordinate of the other endpoint of the segment
	 * @param x		the x coordinate of the point
	 * @param y		the y coordinate of the point
	 * @return		the distance from one point to a segment (not a line)
	 */
	public double ptToSeg(long x1, long y1, long x2, long y2, long x, long y)
	{
		double cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1);
		if(cross <= 0)
		{
			return (x - x1) * (x - x1) + (y - y1) * (y - y1);
		}
		double d = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
		if(cross >= d) 
		{
			return (x - x2) * (x - x2) + (y - y2) * (y - y2);
		}
		double r = cross / d;
		double px = x1 + (x2 - x1) * r;
		double py = y1 + (y2 - y1) * r;
		return (x - px) * (x - px) + (y - py) * (y - py);
	}
	
	/**
	 * 4---KMP match, i.e. kmpMatch("abcd", "bcd") = 1, kmpMatch("abcd", "bfcd") = -1.
	 * @param t:	String to match.
	 * @param p:	String to be matched.
	 * @return		if can match, first index; otherwise -1.
	 */
	public int kmpMatch(char[] t, char[] p)
	{
		int n = t.length;
		int m = p.length;
		int[] next = new int[m + 1];
		next[0] = -1;
		int j = -1;
		for(int i = 1;i < m;++i)
		{
			while(j >= 0 && p[i] != p[j + 1])
			{
				j = next[j];
			}
			if(p[i] == p[j + 1])
			{
				++j;
			}
			next[i] = j;
		}
		j = -1;
		for(int i = 0;i < n;++i)
		{
			while(j >= 0 && t[i] != p[j + 1])
			{
				j = next[j];
			}
			if(t[i] == p[j + 1])
			{
				++j;
			}
			if(j == m - 1)
			{
				return i - m + 1;
			}
		}
		return -1;
	}
	
	/**
	 * 5---Get the hash code of a String
	 * @param	s:	input string
	 * @return	hash code
	 */
	public long hash(String s)
	{
		long key = 0, t = 1;
		for(int i = 0;i < s.length();++i)
		{
			key = (key + s.charAt(i) * t) % MODH;
			t = t * BASE % MODH;
		}
		return key;
	}
	
	/**
	 * 6---Get x ^ n % MOD quickly.
	 * @param	x:	base
	 * @param 	n:	times
	 * @return	x ^ n % MOD
	 */
	public long quickMod(long x, long n)
	{
		long ans = 1;
		while(n > 0)
		{
			if(1 == n % 2)
			{
				ans = ans * x % MOD;
 			}
			x = x * x % MOD;
			n >>= 1;
		}
		return ans;
	}
	
	/**
	 * 7---judge if a point is located inside a polygon
	 * @param x0	the x coordinate of the point
	 * @param y0	the y coordinate of the point
	 * @return true if it is inside the polygon, otherwise false
	 */
	/*public boolean contains(double x0, double y0)
	{
		int cross = 0;
		for(int i = 0;i < n;++i)
		{
			double s = x[i + 1] == x[i] ? 100000000 : (double)(y[i + 1] - y[i]) / (x[i + 1] - x[i]);
			boolean b1 = x[i] <= x0 && x0 < x[i + 1];
			boolean b2 = x[i + 1] <= x0 && x0 < x[i];
			boolean b3 = y0 < s * (x0 - x[i]) + y[i];
			if((b1 || b2) && b3) ++cross;
		}
		return cross % 2 != 0;
	}*/
	
	/**
	 * 8---judge if a point is located on the segment
	 * @param	x1	the x coordinate of one point of the segment
	 * @param	y1	the y coordinate of one point of the segment
	 * @param 	x2	the x coordinate of another point of the segment
	 * @param 	y2	the y coordinate of another point of the segment
	 * @param	x	the x coordinate of the point
	 * @param 	y	the y coordinate of the point
	 * @return	true if it is located on the segment, otherwise false
	 */
	public boolean isOnSeg(long x1, long y1, long x2, long y2, long x, long y)
	{
		return (x - x1) * (y2 - y1) == (x2 - x1) * (y - y1) && 
				x >= Math.min(x1, x2) && x <= Math.max(x1, x2) && 
				y >= Math.min(y1, y2) && y <= Math.max(y1, y2);
	}
	
	/**
	 * 9---get the cross product
	 * @param 	p1	point A
	 * @param 	p2	point B
	 * @param 	p	point O
	 * @return	cross product of OA x OB
	 */
	/*public long cross(Point p1, Point p2, Point p)
	{
		return (long)(p1.x - p.x) * (p2.y - p.y) - (long)(p2.x - p.x) * (p1.y - p.y);
	}*/
	
	/**
	 * 10---implement topsort and tell if it is possible
	 * @return true if it is possible to implement topsort, otherwise false
	 */
	/*public boolean topsort()
	{
		Queue<Integer> q = new LinkedList<Integer>();
		StringBuilder ans = new StringBuilder();
		int[] in = new int[26];
		for(int i = 0;i < 26;++i)
		{
			if(0 == in[i]) 
			{
				ans.append((char)('a' + i));
				q.add(i);
			}
		}
		while(!q.isEmpty())
		{
			int u = q.poll();
			for(int i = 0;i < 26;++i)
			{
				if(map[u][i])
				{
					--in[i];
					if(0 == in[i])
					{
						ans.append((char)('a' + i));
						q.add(i);
					}
				}
			}
		}
		return 26 == ans.length();
	}*/
	
	class MyScanner
	{
	    private byte[] buf = new byte[1024];
	    private int curChar;
	    private int numChars;
	    BufferedInputStream bis = new BufferedInputStream(System.in);

	    public int read() 
	    {
	        if (-1 == numChars)
	        {
	        	throw new InputMismatchException();
	        }
	        if (curChar >= numChars)
	        {
	            curChar = 0;
	            try 
	            {
	                numChars = bis.read(buf);
	            }
	            catch (IOException e)
	            {
	                throw new InputMismatchException();
	            }
	            if (numChars <= 0)
	            {
	            	return -1;
	            }
	        }
	        return buf[curChar++];
	    }

	    public int nextInt() 
	    {
	        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 nextLong() 
	    {
	    	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 double nextDouble() 
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        int sgn = 1;
	        if (c == '-')
	        {
	            sgn = -1;
	            c = read();
	        }
	        double res = 0;
	        while (!isSpaceChar(c) && c != '.') 
	        {
	            if (c == 'e' || c == 'E')
	            {
	            	return res * Math.pow(10, nextInt());
	            }
	            if (c < '0' || c > '9')
	            {
	            	throw new InputMismatchException();
	            }
	            res *= 10;
	            res += c & 15;
	            c = read();
	        }
	        if (c == '.') 
	        {
	            c = read();
	            double m = 1;
	            while (!isSpaceChar(c)) 
	            {
	                if (c == 'e' || c == 'E')
	                {
	                	return res * Math.pow(10, nextInt());
	                }
	                if (c < '0' || c > '9')
	                {
	                	throw new InputMismatchException();
	                }
	                m /= 10;
	                res += (c & 15) * m;
	                c = read();
	            }
	        }
	        return res * sgn;
	    }
	    
	    public String next()
	    {
	        int c = read();
	        while (isSpaceChar(c))
	        {
	        	c = read();
	        }
	        StringBuilder res = new StringBuilder();
	        do 
	        {
	            res.appendCodePoint(c);
	            c = read();
	        } while (!isSpaceChar(c));
	        return res.toString();
	    }

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