using namespace std;
bool is_upper(char c) { return 'A' <= c and c <= 'Z'; }
string lower(string s)
{
    string ans = s;
    for (int i = 0, len = s.size(); i < len; ++i)
        if (is_upper(s[i]))
            ans[i] += ('a' - 'A');
    return ans;
}
int main(void)
{
    string s1, s2;
    cin >> s1 >> s2;
    s1 = lower(s1);
    s2 = lower(s2);
    cout << (s1 == s2 ? 0 : (s1 > s2 ? 1 : -1)) << endl;
    return 0;
}

using namespace std;
using ll = long long;
ll n, k, A, B;
ll a[100010];
ll binary_search(ll low, ll high, ll target)
{
    auto p = [&](ll x) { return a[x] >= target; };
    while (low < high)
    {
        ll mid = low + (high - low) / 2;
        if (p(mid))
            high = mid;
        else
            low = mid + 1;
    }
    if (not p(low))
        return high + 1;
    return low;
}
ll divide_and_conquer(ll l, ll r)
{
    ll tl = binary_search(0, k - 1, l);
    ll tr = binary_search(0, k - 1, r + 1) - 1;
    if (tr < tl)
        return A;
    else
    {
        if ((r - l) == 0)
            return B * (tr - tl + 1) * 1;
        else
        {
            ll m = l + (r - l) / 2;
            return min(divide_and_conquer(l, m) + divide_and_conquer(m + 1, r),
                       B * (tr - tl + 1) * (r - l + 1));
        }
    }
}
ll solve(void)
{
    sort(a, a + k);
    return divide_and_conquer(0, (int)pow(2, n) - 1);
}
int main(void)
{
    ll ai;
    cin >> n >> k >> A >> B;
    for (int i = 0; i < k; ++i)
    {
        cin >> ai;
        a[i] = ai - 1;
    }
    cout << solve() << endl;
    return 0;
}

using namespace std;
using ss = stringstream;
int initial[8];
int board[8];
bool valid(int nrow, int ncol)
{
    for (int col = 0; col < ncol; ++col)
    {
        if (board[col] == nrow)
            return false;
        if ((ncol - col) == (int)abs(nrow - board[col]))
            return false;
    }
    return true;
}
int current_score(void)
{
    int score = 0;
    for (int col = 0; col < 8; ++col)
        score += (board[col] - initial[col]) != 0;
    return score;
}
int backtrack(int col)
{
    int ans = INT_MAX;
    for (int row = 0; row < 8; ++row)
    {
        if (valid(row, col))
        {
            int last = board[col];
            board[col] = row;
            if (col < 7)
                ans = min(ans, backtrack(col + 1));
            else
                ans = min(ans, current_score());
            board[col] = last;
        }
    }
    return ans;
}
int main(void)
{
    string line;
    int t = 0;
    while (getline(cin, line) and line != "")
    {
        ++t;
        int row;
        ss rows(line);
        for (int i = 0; i < 8; ++i)
        {
            rows >> row;
            board[i] = initial[i] = row - 1;
        }
        cout << "Case " << t << ": " << backtrack(0) << endl;
        line = "";
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int l, m;
        vi left, right;
        cin >> l >> m;
        l *= 100;
        while (m--)
        {
            int len;
            string side;
            cin >> len >> side;
            if (side[0] == 'l')
                left.push_back(len);
            else
                right.push_back(len);
        }
        int lans = 0, rans = 0, cur_acc = 0;
        for (auto len : left)
        {
            if (cur_acc + len >= l)
            {
                lans++;
                cur_acc = len;
            }
            else
                cur_acc += len;
        }
        if (cur_acc > 0)
            ++lans;
        cur_acc = 0;
        for (auto len : right)
        {
            if (cur_acc + len >= l)
            {
                rans++;
                cur_acc = len;
            }
            else
                cur_acc += len;
        }
        if (cur_acc > 0)
            ++rans;
        cout << 2 * max(lans, rans) - (lans > rans ? 1 : 0) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using ii = array<ll, 2>;
const ll NMAX = 5e3 + 11;
ll x[NMAX];
ii mem[NMAX][NMAX];
bool vis[NMAX][NMAX];
ii dp(ll l, ll r, bool player)
{
    ii &ans = mem[l][r];
    ll lval = x[l];
    ll rval = x[r];
    if (r - l + 1 == 2)
    {
        ans[player] = max({lval, rval});
        ans[!player] = min({lval, rval});
        return ans;
    }
    if (vis[l][r])
        return ans;
    vis[l][r] = true;
    ii lans = dp(l + 1, r, !player);
    ii rans = dp(l, r - 1, !player);
    lans[player] += lval;
    rans[player] += rval;
    ans = lans[player] > rans[player] ? lans : rans;
    return ans;
}
int main(void)
{
    ll n;
    cin >> n;
    for (ll i = 0; i < n; ++i)
        cin >> x[i];
    cout << dp(0, n - 1, true)[true] << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const MOD = 1e9 + 7;
ll modpow(ll a, ll b)
{
    a %= MOD;
    ll ans = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        cout << modpow(a, b) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 2e5 + 11;
int a[NMAX];
int main(void)
{
    int n;
    ll ans = 0;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i)
    {
        ans += max(0, a[i - 1] - a[i]);
        a[i] = max(a[i - 1], a[i]);
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll MOD = 1e9 + 7;
ll solve(ll n)
{
    ll target;
    target = (n * (n + 1)) / 2;
    if (target % 2 != 0)
        return 0;
    target /= 2;
    vvll dp(n + 1, vll(target + 1, 0));
    dp[0][0] = 1;
    for (ll x = 1; x <= n; ++x)
    {
        for (ll sum = 1; sum <= target; ++sum)
        {
            ll &ans = dp[x][sum];
            ans = dp[x - 1][sum];
            if (sum - x >= 0)
                ans = (ans + dp[x - 1][sum - x] % MOD) % MOD;
        }
    }
    return dp[n][target];
}
int main(void)
{
    ll n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e6 + 11;
bool taken[NMAX];
int ntaken;
bool possible(int n, ll sum)
{
    if (sum % 2 == 1)
        return false;
    sum /= 2;
    for (int i = n; i >= 1 and sum > 0; --i)
    {
        if (sum - i >= 0)
        {
            ++ntaken;
            taken[i] = true;
            sum -= i;
        }
    }
    return true;
}
int main(void)
{
    int n;
    ll sum = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        sum += i;
    if (possible(n, sum))
    {
        cout << "YES" << endl;
        cout << ntaken << endl;
        for (int i = 1; i <= n; ++i)
            if (taken[i])
                cout << i << " ";
        cout << endl;
        cout << n - ntaken << endl;
        for (int i = 1; i <= n; ++i)
            if (not taken[i])
                cout << i << " ";
    }
    else
        cout << "NO" << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
int main(void)
{
    int n, m;
    cin >> n >> m;
    set<ii> h;
    for (int i = 0; i < n; ++i)
    {
        int hi;
        cin >> hi;
        h.emplace(hi, i);
    }
    for (int i = 0; i < m; ++i)
    {
        int ti;
        cin >> ti;
        auto it = h.upper_bound({ti, 1e9});
        if (it != h.begin())
        {
            --it;
            cout << it->first << endl;
            h.erase(it);
        }
        else
            cout << -1 << endl;
    }
    return 0;
}