Polly the Polynomial

Algebra! Remember algebra? There is a theory that as engineers progresses further and further in their studies, they lose basic math skills. This problem is designed to help you remember those basic algebra skills, make the world a better place, etc., etc.

Input

Your program should accept an even number of lines of text. Each pair of lines will represent one problem. The first line will contain a list of integers { } which represent a set of coefficients to a polynomial expression. The order of the polynomial is n. The coefficients should be paired with the terms of the polynomial in the following manner:

The second line of text represents a sequence of values for x, { }.

Output

For each pair of lines, your program should evaluate the polynomial for all the values of x ( through ) and output the resulting values on a single line.

Sample Input

-2
5 0 1 6
1 -1
7 6 -1

Sample Output

-2 -2 -2 -2
6 5 -2

---

#include <stdio.h>
int parseLine(char *str, int a[]) {
    int i, neg = 1, g = 0, tmp = 0, idx = 0;
    for(i = 0; str[i]; i++) {
        if(str[i] >= '0' && str[i] <= '9')
            tmp = tmp*10 + str[i]-'0', g = 1;
        else {
            if(str[i] == '-') {
                neg = -1;
            } else if(str[i] == '+') {
                neg = 1;
            } else if(g) {
                a[idx++] = tmp*neg;
                g = 0, tmp = 0, neg = 1;
            }
        }
    }
    if(g)
        a[idx++] = tmp*neg;
    return idx;
}
int pow(int x, int y) {
    if(y == 0)
        return 1;
    if(y&1)
        return pow(x*x, y>>1)*x;
    else
        return pow(x*x, y>>1);
}
int main() {
    char line[500];
    int c[500], x[500];
    while(gets(line)) {
        int ct, xt;
        ct = parseLine(line, c);
        gets(line);
        xt = parseLine(line, x);
        int sum, i, j;
        for(i = 0; i < xt; i++) {
            sum = 0;
            for(j = 0; j < ct; j++)
                sum += pow(x[i], ct-j-1)*c[j];
            if(i)
                putchar(' ');
            printf("%d", sum);
        }
        puts("");
    }
    return 0;
}