A. Tricky Sum(模拟)

In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.

For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 20, 21 and 22 respectively.

Calculate the answer for t values of n.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.

Each of next t lines contains a single integer n (1 ≤ n ≤ 109).

Output

Print the requested sum for each of t integers n given in the input.

Examples

input

241000000000

output

-4499999998352516354

Note

The answer for the first sample is explained in the statement.

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 int main() 5 { 6     LL n; 7     int t; 8     scanf("%d" , &t); 9     while(t--)10     {11         LL sum = 0;12         scanf("%I64d" , &n);13         sum = n * (n + 1) / 2;14         for(int i = 0 ; (1 << i) <= n ; ++i)15         {16             sum -= (1 << i) << 1;17         }18         printf("%I64d\n" , sum);19     }20 21 }

View Code

B. Queries on a String(模拟)

You are given a string s and should process m queries. Each query is described by two 1-based indices l**i, r**i and integer k**i. It means that you should cyclically shift the substring s[l**i... r**i] k**i times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is abacaba and the query is l1 = 3, r1 = 6, k1 = 1 then the answer is abbacaa. If after that we would process the query l2 = 1, r2 = 4, k2 = 2 then we would get the string baabcaa.

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 10 000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers l**i, r**i and k**i (1 ≤ l**i ≤ r**i ≤ |s|, 1 ≤ k**i ≤ 1 000 000) — the description of the i-th query.

Output

Print the resulting string s after processing all m queries.

Examples

input

abacaba23 6 11 4 2

output

baabcaa

Note

The sample is described in problem statement.

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 1e4 + 10; 4 string data; 5 int main() 6 { 7     cin >> data; 8     int m;int x , y , k; 9     scanf("%d" , &m);10     while(m--)11     {12         scanf("%d%d%d" , &x , &y , &k);13         int len = y - x + 1;14         k %= len;15         --x , --y;16         string ls = data.substr(x , len - k);17         string rs = data.substr(y - k + 1 , k);18         data = http://www.mamicode.com/data.substr(0 , x) + rs + ls + data.substr(y + 1);19     }20     cout << data;21 }

View Code

C. Nearest vectors(计算几何)

You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.

Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.

Input

First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.

The i-th of the following n lines contains two integers x**i and y**i (|x|, |y| ≤ 10 000, x2 + y2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).

Output

Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.

Examples

input

4-1 00 -11 01 1

output

3 4

input

6-1 00 -11 01 1-4 -5-4 -6

output

6 5

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long double LD; 4 static const int MAXN = 1e5 + 10; 5 static const int OO = 0x3fffffff; 6 static const LD EPS = 1e-9; 7 static const double PI = acos(-1.0); 8 struct Node 9 {10     LD x;11     int id;12 }data[MAXN];13 int main()14 {15     int n;16     scanf("%d" , &n);17     int x , y;18     for(int i = 1 ; i <= n ; ++i)19     {20         scanf("%d%d" , &x , &y);21         data[i].x = atan2(y , x);22         data[i].id = i;23     }24 25     sort(data + 1 , data + 1 + n , [](Node a , Node b){return a.x < b.x;});26     LD ans = OO;27     data[n + 1] = data[1];28     data[n + 1].x += 2 * PI;29     int id = 0;30     for(int i = 1 ; i <= n ; ++i)31     {32         LD now = data[i + 1].x - data[i].x;33         if(ans > now)34         {35             ans = now;36             id = i;37         }38     }39 40     printf("%d %d" , data[id].id , data[id + 1].id);41 }

View Code

D. Igor In the Museum(染色问题、离线处理)

Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of n × m cells. Each cell is either empty or impassable. Empty cells are marked with ‘.‘, impassable cells are marked with ‘*‘. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.

Input

First line of the input contains three integers n, m and k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — the museum dimensions and the number of starting positions to process.

Each of the next n lines contains m symbols ‘.‘, ‘*‘ — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can‘t go out from the museum.

Each of the last k lines contains two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — the row and the column of one of Igor‘s starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.

Output

Print k integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.

Examples

input

5 6 3*******..*.********....*******2 22 54 3

output

6410

input

4 4 1*****..**.******3 2

output

8

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 1e3 + 10; 4 static const int dirx[5] = {0 , 1 , 0 , -1}; 5 static const int diry[5] = {1 , 0 , -1 , 0}; 6 int num[MAXN * MAXN]; 7 int vis[MAXN][MAXN]; 8 char data[MAXN][MAXN]; 9 int n , m , k;10 int color;11 int sum;12 void Dfs(int x , int y)13 {14     vis[x][y] = color;15     for(int i = 0 ; i < 4 ; ++i)16     {17         int nx = x + dirx[i] , ny = y + diry[i];18         if(nx < 1 || ny < 1 || nx > n || ny > m || vis[nx][ny] || data[nx][ny] == ‘*‘)19         {20             if(data[nx][ny] == ‘*‘)21                 ++sum;22             continue;23         }24         Dfs(nx , ny);25     }26 }27 int main()28 {29 30     scanf("%d%d%d" , &n , &m , &k);31     for(int i = 1 ; i <= n ; ++i)32     {33         for(int j = 1 ; j <= m ; ++j)34         {35             scanf(" %c" , &data[i][j]);36         }37     }38 39     for(int i = 1 ; i <= n ; ++i)40     {41         for(int j = 1 ; j <= m ; ++j)42         {43             if(data[i][j] == ‘.‘ && !vis[i][j])44             {45                 ++color;46                 sum = 0;47                 Dfs(i , j);48                 num[color] = sum;49             }50         }51     }52 53     while(k--)54     {55         int x , y;56         scanf("%d%d" , &x , &y);57         printf("%d\n" , num[vis[x][y]]);58 59     }60 }

View Code

2017-5-10-Train:Educational Codeforces Round 1