Problem Statement

You are given three non-negative integers, x, y, z. Your task is to find the smallest non-negative integer n with all of the following conditions:

• n\ {\rm mod}\ 17 = x
• n\ {\rm mod}\ 107 = y
• n\ {\rm mod}\ 1000000007(=10^9+7) = z

Constraints

• 0 \leq x < 17
• 0 \leq y < 107
• 0 \leq z < 10^9+7

Sample Input 1

15 50 1

Sample Output 1

1000000008

Sample Input 2

0 0 0

Sample Output 2

0

Sample Input 3

3 14 159265358

Sample Output 3

1050159272708

Problem Statement

There are 1-, 5-, 10-, 50-, 100-, 500- yen coins, and you have an infinite number of coins of each type.

For a given positive integer x, let f(x) be the smallest number of coins you have to use to pay exactly x yen. For example, f(2018)= 9 because 2018 = 1 + 1 + 1 + 5 + 10 + 500 + 500 + 500 + 500.

You are given a positive integer N. Count the number of positive integers x such that f(x) = N.

Constraints

• 1 \leq N \leq 10^{18}

Sample Input 1

1

Sample Output 1

6

The value of x is 1, 5, 10, 50, 100, or 500.

Sample Input 2

2

Sample Output 2

19

The value of x is 2, 6, 11, 15, 20, 51, 55, 60, 101, 105, 110, 150, 200, 501, 505, 510, 550, 600, or 1000.

Sample Input 3

1000000000000000000

Sample Output 3

500

Problem Statement

You have a regular N-sided convex polygon. You are going to choose 3 or more vertices from the polygon, and make a new convex polygon P formed by chosen vertices. You very much like equiangular polygons (polygons whose vertex angles are all equal), so the polygon P must be equiangular.

Count the number of equiangular polygons that you can get in the above-mentioned way. Here, two polygons are considered to be the same if they are congruent, that is, one has the same shape and size as the other or as the mirror image of the other.

Constraints

• 3 \leq N \leq 10^{12}

Sample Input 1

6

Sample Output 1

3

You can get following 3 polygons.

Sample Input 2

10

Sample Output 2

4

You can get following 4 polygons.

Sample Input 3

1000000000000

Sample Output 3

749847411091

Problem Statement

First, you are given a positive integer MOD.

You have a knapsack, this is empty at first.

You have to perform Q queries.

• In each query, you have first to perform either ADD or REMOVE operation, and then perform FIND operation.
• ADD operation : You are given positive integers w, v. You put the cookie whose weight is w and whose value is v to the knapsack.

• REMOVE operation : You take out the cookie with the smallest weight from the knapsack and eat it.

• FIND operation : You are given non-negative integers l, r. You answer the following question:

  • Can you choose cookies from the knapsack so that the sum X of the weights of selected cookies satisfies l \leq (X\ {\rm mod}\ MOD) \leq r
  • If you can't, output -1.
  • Otherwise, output the maximum sum of the values of selected cookies.

Constraints

• 2 \leq MOD \leq 500
• 1 \leq Q \leq 100,000
• 1 \leq w_i, v_i \leq 10^9

• 0 \leq l_i \leq r_i \leq MOD-1

• The cookie given by an ADD operation is strictly heavier than any cookie which was added by a previous ADD operation.

• When executing REMOVE operation, the knapsack isn't empty.
• Queries are Online Query. Queries are encrypted as described later.

Decryption

We prepare the decryption code with C++11 (or later), Java, D, C#.

Use class Crypto for decryption, the code of class Crypto is below.

#include <cstdint> //uint8_t, uint32_t

class Crypto {
public:    
    Crypto() {
        sm = cnt = 0;
        seed();
    }

    int decode(int z) {
        z ^= next();
        z ^= (next() << 8);
        z ^= (next() << 16);
        z ^= (next() << 22);
        return z;
    }

    void query(long long z) {
        const long long B = 425481007;
        const long long MD = 1000000007;
        cnt++;
        sm = ((sm * B % MD + z) % MD + MD) % MD;
        seed();
    }
private: 
    long long sm;
    int cnt;

    uint8_t data[256];
    int I, J;

    void swap_data(int i, int j) {
        uint8_t tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;    
    }

    void seed() {
        uint8_t key[8];
        for (int i = 0; i < 4; i++) {
            key[i] = (sm >> (i * 8));
        }
        for (int i = 0; i < 4; i++) {
            key[i+4] = (cnt >> (i * 8));
        }

        for (int i = 0; i < 256; i++) {
            data[i] = i;
        }
        I = J = 0;

        int j = 0;
        for (int i = 0; i < 256; i++) {
            j = (j + data[i] + key[i%8]) % 256;
            swap_data(i, j);
        }
    }

    uint8_t next() {
        I = (I+1) % 256;
        J = (J + data[I]) % 256;
        swap_data(I, J);
        return data[(data[I] + data[J]) % 256];
    }
};

public class Main {
    public static class Crypto {
        public Crypto() {
            sm = cnt = 0;
            seed();
        }
        public int decode(int z) {
            z ^= next();
            z ^= (next() << 8);
            z ^= (next() << 16);
            z ^= (next() << 22);
            return z;
        }
        public void query(long z) {
            final long B = 425481007;
            final long MD = 1000000007;
            cnt++;
            sm = ((sm * B % MD + z) % MD + MD) % MD;
            seed();
        }

        long sm;
        int cnt;

        byte data[] = new byte[256];
        int I, J;

        int asUint(byte x) {
            int y = x;
            return y & 0xff;
        }
        void seed() {
            byte key[] = new byte[8];
            for (int i = 0; i < 4; i++) {
                key[i] = (byte)(sm >>> (i * 8));
            }
            for (int i = 0; i < 4; i++) {
                key[i+4] = (byte)(cnt >>> (i * 8));
            }

            for (int i = 0; i < 256; i++) {
                data[i] = (byte)i;
            }
            I = J = 0;

            int j = 0;
            for (int i = 0; i < 256; i++) {
                j = (j + asUint(data[i]) + asUint(key[i % 8])) % 256;
                byte tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
        int next() {
            I = (I+1) % 256;
            J = (J+asUint(data[I])) % 256;
            byte tmp = data[I];
            data[I] = data[J];
            data[J] = tmp;
            return asUint(data[(asUint(data[I]) + asUint(data[J])) % 256]);
        }
    }
    public static void main(String[] args) {
        ...
    }
}

class Crypto {
public:
    this() {
        sm = cnt = 0;
        seed();
    }

    int decode(int z) {
        z ^= next();
        z ^= (next() << 8);
        z ^= (next() << 16);
        z ^= (next() << 22);
        return z;
    }

    void query(long z) {
        immutable static long B = 425481007;
        immutable static long MD = (10^^9)+7;
        cnt++;
        sm = ((sm * B % MD + z) % MD + MD) % MD;
        seed();
    }
private:
    import std.algorithm : swap;
    long sm;
    int cnt;

    ubyte[256] data;
    int I, J;
    void seed() {
        ubyte[8] key;
        foreach (i; 0..4) {
            key[i] = cast(ubyte)(sm >> (i*8));
        }
        foreach (i; 0..4) {
            key[i+4] = cast(ubyte)(cnt >> (i*8));
        }

        foreach (i; 0..256) {
            data[i] = cast(ubyte)(i);
        }
        I = J = 0;

        int j = 0;
        foreach (int i; 0..256) {
            j = (j + data[i] + key[i%8]) % 256;
            swap(data[i], data[j]);
        }        
    }

    ubyte next() {
        I = (I+1) % 256;
        J = (J + data[I]) % 256;
        swap(data[I], data[J]);
        return data[(data[I] + data[J]) % 256];
    }
}

class Crypto {
    public Crypto() {
        sm = cnt = 0;
        data = new byte[256];
        seed();
    }

    public int decode(int z) {
        z ^= next();
        z ^= (next() << 8);
        z ^= (next() << 16);
        z ^= (next() << 22);
        return z;
    }

    public void query(long z) {
        const long B = 425481007;
        const long MD = 1000000007;
        cnt++;
        sm = ((sm * B % MD + z) % MD + MD) % MD;
        seed();
    }

    long sm;
    int cnt;

    byte[] data;
    int I, J;

    void seed() {
        byte[] key = new byte[8];
        for (int i = 0; i < 4; i++) {
            key[i] = (byte)(sm >> (i*8));
        }
        for (int i = 0; i < 4; i++) {
            key[i+4] = (byte)(cnt >> (i*8));
        }

        for (int i = 0; i < 256; i++) {
            data[i] = (byte)i;
        }
        I = J = 0;

        int j = 0;
        for (int i = 0; i < 256; i++) {
            j = (j + data[i] + key[i%8]) % 256;
            byte tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }
    }

    byte next() {
        I = (I+1) % 256;
        J = (J + data[I]) % 256;
        byte tmp = data[I];
        data[I] = data[J];
        data[J] = tmp;
        return data[(data[I] + data[J]) % 256];
    }
}

The procedure of decrypto:

• First, you make an instance of class Crypto.
• In each query,
  • call the decode function for each of t', w', v', l', r' in order. The return values are t, w, v, l, r.
  • call the query function with the result of the FIND operation.

The sample code of C++ is below.

#include <cstdio>
#include <cstdlib>
#include <cstdint> //uint8_t, uint32_t

class Crypto {
    ...
};

int main() {
    int MOD, Q;
    scanf("%d %d", &MOD, &Q);
    Crypto c;
    for (int i = 0; i < Q; i++) {
        int t, w, v, l, r;
        scanf("%d %d %d %d %d", &t, &w, &v, &l, &r);
        t = c.decode(t);
        w = c.decode(w);
        v = c.decode(v);
        l = c.decode(l);
        r = c.decode(r);
        if (t == 1) {
            (add candy(w, v))
        } else {
            (delete candy)
        }
        long long ans = (answer for query(l, r));
        c.query(ans);
        printf("%lld\n", ans);
    }
}

The sample codes of Java, D, C# are below.

import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static class Crypto {
        ...
    }    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); //!!warning!! : Java's scanner is slow
        PrintWriter out = new PrintWriter(System.out);
        int MOD = in.nextInt();
        int Q = in.nextInt();

        Crypto c = new Crypto();
        for (int i = 0; i < Q; i++) {
            int t, w, v, l, r;
            t = c.decode(in.nextInt());
            w = c.decode(in.nextInt());
            v = c.decode(in.nextInt());
            l = c.decode(in.nextInt());
            r = c.decode(in.nextInt());
            if (t == 1) {
                (add candy(w, v))
            } else {
                (delete candy)
            }
            long ans = (answer for query(l, r));
            c.query(ans);
            out.println(ans);
        }
        out.flush();
    }
}

class Crypto {
    ...
}
int main() {
    import std.stdio;
    int MOD, Q;
    readf("%d\n%d\n", &MOD, &Q);
    Crypto c = new Crypto();
    foreach (i; 0..Q) {
        int t, w, v, l, r;
        readf("%d %d %d %d %d\n", &t, &w, &v, &l, &r);
        t = c.decode(t);
        w = c.decode(w);
        v = c.decode(v);
        l = c.decode(l);
        r = c.decode(r);
        if (t == 1) {
            (add candy(w, v))
        } else {
            (delete candy)
        }
        long ans = (answer for query(l, r));
        c.query(ans);
        writeln(ans);
    }
    return 0;
}

using System;
using System.IO;

class Crypto {
    ...
}
class Myon {
    static void Main() {
        var writer = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false}; //fast writer
        Console.SetOut(writer);

        int MOD = int.Parse(Console.ReadLine());
        int Q = int.Parse(Console.ReadLine());
        Crypto c = new Crypto();
        for (int i = 0; i < Q; i++) {
            var inputs = Console.ReadLine().Split(' ');
            int t, w, v, l, r;
            t = c.decode(int.Parse(inputs[0]));
            w = c.decode(int.Parse(inputs[1]));
            v = c.decode(int.Parse(inputs[2]));
            l = c.decode(int.Parse(inputs[3]));
            r = c.decode(int.Parse(inputs[4]));
            if (t == 1) {
                (add candy(w, v))
            } else {
                (delete candy)
            }
            long ans = (answer for query(l, r));
            c.query(ans);
            Console.WriteLine(ans);
        }
        Console.Out.Flush();
    }
}

Remark:

• You don't need to find vulnerability of this encryption.
• class Crypto consume time at most about 200 ms when Q = 100,000.

Output

Print results of FIND operation, one per line.

Sample Input 1

10
7
281614559 249378726 433981056 466775634 683612866
727071329 787572584 591471796 328464426 757737734
279580343 240336097 538846427 808491898 224313807
222498984 42804452 371605808 667115067 791865961
68683864 1045549765 515479514 1067782238 349547144
907343711 381772625 149003422 879314974 953881571
883899098 700164610 414212891 752949213 972845634

Sample Output 1

10
0
-1
21
-1
11
111

The result of decoding this input is as follows.

10
7
1 5 10 5 5
2 0 0 0 9
1 7 10 2 4
1 12 11 9 9
2 0 0 1 1
1 22 10 2 3
1 32 100 4 4

Sample Input 2

7
20
281614559 249378726 433981094 466775639 683612870
59536386 999828879 241246766 434670565 174365647
172060134 848462699 857413429 182122460 807914643
808426426 600772095 829463884 974102196 354283529
370037909 1024921880 664216868 194331103 140834169
917331875 242953442 205247688 335469789 1055568137
823475244 641321246 617915164 160300810 1073617378
892669150 939175632 904628449 606339993 1059849410
829170894 436718235 288920513 228195002 55212938
772189413 373108543 94133155 610930061 513937768
986619331 175674265 812546186 865335970 605634588
880196843 1071068047 723408215 587598264 380801783
393196081 141080294 584230885 135343295 661927186
5740819 967233824 22597607 888639499 467454437
365679801 515258603 989059385 962028117 761163096
357270919 737051059 569528959 935653628 70506031
869282414 947492121 280522456 96822010 856514221
155948699 826430734 291243254 381421299 617876780
980891674 833928389 1048677341 522527723 223764850
50617939 963598173 281959650 499436870 47455938

Sample Output 2

0
134
90
158
-1
22
238
269
179
189
121
53
41
41
-1
58
-1
84
-1
149

The result of decoding this input is as follows.

7
20
1 5 44 0 1
1 11 90 0 3
2 0 0 3 4
1 18 68 1 6
1 25 32 2 3
1 31 22 2 3
1 32 26 1 5
1 36 31 3 6
2 0 0 2 5
1 43 10 3 6
2 0 0 5 6
2 0 0 3 4
2 0 0 2 4
2 0 0 1 5
2 0 0 3 5
1 49 48 0 4
2 0 0 1 5
1 50 36 0 6
1 56 48 3 5
1 59 17 3 5

Problem Statement

Ao loves certain sets of non-negative integers.

Let X be a set of non-negative integers. Whether she loves X or not is determined as follows:

• If X is the empty set, she loves X.
• If, for any (possibly the same) two elements u and v in X, at least one of u+v and {\rm abs}(u-v) is contained in X, she loves X.
• If none of the above conditions is satisfied, she does not love X.

You are a big fan of Ao, and going to present her a set of non-negative integers. Currently you have a set A of non-negative integers. You want to erase (possibly zero) elements from A so that she loves the set of remaining integers. You also want to maximize the number of remaining integers. What is the largest number of remaining integers?

Constraints

• A is not empty.
• The largest element in A is not larger than 500,000

Sample Input 1

1000001001011

Sample Output 1

3

The set A = \{0,6,9,11,12\}. If you erase 9 and 11, Ao loves the set of remaining integers: \{0,6,12\}.

Sample Input 2

10110110101

Sample Output 2

4

Sample Input 3

0111

Sample Output 3

0

The set of remaining integers must be empty.

Problem Statement

Takahashi-kun sends integer sequences to Aoki-kun every year as his birthday present. But in this year, Takahashi-kun plans to send sequences of points on a two-dimensional plane to Aoki-kun.

Firstly, he makes 3 point sequences: (a_0, a_1, ..., a_{N-1}), (b_0, b_1, ..., b_{N-1}), and (c_0, c_1, ..., c_{N-1}), and makes a point d_0. Then he makes the points d_1, d_2, ..., d_N in this order as follows:

• For each i = 0, 1, ..., {N-1}, d_{i+1} is defined as the intersection point of two lines: the line that passes through a_i and b_i, and the line that passes through c_i and d_i.

It can happen that a point d_{i+1} can not be defined for some i. For example, when two lines are the same, there are an infinite number of intersection points.

Takahashi-kun wants to know the smallest i such that d_{i+1} can not be defined. To be precise, d_{i+1} can not be defined if either of the following conditions is met.

• c_i = d_i
• two lines given by a_i, b_i, c_i, and d_i are the same, or parallel.

It is guaranteed that a_i \neq b_i for all i.

Note that, in the following sections, x- and y- coordinates of a point p are denoted as p.x and p.y, respectively.

Constraints

• 1 \leq N \leq 100,000
• |a_i.x|, |a_i.y|, |b_i.x|, |b_i.y|, |c_i.x|, |c_i.y| \leq 1,000
• |d_0.x|, |d_0.y| \leq 1000
• a_i \neq b_i
• All values in input are integers.

Sample Input 1

6
0 0
10 -10 10 10 10 0
0 10 20 10 10 10
0 -10 0 -100 0 10
0 0 0 -100 0 0
0 0 0 1 0 0
31 14 15 92 65 35

Sample Output 1

3

Sample Input 2

11
0 0
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
0 0 3 1 3 1

Sample Output 2

10

Problem Statement

You have Q triangles, numbered 1 through Q.

The coordinates of the vertices of the i-th triangle are (x_{i1}, y_{i1}), (x_{i2}, y_{i2}) and (x_{i3}, y_{i3}) in counterclockwise order. Here, x_{i1}, x_{i2}, x_{i3}, y_{i1}, y_{i2} and y_{i3} are all integers.

For each triangle, determine if there exists a grid point contained in its interior (excluding the boundary). If it exists, construct one such point.

Constraints

• All input values are integers.
• 1 \leq Q \leq 10 000
• 0 \leq x_{i1}, x_{i2}, x_{i3}, y_{i1}, y_{i2}, y_{i3} \leq 10^9
• (x_{i1}, y_{i1}), (x_{i2}, y_{i2}) and (x_{i3}, y_{i3}) are in counterclockwise order.
• The areas of the triangles are not 0.

Sample Input 1

4
1 7 3 5 5 7
1 4 1 2 5 4
6 1 7 1 7 6
11 3 11 4 8 5

Sample Output 1

3 6
2 3
-1 -1
10 4

Problem Statement

You are given a string S consisting of lowercase English letters. Count the number of strings T that satisfies all of the following conditions:

• T is a string of the same length as S, consisting of lowercase English letters.
• For all K ( 1 \leq K \leq |S| ), the string formed by the first K letters of S does not coincide with the string formed by the last K letters of T.

Since the answer can be very large, find the number modulo 10^9+7.

Constraints

• 1 \leq |S| \leq 10^6
• S consists of lowercase English letters.

Sample Input 1

aa

Sample Output 1

650

For example, T= zz and ab satisfy the condition, but ba or aa does not.

Sample Input 2

abc

Sample Output 2

16873

Sample Input 3

xrxbaxrxikxrxgvcpuwx

Sample Output 3

352084595

Problem Statement

You are given an integer sequence a_0, a_1, ..., a_{N-1}.

You have to perform Q queries, each query is one of the following:

• ADD QUERY(t=0 l r x) : for each i between l and r, inclusive, replace a_i with a_i + x.
• DIV QUERY(t=1 l r x) : for each i between l and r, inclusive, replace a_i with {\rm floor}(a_i / x), where {\rm floor}(y) is the biggest integer that is not greater than y.
• MAX QUERY(t=2 l r x=0) : print {\rm max}(a_l, a_{l+1}, ..., a_r).
• RESTORE QUERY(t=3 l r x=0) : for each i between l and r, inclusive, set a_i to the initial value of a_i, that is, the value given in the input.

Constraints

• All input values are integers.
• 1 \leq N, Q \leq 200,000
• 0 \leq a_i \leq 10^8
• t_i = 0, 1, 2, 3
• 0 \leq l_i \leq r_i \leq N-1
• 1 \leq x_i \leq 1000(when t_i \neq 2, 3)

Sample Input 1

5 9
1 2 3 4 5
2 0 4 0
0 0 1 10
2 0 4 0
2 2 2 0
1 0 1 4
2 0 0 0
2 1 1 0
3 0 4 0
2 0 1 0

Sample Output 1

5
12
3
2
3
2

• {\rm max}(1, 2, 3, 4, 5) = 5
• 1, 2, 3, 4, 5 → 11, 12, 3, 4, 5
• {\rm max}(11, 12, 3, 4, 5) = 12
• {\rm max}(3) = 3
• 11, 12, 3, 4, 5 → 2, 3, 3, 4, 5
• {\rm max}(2) = 2
• {\rm max}(3) = 3
• The array is restored to 1, 2, 3, 4, 5
• {\rm max}(1, 2) = 2

Sample Input 2

4 7
0 1 0 1
2 0 3 0
0 0 3 1
1 0 3 2
2 0 3 0
0 0 3 1
1 0 3 2
2 0 3 0

Sample Output 2

1
1
1

Sample Input 3

10 23
13 1 22 8 28 18 23 9 22 27
1 3 4 5
1 8 8 8
0 3 9 5
0 2 6 3
3 0 4 0
1 1 3 7
2 2 2 0
2 3 5 0
0 1 4 2
3 0 9 0
2 0 1 0
0 3 9 8
2 1 9 0
0 8 9 5
1 5 7 7
0 3 5 7
0 7 9 7
3 3 6 0
2 1 6 0
0 1 1 7
1 4 8 10
2 0 9 0
1 5 6 1

Sample Output 3

3
28
13
36
28
47

Problem Statement

You have a string s=s_0s_1...s_{N-1} of length N consisting of A and B. You have to process Q queries. Consider the i-th query ( 1 \leq i \leq Q ). In this query you are given integers l_i and r_i. Then, for each x ( l_i \leq x \leq r_i ), s_x is changed to the other letter, that is, A becomes B and B becomes A.

After each query, you have to calculate f(B + s + A). Here, f(t) is a function which, given a string t, returns a non-negative integer. The value of f(t) is defined as follows:

• Consider the following step.
  • Step: For all substrings of t which coincide with BA, replace them with AB. All replacements are done at the same time.
• f(t) is the number of steps you need to perform until no substring of t coincides with BA.

For example, f(ABAB) = 1, f(BBAA) = 3, and f(AAA) = 0.

Constraints

• 1 \leq N \leq 200000
• |s| = N
• s consists of A and B.
• 1 \leq Q \leq 200000
• 0 \leq l_i \leq r_i \leq N-1
• N,Q,l_i,r_i are integers.

Sample Input 1

5
BAABA
2
1 3
0 2

Sample Output 1

6
6

After the first query, the string s is BBBAA, so print the value of f(BBBBAAA) in the first line. After the second query, the string s is AAAAA, so print the value of f(BAAAAAA) in the second line.

Sample Input 2

1
A
2
0 0
0 0

Sample Output 2

2
2

Problem Statement

You are given three integers N, A, and B.

Let P=(P_0,P_1,...,P_{N-1}) be a permutation of (0,1,...,N-1). P is said good if and only if it satisfies all of the following conditions:

• The length of a longest increasing subsequence of P is at most 2.
• P_A = B

Count the number of good permutations modulo 10^9+7.

Constraints

• 1 \leq N \leq 10^6
• 0 \leq A \leq N-1
• 0 \leq B \leq N-1

Sample Input 1

3 0 0

Sample Output 1

1

The only good permutation is (0,2,1).

Sample Input 2

12 2 3

Sample Output 2

5390

Sample Input 3

10000 9875 5431

Sample Output 3

135608808