#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i ++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.back() == 0 && C.size() > 1)
        C.pop_back();
    return C;
}
vector<int> sub(vector<int> &A, vector<int> &B) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++) {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.back() == 0 && C.size() > 1)
        C.pop_back();
    return C;
}
bool cmp(vector<int> &A, vector<int> &B) {
    if (A.size() != B.size())
        return A.size() > B.size();
    for (int i = 0; i < A.size(); i ++)
        if (A[i] != B[i]) return A[i] > B[i];
    return true;
}
int n;
int main() {
    while (cin >> n, n) {
        int a1 = 1, ans1 = 1;
        vector<int> ans = {0};
        while (n --) {
            string a;
            vector<int> A;
            cin >> a;
            if (a[0] == '-') {
                a1 = 0;
                for (int i = a.size() - 1; i > 0; i --)
                    A.push_back(a[i] - '0');
            } else {
                for (int i = a.size() - 1; i >= 0; i --)
                    A.push_back(a[i] - '0');
                a1 = 1;
            }
            if (cmp(ans, A)) {
                if (ans1 && a1) ans = add(ans, A), ans1 = 1;
                else if (ans1 && !a1) ans = sub(ans, A), ans1 = 1;
                else if (!ans1 && !a1) ans = add(ans, A), ans1 = 0;
                else ans = sub(ans, A), ans1 = 0;
            } else {
                if (ans1 && a1) ans = add(ans, A), ans1 = 1;
                else if (ans1 && !a1) ans = sub(A, ans), ans1 = 0;
                else if (!ans1 && !a1) ans = add(ans, A), ans1 = 0;
                else ans = sub(A, ans), ans1 = 1;
            }
        }
        if (!ans1 && ans[0]) cout << '-';
        for (int i = ans.size() - 1; i >= 0; i --)
            cout << ans[i];
        cout << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
int f;
int a, b;
int gcd(int a, int b) {
    if (a % b == 0) return b;
    else {
//         if (f) cout << ' ';
        printf(" gcd(%d,%d)", b, a % b);
        return gcd(b, a % b);
    }
}
int main() {
    cin >> a >> b;
    printf("gcd(%d,%d)", a, b);
    int res = gcd(a, b);
    cout << ' ' << res;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, arr[N], x, cnt;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> arr[i];
    cin >> x;
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (arr[mid] > x) r = mid - 1,cnt ++;
        else if (arr[mid] < x) l = mid + 1, cnt ++;
        else {
            cnt ++;
            cout << mid << endl << cnt << endl;
            return 0;
        }
    }
    cout << -1 << endl << cnt << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int path[N], n;
void dfs(int u) {
    if (u == n) {
        for (int i = 1; i <= n; i ++)
            cout << path[i] << ' ';
        cout <<endl;
        return ;
    }
    for (int i = u; i <= n; i ++) {
        swap(path[i], path[u]);
        dfs(u + 1);
        swap(path[u], path[i]);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        path[i] = i;
    dfs(1);
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
// 结论需要推
struct Mx {
    LL g[3][3];
    Mx() {
        memset(g, 0, sizeof g);
    }
};
// 矩阵乘法 3 重循环
Mx mul(Mx a, Mx b) {
    Mx res;
    for (int i = 0; i < 3; i ++)
        for (int j = 0; j < 3; j ++) {
            LL sum = 0;
            for (int k = 0; k < 3; k ++)
                sum = (sum + a.g[i][k] * b.g[k][j]) % mod;
            res.g[i][j] = sum;
        }
    return res;
}
// 矩阵快速幂
Mx Mx_pow(Mx a, LL b) {
    Mx res;
    // 构造单位矩阵
    res.g[0][0] = res.g[1][1] = res.g[2][2] = 1;
    while (b) {
        if (b & 1) res = mul(res, a); // b & 1 判断 b 的末尾是否为 0
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}
LL n;
Mx a;
int main() {
    cin >> n;
    // 目标矩阵
    a.g[0][0] = a.g[1][0] = a.g[2][1] = 1;
    a.g[0][1] = 2;
    a.g[0][2] = 3;
    a = Mx_pow(a, n - 3);
    LL ans[3][1], num[3][1];
    num[0][0] = 3, num[1][0] = 2, num[2][0] = 1;
    for (int i = 0; i < 3; i ++) {
        LL sum = 0;
        for (int j = 0; j < 3; j ++)
            sum = (sum + a.g[i][j] * num[j][0]) % mod;
        ans[i][0] = sum;
    }
    cout << ans[0][0] << endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, x, t;
int main() {
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; i ++) {
        cin >> t;
        if (t >= x) {
            cout << i + 1;
            return 0;
        }
    }
    cout << n + 1 << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    vector<int>ans;
    int x;
    while (cin >> x) ans.push_back(x);
    sort(ans.begin(), ans.end());
    cout << ans[0] << ',' << ans[ans.size() - 1];
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    sort(a, a + n);
    cout << a[m - 1] << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i ++)
        scanf("%d", &a[i]);
    sort(a, a + n);
    cout << a[n - m] << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int maxv;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];
    for (int i = n; i >= 0; i --) {
        for (int j = 1; j <= m; j ++) {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) {
                f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
                maxv = f[i][j];
            }
        }
    }
    int j = m, t = 0;
    for (int i = 1; i <= n; i ++)
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ', t = 1;
            j -= v[i];
        }
    if (!t) cout << "No" << endl << 0 << endl;
    else cout << endl << maxv << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int idx, sum;
int w[N], op[N];
void dfs(int idx, int sum) {
    if (idx > n || sum > m) return ;
    else if (sum == m) {
        for (int i = 0; i < n; i ++)
            if (op[i])
                cout << w[i] << ' ';
        cout << endl;
        return ;
    } else {
        op[idx] = 1;
        dfs(idx + 1, sum + w[idx]);
        op[idx] = 0;
        dfs(idx + 1, sum);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        cin >> w[i];
    dfs(0, 0);
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, arr[N], cnt;
int st[N];
void dfs(int a[], int n, int i, int st[]) {
    if (i >= n) cnt ++;
    else {
        st[i] = 1;
        dfs(a, n, i + 1, st);
        st[i] = 0;
        dfs(a, n, i + 1, st);
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> arr[i];
    dfs(arr, n, 0, st);
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
struct activity {
    int b, e, no;
    bool operator < (activity & t) {
        if (e != t.e) return e < t.e;
        else return b < t.b;
    }
}a[1010];
int n, x ,y;
// bool cmp (activity x, activity y) {
//     if (x.b != x.b) return x.b < y.b;
//     else return x.e < y.e;
// }
int main() {
    while (cin >> n, n != 0) {
        int cnt = 0, pre = 0;
        for (int i = 0; i < n; i ++) {
            cin >> a[i].b >> a[i].e;
    //         cout << a[i].b << ' ' << a[i].e << endl;
        }
        sort(a, a + n);
        for (int i = 0; i < n; i ++) {
//             cout << a[i].b << ' ' << a[i].e << endl;
            if (a[i].b >= pre) {
                pre = a[i].e;
//                 cout << a[i].b << ' ' << a[i].e << endl;
                cnt ++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    char e;
    int a = 0, b = 0, c = 0, d = 0;
    while ((e = getchar()) != '\n') {
        if (e == 'A') a ++;
        else if(e == 'B') b ++;
        else if (e == 'C') c ++;
        else if (e == 'D') d ++;
    }
    printf("Competition department %d people!\n", a);
    printf("Propaganda Department %d people!\n", b);
    printf("Office %d people!\n", c);
    printf("Organization Department %d people!\n", d);
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
struct activity {
    int b, e, no;
//     bool operator < (activity & t) {
//         if (e != t.e) return e < t.e;
//     }
}a[1010];
int n, x ,y;
bool cmp (activity x, activity y) {
    return x.e < y.e;
//     if (x.e != y.e) return x.e < y.e;
//     else return x.b < y.b;
}
int main() {
   cin >> n;
    int cnt = 0, pre = 0, score = 0;
    for (int i = 0; i < n; i ++) {
        cin >> a[i].b >> a[i].e >> a[i].no;
//         cout << a[i].b << ' ' << a[i].e << endl;
    }
    sort(a, a + n, cmp);
    for (int i = 0; i < n; i ++) {
//         cout << a[i].b << ' ' << a[i].e << endl;
        if (a[i].b >= pre) {
            pre = a[i].e;
//             cout << a[i].b << ' ' << a[i].e << endl;
            cnt ++;
            score += a[i].no;
        }
    }
    cout << cnt << ' ' << score << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1010;
int n, max_x = -1;
int a[N], b[N];
int main() {
    cin >> n;
    for (int i = 1; i<= n; i ++)
        cin >> a[i], b[i] = 100;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            if (a[i] <= b[j]) {
                b[j] -= a[i];
                cout << a[i] << ' ' << j << endl;
                max_x = max(max_x, j);
                    break;
            }
        }
    }
    cout << max_x << endl;
    return 0;
}