Problems
Handbook - Problem example

In this article, we present a more advanced example with full details to give you a better overall impression of Sphere Engine Problems service capabilities. It is still an elementary example but illustrates much more about the specifics of Online Judge systems.

The problem is to count the sum of numbers from 1 to given n i.e., 1 + 2 + 3 + ... + n, which we call the Initial sum problem. We are going to prepare it to deal with multiple pairs of input/output data in a single test case by proper input/output specification design.

Consider the following problem description:

For a positive integer n calculate the value of the sum of all positive integers that are not greater than n i.e., 1 + 2 + 3 + ... + n. For instance, when n = 5 the correct answer is 15.

Input specification

In the first line is the number 1 ≤ T ≤ 10000000 which is the number of instances for your problem. In each of the next T lines, there will be one number n for which you should calculate the defined initial sum.

Output specification

For each n print the calculated initial sum. Separate answers with the newline character.

Examples

Input
4
1
2
3
4

Output
1
3
6
10

Before we design test cases let us present two different solutions to the problem:

long long initsum(long long n)
{
    int i;
    long long sum = 0;
    for (i=1; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

int main()
{
    int t;
    long long n;
    scanf("%d", &t);
    while (t > 0)
    {
        scanf("%lld", &n);
        printf("%lld\n", initsum(n));
        t--;
    }
    return 0;
}

The first solution is implemented to calculate the sum according to the definition of the problem, i.e., the function initsum iterates from 1 to n to calculate the desired value. The calculation requires n operations of addition to obtain the result.

We can apply a different approach to obtain the same results. There is a compact formula that allows for fast calculations:

long long initsum(long long n)
{
    return n*(n+1)/2;
}

int main()
{
    int t;
    long long n;
    scanf("%d", &t);
    while (t > 0)
    {
        scanf("%lld", &n);
        printf("%lld\n", initsum(n));
        t--;
    }
    return 0;
}

Both programs are correct answers to the Initial Sum problem but the second one requires considerably fewer operations to calculate the result. We can design test cases to distinguish between these solutions, i.e., we can create a test case that only the second solution is able to pass.

Our suggestion is to design one test case for both algorithms that is easy to pass, to provide information that the solution is correct. We also suggest designing a second test case that only the second algorithm can pass.

It is also good practice to design a single test case to be the same as an example from the problem description. In this way, the user can verify that they handle input and output data correctly.

We cannot put all input and output data here because of its large size. We therefore share a shorter version:

Test case	Input file	Output file
1 (example data)	4 1 2 3 4	1 3 6 10
2	1000 1 2 ... 1000	1 3 ... 500500
3	999000 1001 1002 ... 1000000	501501 502503 ... 500000500000

The user submitting a solution similar to the first example receives information that it successfully passes two first test cases (the low difficulty and example test cases). However, it doesn't pass the third test case because of the exceeded time limit.

The computational power of modern era computers is enough to finish the first test case instantly. Both presented algorithms finish computations with a time below 0.01s. However, it is a good test case to verify correctness concerning returned values.

Verification that covers the first 1,000 positive integers provides assurance that the solution is mathematically correct. On the other hand, the third test case is rich enough to make the first example solution exceed even 5s time limit.

The second algorithm works fast enough to pass the third test case in a time below 0.1s. There is a huge gap between 0.1s and 5s so we can easily choose a safe value for the time limit, for example, 1s.

We still haven't chosen judges for test cases and a master judge for the problem. The Ignore extra white spaces test case judge is a good choice for defined test cases. It leaves users with the possibility of small formatting errors and without the risk of unwanted rejections of their solutions. For instance, it is possible to replace newline characters with spaces in output formatting and still pass the test case.

We assume that we want to accept every correct solution but distinguish the better ones and give them a superior score. The master judge called Score is the % of correctly solved sets is a suitable choice for this purpose. Submitting the first example solution returns a result of 66% (i.e., the first and the second test cases are solved correctly but the third isn't solved in time) while the second presented solution passes all three test cases to obtain a final score equal to 100%.

To sum up we present the full problem specification:

Description

The task

For a positive integer n calculate the value of the sum of all positive integers that are not greater than n i.e., 1 + 2 + 3 + ... + n. For instance, when n = 5, the correct answer is 15.

Input specification

In the first line is the number 1 ≤ T ≤ 10000000, which is the number of instances for our problem. In each of the next T lines, there will be one number n for which we should calculate the defined initial sum.

Output specification

For each n print the calculated initial sum. Separate answers with the newline character.

Examples

Input
4
1
2
3
4

Output
1
3
6
10

Test cases

Test case	Input file	Output file	Judge	Time limit
1 (example data)	4 1 2 3 4	1 3 6 10	Ignoring extra whitespaces	1s
2	1000 1 2 ... 1000	1 3 ... 500500	Ignoring extra whitespaces	1s
3	999000 1001 1002 ... 1000000	501501 502503 ... 500000500000	Ignoring extra whitespaces	1s

Master judge

Score is % of correctly solved sets