PrincetonPLI/LongProc huggingface dataset:
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
declare new long long variable mod with value 1e9+9
new array of characters s with size 500005
long long function power with long long arguments a and b
    create long long variable ret = 1
    change a to a modulo mod
    while b is not 0
        if b & 1 is not 0, change ret to ret * a % mod
        change a to a squared modulo mod
        set b to b >> 1
    end of the block
    return ret
end of the block
define the main function
    declare long long variables n, a, b and k
    read n, a, b and k from the user input
    read input an store it into s
    read input into s
    declare new long long called t with value (n + 1) / k
    declare new long long u = power(b, k) * power(power(a, k), mod - 2) % mod
    assign (power(u, t) + mod - 1) % mod * power(u - 1 + mod, mod - 2) % mod to t
    if u = 1, assign (n + 1) / k to t
    declare long long variable with name ans with value 0
    for i = 0 to k exclusive incrementing i
        declare long long variable tmp
        assign the new value = power(a, n - i) * power(b, i) % mod
        assign tmp * t % mod to tmp
        if s[i] = '+'
            change the value of ans to (ans + tmp) % mod
        else
            change ans to ans - tmp + mod
            change the value of ans to ans modulo mod
        end of the block
    end of the block
    print ans
    return to indicate successful execution
end of the block

[CODE]:

long long mod = 1e9 + 9;
char s[500005];
long long power(long long a, long long b) {
    long long ret = 1;
    a %= mod;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
int main() {
    long long n, a, b, k;
    cin >> n >> a >> b >> k;
    gets(s);
    gets(s);
    long long t = (n + 1) / k;
    long long u = power(b, k) * power(power(a, k), mod - 2) % mod;
    t = (power(u, t) + mod - 1) % mod * power(u - 1 + mod, mod - 2) % mod;
    if (u == 1) t = (n + 1) / k;
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        long long tmp;
        tmp = power(a, n - i) * power(b, i) % mod;
        tmp = tmp * t % mod;
        if (s[i] == '+') {
            ans = (ans + tmp) % mod;
        } else {
            ans = ans - tmp + mod;
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
f = int array of size 1000
in function find taking int x and returning int
    if f[x] is x
        return x
    else
        return find of f[x]
end of the block
in function unionn taking int a, int b
    x = int with x = find of a
    y = int with y = find of b
    if x is not y set f[x] to y
end of the block
define the main function
    t = int
    n, m, k, x, y = int
    s, num = int array of size 1000 each
    loop while reading n then m then k
        set all values of num to 0
        for i = 1 to n inclusive set f[i] to i
        for i = 1 to k inclusive read s[i]
        for i = 0 to m
            read x then y
            call unionn of x, y
        end of the block
        for i = 1 to n inclusive increment num[find of i]
        Max, sum, ss = int with Max = 0 and sum = 0 and ss = n
        for i = 1 to k inclusive
            set num[s[i]] to num[find of s[i]]
            set Max to max of Max, num[s[i]]
            decrement ss by num[s[i]]
            increment sum by (num[s[i]]) * (num[s[i]] - 1) / 2
        end of the block
        increment sum by (ss + Max) * (ss + Max - 1) / 2
        decrement sum by Max * (Max - 1) / 2 + m
        print sum
    end of the block
    return to indicate successful execution
end of the block

[CODE]:

int f[1000];
int find(int x) {
    if (f[x] == x)
        return x;
    else
        return find(f[x]);
}
void unionn(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x != y) f[x] = y;
}
int main() {
    int t;
    int n, m, k, x, y;
    int s[1000], num[1000];
    while (cin >> n >> m >> k) {
        memset(num, 0, sizeof(num));
        for (int i = 1; i <= n; i++) f[i] = i;
        for (int i = 1; i <= k; i++) cin >> s[i];
        for (int i = 0; i < m; i++) {
            cin >> x >> y;
            unionn(x, y);
        }
        for (int i = 1; i <= n; i++) num[find(i)]++;
        int Max = 0, sum = 0, ss = n;
        for (int i = 1; i <= k; i++) {
            num[s[i]] = num[find(s[i])];
            Max = max(Max, num[s[i]]);
            ss -= num[s[i]];
            sum += (num[s[i]]) * (num[s[i]] - 1) / 2;
        }
        sum += (ss + Max) * (ss + Max - 1) / 2;
        sum -= Max * (Max - 1) / 2 + m;
        cout << sum << endl;
    }
    return 0;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
p, n, k, s = integer with p = 1, s = array of size 105
c = character
define the main function
    s[increment k] = 1
    while (read c and c is not =
        if c is +, increment p, s[increment k] = 1
        if c is -, decrement p, s[increment k] = -1
    end of the block
    read n
    for i = 0 to k exclusive
        if s[i] > 0
            while p < n and s[i] < n, increment s[i], increment p
        else
            while p > n and s[i] > -n, decrement s[i], decrement p
    end of the block
    if p is not n
        print Impossible
        return to indicate successful execution
    end of the block
    print Possible
    for i = 0 to k exclusive, (if i, (if s[i] < 0, print - else print +) else ), and print absolute of s[i]
    print = and n
end of the block

[CODE]:

int p = 1, n, k, s[105];
char c;
int main() {
    s[k++] = 1;
    while (cin >> c && c != '=') {
        if (c == '+') p++, s[k++] = 1;
        if (c == '-') p--, s[k++] = -1;
    }
    cin >> n;
    for (int i = 0; i < k; i++) {
        if (s[i] > 0)
            while (p < n && s[i] < n) s[i]++, p++;
        else
            while (p > n && s[i] > -n) s[i]--, p--;
    }
    if (p != n) {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    for (int i = 0; i < k; i++) cout << (i ? (s[i] < 0 ? "- " : "+ ") : "") << abs(s[i]) << " ";
    cout << "= " << n << endl;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
let fx, fy, dx, dy ints, all with value 0
define the main function
    read fx and fy
    let c a string
    read c
    if fx and fy are 0, print Yes and return 0
    for i = 0 to length of c exclusive
        if c[i] is u
            increment dy
        otherwise if c[i] is D
            decrement dy
        otherwise, if c[i] is L
            decrement dx
        otherwise
            increment dx
    end of the block
    for i = 0 to size of c exclusive
        let nx, ny ints with value 0
        for j = 0 to i inclusive
            if c[j] is U
                increment ny
            otherwise if c[j] is D
                decrement ny
            otherwise if c[j] is L
                decrement nx
            otherwise
                increment nx
        end of the block
        if nx equals fx and ny equals fy, print Yes and return 0
        let k1 and k2 be integers with value 0
        if dx is not 0, set k1 to (fx - nx) / dx
        if dy is not 0, set k2 = (fy - ny) / dy
        if dx is 0, set k1 equals k2
        if dy is 0, set k2 equals k1
        if k1 * dx + nx = fx and k2 * dy + ny = fy and k1 nonnegative, print Yes and return 0
    end of the block
    print No and return 0
end of the block

[CODE]:

int fx = 0, fy = 0, dx = 0, dy = 0;
int main() {
    cin >> fx >> fy;
    string c;
    cin >> c;
    if (fx == 0 && fy == 0) return cout << "Yes" << endl, 0;
    for (int i = 0; i < c.size(); i++) {
        if (c[i] == 'U')
            dy++;
        else if (c[i] == 'D')
            dy--;
        else if (c[i] == 'L')
            dx--;
        else
            dx++;
    }
    for (int i = 0; i < c.size(); i++) {
        int nx = 0, ny = 0;
        for (int j = 0; j <= i; j++) {
            if (c[j] == 'U')
                ny++;
            else if (c[j] == 'D')
                ny--;
            else if (c[j] == 'L')
                nx--;
            else
                nx++;
        }
        if (nx == fx && ny == fy) return cout << "Yes" << endl, 0;
        int k1 = 0, k2 = 0;
        if (dx != 0) k1 = (fx - nx) / dx;
        if (dy != 0) k2 = (fy - ny) / dy;
        if (dx == 0) k1 = k2;
        if (dy == 0) k2 = k1;
        if (k1 * dx + nx == fx && k2 * dy + ny == fy && k1 == k2 && k1 >= 0) return cout << "Yes" << endl, 0;
    }
    return cout << "No" << endl, 0;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
make constant ints N = 5e5 and inf = 1e9
create map m of chars to ints
create int n and int arrays tmp of size N, x of size N, and y of size N
declare Ok taking in int cur and returning bool
    for i = 0 to n exclusive
        set tmp[i] to 0
        set tmp[i] to tmp[i] | (1 << (x[i] - 1)) & cur
        set tmp[i] to tmp[i] | (1 << (y[i] - 1 + 5)) & cur
        for j = 0 to i exclusive
            if tmp[i] is equal to tmp[j] and if x[i] is not equal to x[j] or y[i] is not equal to y[j], return false
        end of the block
    end of the block
    return true
end of the block
define the main function
    set M['R'] to 1, M['G'] to 2, M['B'] to 3, M['Y'] to 4, and M['W'] to 5
    read n
    for i = 0 to n exclusive
        make string s
        read s
        set x[i] to M[s[0]]
        set y[i] to s[1] - '0'
    end of the block
    create integer res = 10
    for i = 0 to (1 << 10) exclusive
        make integer cur = _builtin_popcount(i)
        if cur is greater than or equal to res, continue loop
        if Ok(i) is truthy, set res to cur
    end of the block
    print res
    return to indicate successful execution
end of the block

[CODE]:

const int N = 5e5, inf = 1e9 + 7;
map<char, int> M;
int tmp[N], x[N], y[N], n;
bool Ok(int cur) {
    for (int i = 0; i < n; i++) {
        tmp[i] = 0;
        tmp[i] |= (1 << (x[i] - 1)) & cur;
        tmp[i] |= (1 << (y[i] - 1 + 5)) & cur;
        for (int j = 0; j < i; j++) {
            if (tmp[i] == tmp[j] && (x[i] != x[j] || y[i] != y[j])) return false;
        }
    }
    return true;
}
int main() {
    M['R'] = 1, M['G'] = 2, M['B'] = 3, M['Y'] = 4, M['W'] = 5;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        x[i] = M[s[0]];
        y[i] = s[1] - '0';
    }
    int res = 10;
    for (int i = 0; i < (1 << 10); i++) {
        int cur = __builtin_popcount(i);
        if (cur >= res) continue;
        if (Ok(i)) res = cur;
    }
    cout << res << "\n";
    return 0;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
create integer n, array a with size 105
create map mp of char to int
define the main function
    read n
    set mp['R'] to 5
    set mp['G'] to 6
    set mp['B'] to 7
    set mp['Y'] to 8
    set mp['W'] to 9
    for i = 0 to n exclusive
        create stirng s
        read s
        create ints c, v
        set c to mp[s[0]]
        set v to s[1] - '0' - 1
        set a[i] to (1 bitwise shift left c) bitwise or (1 bitwise shift left v)
    end of the block
    sort a [0:n)
    set n to unique(a, a + n) - a
    create integer ans = 11
    for int mask = 0; msk less than (1 bitwise shift left 10); increment msk
        create bool f = true
        for i = 0 to n exclusive
            for j = i + 1 to n exclusive
                create int t = a[i] bitwise XOR a[j]
                if (msk bitwise and t) equals 0
                    set f to false
                    break
                end of the block
            end of the block
            if not f, break
        end of the block
        if f, set ans to min(ans, __builtin_popcount(msk))
    end of the block
    print ans
    return to indicate successful execution
end of the block

[CODE]:

int n, a[105];
map<char, int> mp;
int main() {
    cin >> n;
    mp['R'] = 5;
    mp['G'] = 6;
    mp['B'] = 7;
    mp['Y'] = 8;
    mp['W'] = 9;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int c, v;
        c = mp[s[0]];
        v = s[1] - '0' - 1;
        a[i] = (1 << c) | (1 << v);
    }
    sort(a, a + n);
    n = unique(a, a + n) - a;
    int ans = 11;
    for (int msk = 0; msk < (1 << 10); msk++) {
        bool f = true;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int t = a[i] ^ a[j];
                if ((msk & t) == 0) {
                    f = false;
                    break;
                }
            }
            if (!f) break;
        }
        if (f) { ans = min(ans, __builtin_popcount(msk)); }
    }
    cout << ans << endl;
    return 0;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
Mod = const int with Mod = 1e9 + 7
n, p = integers
choose, ans = long long with choose = 2d array of 30025 rows and 600 columns, ans = 1
Pedy = map from int to int
define the main function
    read n
    index 0, 0 of choose = 1
    for i = 1 to 30024
        index i and 0 of choose = 1
        for j = 1 to n index i and j of choose = (choose[i - 1][j - 1] + choose[i - 1][j]) modulo Mod
    end of the block
    for i = 0 to n exclusive
        read p
        for j = 2 to j * j <= p
            if p modulo j is 0
                while not(p modulo j)
                    p = p / j
                    increment Pedy[j]
                end of the block
            end of the block
        if p > 1, increment Pedy[p]
    end of the block
    for it = Pedy.begin() to it is not Pedy.end()
        p = second in it
        ans = (ans * choose[p + n - 1][n - 1]) modulo Mod
    end of the block
    print ans
    return to indicate successful execution
end of the block

[CODE]:

const int Mod = 1e9 + 7;
int n, p;
long long choose[30000 + 25][600], ans = 1;
map<int, int> Pedy;
int main() {
    cin >> n;
    choose[0][0] = 1;
    for (int i = 1; i < 30000 + 25; i++) {
        choose[i][0] = 1;
        for (int j = 1; j <= n; j++) choose[i][j] = (choose[i - 1][j - 1] + choose[i - 1][j]) % Mod;
    }
    for (int i = 0; i < n; i++) {
        cin >> p;
        for (int j = 2; j * j <= p; j++)
            if (p % j == 0) {
                while (not(p % j)) {
                    p /= j;
                    Pedy[j]++;
                }
            }
        if (p > 1) Pedy[p]++;
    }
    for (map<int, int>::iterator it = Pedy.begin(); it != Pedy.end(); it++) {
        p = it->second;
        ans = (ans * choose[p + n - 1][n - 1]) % Mod;
    }
    cout << ans << endl;
    return 0;
}
[TASK]:
You will be given lines of pseudocode, your task is to write the corresponding C++ code. The pseudocode will provide detailed description of the c++ code line by line. The pseudocode is garanteed to be correct and complete.

[INSTRUCTION]:
The following libraries are already included in the code.
```cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <fstream>
#include <climits>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <bitset>
using namespace std;
```
Do not include them in your code again. Please surround your code with ```cpp and ``` markers. Note that the code should correspond to the pseudocode line by line.

[PSEUDOCODE]:
h, m = int
define the main function
    read h then m
    l1, l2 = int with l1 = 1 and l2 = 1
    for i = 7 to h setting i to i * 7 increment l1
    for i = 7 to m setting i to i * 7 increment l2
    ans = int with ans = 0
    if l1 + l2 is greater than 7
        print "0"
        return to indicate successful execution
    end of the block
    for i = 0 to h
        for j = 0 to m
            cnt = int vector of size 7 setting all values to 0
            x, l = int with x = i and k = 0 loop until k is l1 setting x to x / 7 and incrementing k each time increment cnt[x mod 7]
            x, l = int with x = j and k = 0 loop until k is l2 setting x to x / 7 and incrementing k each time increment cnt[x mod 7]
            if value of max_element of begin of cnt and end of cnt is less than 2 then increment ans
        end of the block
    print ans
end of the block

[CODE]:

int h, m;
int main() {
    cin >> h >> m;
    int l1 = 1, l2 = 1;
    for (int i = 7; i < h; i *= 7) l1++;
    for (int i = 7; i < m; i *= 7) l2++;
    int ans = 0;
    if (l1 + l2 > 7) {
        cout << "0\n";
        return 0;
    }
    for (int i = 0; i != h; ++i)
        for (int j = 0; j != m; ++j) {
            vector<int> cnt(7, 0);
            for (int x = i, k = 0; k != l1; x /= 7, ++k) cnt[x % 7]++;
            for (int x = j, k = 0; k != l2; x /= 7, ++k) cnt[x % 7]++;
            if (*max_element(cnt.begin(), cnt.end()) <= 1) ans++;
        }
    cout << ans << '\n';
}