You are given a sequence consisting of $$$N$$$ integers $$$\lbrace a_i \rbrace$$$. There will be $$$m$$$ different events.

• $$$\texttt{AND} ~ l ~ r ~ v$$$ – for all elements $$$a_i ~ (l \leq i \leq r)$$$, change $$$a_i$$$ to $$$a_i ~ \& ~ v$$$, where $$$\&$$$ means bitwise AND

• $$$\texttt{UPD} ~ x ~ v$$$ – change $$$a_x$$$ to $$$v$$$

• $$$\texttt{QUE} ~ l ~ r$$$ – ask for the maximum value of $$$a_i$$$ where $$$l \leq i \leq r$$$

Please write a program to support these events efficiently.

Moon cake betting (博饼) is a traditional Mid-autumn festival activity originated in Xiamen and then spread to southern Fujian. It began in the early Qing Dynasty. It was invented by Zheng Chenggong when he stationed in order to resolve the Mid-autumn lovesickness of the soldiers and inspire their morale. As a result, it has become a unique folk custom in Southern Fujian.

However, no one around wor knows how to play Moon cake betting, he have to play it with his brain girlfriend.

Moon cake betting is a game of dice. Each person rolls 6 dice at a time and gets corresponding prizes according to the result type.

All result types are as follows:

• ZhuangYuan: There are six sub-situations.

  • SiHong: Four $$$\texttt{#4}$$$ + two arbitrary non $$$\texttt{#4}$$$ (non $$$\texttt{#1#1}$$$), which can not form a Multi-award special case.
  • WuZiDengKe: Five arbitrary (non $$$\texttt{#4#4#4#4#4}$$$) + one arbitrary different from the previous ones, which can form a Multi-award special case.
  • WuHong: Five $$$\texttt{#4}$$$ + one arbitrary non $$$\texttt{#4}$$$, which can not form a Multi-award special case.
  • ManDiJin: Six arbitrary (non $$$\texttt{#4#4#4#4#4#4}$$$), which can not form a Multi-award special case.
  • ManTangCai: Six $$$\texttt{#4}$$$, which can not form a Multi-award special case.
  • ZhuangYuanChaJinHua: Four $$$\texttt{#4}$$$ + two $$$\texttt{#1}$$$, which can not form a Multi-award special case.

  The rank of ZhuangYuan is compared according to the following rules:

  1. First compare the type. SiHong < WuZiDengKe < WuHong < ManDiJin < ManTangCai < ZhuangYuanChaJinHua
  2. If the types are same, then compare according to the following rules:

     1. If they are same SiHong, then compare the sum of remaining two dices points.
     2. If they are same WuZiDengKe, then compare the points of dice that form the WuZiDengKe. If still the same, then compare the remaining one dice points.
     3. If they are same WuHong, then compare the remaining one dice points.
     4. If they are same ManDiJin, then compare the points of dice that form the ManDiJin.
     5. If still same after compared by above rules, then the first one who rolled will get it.

• DuiTang: $$$\texttt{#1#2#3#4#5#6}$$$, which can not form a Multi-award special case.

  

• SanHong: Three $$$\texttt{#4}$$$ + three arbitrary non $$$\texttt{#4}$$$, which can not form a Multi-award special case.
• SiJin: Four arbitrary non $$$\texttt{#4}$$$ + two arbitrary different from the previous, which can form a Multi-award special case.
• ErJu: Two $$$\texttt{#4}$$$ + four arbitrary non $$$\texttt{#4}$$$ and doesn't constitute any other form, which can not form a Multi-award special case.

  

• YiXiu: One $$$\texttt{#4}$$$ + five arbitrary non $$$\texttt{#4}$$$ and doesn't constitute any other form, which can not form a Multi-award special case.
• LuoBang: Doesn't constitute any other form.

There are also several special cases:

• TanChu: If the dice is thrown out of range (concretely, get $$$\texttt{#0}$$$), the next round will stop, and this roll is invalid.
• ManTangHei: Six $$$\texttt{#6}$$$, a part of ManDiJin, except for the ZhuangYuan prize, the rest of the other prize all will be taken away.

  

• Multi-award: May appear in the SiJin and WuZiDengKe, for example $$$\texttt{#3#3#3#3#4#2}$$$ is SiJin with YiXiu, in this case, player can get the award of SiJin and YiXiu at the same time; $$$\texttt{#5#5#5#5#5#4}$$$ is WuZiDengKe with YiXiu, in this case, player can get the award of YiXiu and record the ZhuangYuan at the same time.

Now it is known that there are $$$1$$$ ZhuangYuan prize, $$$2$$$ DuiTang prizes, $$$a$$$ SanHong prizes, $$$b$$$ SiJin prizes, $$$c$$$ ErJu prizes, $$$d$$$ YiXiu prizes.

The prize rules are as follows:

• For ZhuangYuan prize, at the end of game, the biggest one who rolled will win it, and every one will take the last time that rolled the ZhuangYuan to compared.

• For other prizes, first come, first served. If anyone roll a prize but there is no residue then he get nothing. For example player A roll the YiXiu and there is only one YiXiu residue then A can get the last YiXiu. After that, player B roll the YiXiu. But now there is no YiXiu residue so B can not get anything.

Now we know that $$$n$$$ player sit together in a circle and play $$$m$$$ rounds. Player 1 starts to roll. They roll in turn $$$m$$$ times in the order of $$$(1, 2, 3, \cdots, n-1, n, 1, 2, \cdots)$$$.

If any player throw dice out of the range and get TanChu, then this roll is invalid, and he will do nothing the next round (Caution, skipped round is counted) and let the next player roll.

Given the game situation, can you find out the final prize situation of every player?

Little G loves cookies.

One day, he bought a bag of cookies and started eating. The shape of each cookie can be approximately regarded as a convex polygon in 2D coordinate system. Unconsciously, a few cookies fell to the ground and each of them broke into two pieces. The broken pieces can be regarded as simple polygons.

Little G didn't want them to go to waste. So, he randomly picked two pieces from the ground and try to restore the original cookie by translating one of the pieces.

Little G is poor at geometry, it takes long time for him to do this or figure out it's just impossible to form a convex polygon using the two simple polygons. Please write a program to help him.

Note that after combining, the overlapping edges of two polygons need to correspond one to one. One edge matching two or more edges of another polygon is illegal.

The graph above shows one illegal situation for matching (a). The situation (b) of the graph is illegal because the right edge of the first square matches two edges of the other polygon. The situation (c) is legal.

One day, Fop_zz is playing a boring game merge numbers though he is busy.

There is a sequence $$$\{a_i\}$$$ of length $$$N$$$ and he should play this game for $$$n-1$$$ turns. In one turn, he chooses an index $$$x$$$ and then he merges $$$a_x$$$ and $$$a_{x+1}$$$ to $$$a_x \times a_{x+1} \bmod 1\,000\,003$$$ and gets $$$(a_x-a_{x+1})^2$$$ scores.

So, after one turn, the length of sequence will decrease exactly one, and after the last turn there's only $$$1$$$ integer in the sequence and he stops.

Now he want to know the maximum total scores he can get. Can you help him?

You are given $$$n$$$ strings $$$s_1, s_2, \cdots, s_n$$$. We call $$$t$$$ a substring of $$$s$$$ if we can get $$$t$$$ by deleting several consecutive characters (probably zero) from the beginning and/or the end of the string $$$s$$$.

We define a multinest of strings as a sequence $$$p_1, p_2, \cdots, p_m ~ (m \leq n)$$$, where $$$p_i$$$ are pair-wise distinct and $$$s_{p_i}$$$ is a substring of $$$s_{p_{i-1}}$$$ for any $$$2 \leq i \leq m$$$. The length of the multinest is the number of elements in the sequence.

Now you need to calculate the maximum possible length of the multinest among the $$$n$$$ strings.

One day, Little Y came cross a function that confused her a lot.

$$$$$$ f(n) = \begin{cases} 1, & n \in \{1\} \bigcup \operatorname{Prime} \\ p\,f(p^{k-2}), & n = p^k ~ (p \in \operatorname{Prime}; ~ k \gt 1) \\ f(p_1^{e_1})\prod_{i=2}^r {p_i}^{e_i}, & n = \prod_{i=1}^r {p_i} ^ {e_i} ~ (p_1 \lt p_2 \lt \cdots \lt p_r; ~ p_i \in \operatorname{Prime}; ~ r \ge 2) \end{cases} $$$$$$

Now Little Y is interested in $$$\sum_{i=1}^n f(i)$$$. Can you help her?

NoGo is a game whose rules are the reverse of Go. In this game, the player who takes opponent's chess pieces or kills his own pieces will lose the game.

Little G is writing a bot to play the game. And he is now working on a simplified version of this game. In the simplified version, Little G has a chess board of size $$$n \times m$$$. There are only two kinds of state in each intersection: empty or occupied by his stone. Two intersections are considered connected if they are orthogonally adjacent (up, down, left, or right). He believes that the more connected components of empty positions his stones can separate, the greater chance he will have to win.

Now you are given the state of chess board at some point. You need to place one stone into an empty intersection and make the number of separated empty connected components as large as possible after placing your stone.

As we all know, disjoint set union is a useful tool. However, sometimes we must apply the strategy of union by rank or path compression to make it quick. In general, if we have $$$n$$$ operations of merge, we may do all these operations in time complexity of $$$O(n \alpha(n))$$$, where $$$\alpha(n) \leq 4$$$ for $$$n \leq 10^5$$$.

Little Y is the teaching assistant of Data Structure class. One day, one problem was left for practice. There are $$$n$$$ sets numbered from $$$1$$$ to $$$n$$$. Then there are $$$n$$$ pairs of integer $$$(A_i,B_i)$$$. We should merge set $$$A$$$ and $$$B$$$ for each pair $$$(A,B)$$$. The task is to get the count of disjoint sets after all operations.

When reading the homework codes from students, Little Y noticed one implementation of find operation without recursion. Then she thinks this code is not implemented correctly, which may lead to about $$$O(n^2)$$$ times of read or write operations to the array $$$\texttt{parent}$$$. To verify this, she adds a temporary variable called $$$\texttt{counter}$$$ to track the count of write operations.

#include <iostream>
using namespace std;
const int MAXN = 1e5+10;
int parent[MAXN];
long long counter = 0;

int find(int x) {
    while (x != parent[x]) {
        if (x < parent[x]) {
            // Merge-by-rank and Path-compression
            parent[x] = parent[parent[x]];
        }
        x = parent[x];
        counter++;
    }

    return x;
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    parent[a] = b;
}

int main() {
    int n, A, B, ans = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
        parent[i] = i;

    for (int i = 1; i <= n; i++) {
        cin >> A >> B;
        merge(A, B);
    }

    for (int i = 1; i <= n; i++)
        if (i == find(i))
            ans++;

    cout << ans << endl;
    return 0;
}

Little Y thinks there exists one input data that makes the $$$\texttt{counter}$$$ large enough. Can you help her to provide one input data to prove that she is right?

For a given $$$n$$$, you should construct $$$n$$$ pairs of integers $$$(A_i, B_i)$$$. When the number $$$n$$$ and $$$n$$$ pairs of integers $$$(A_i, B_i)$$$ is sent to this program, you should guarantee that the final value of $$$\texttt{counter}$$$ should be greater than a certain number $$$T$$$, which means that this program cannot stop within $$$T$$$ write operations.

ICU for Car! is an exciting racing game. Two players take turns to make a move. In one move, the player chooses one car and push this car one grid right-forward. Cars satisfying all the conditions will be also pushed forward too.

• In the same racetrack with the selected car.
• In front of the selected car.
• Connected with the selected car. Formally, two cars $$$x$$$ and $$$y$$$ are connected, if there is no gap between $$$x$$$ and $$$y$$$, or they are both connected with car $$$z$$$.

Note that if the right-most car in this move has already touched the finishing line, this move is not valid and you cannot process it. The player who can't make a move loses.

There are $$$n$$$ racetracks holding the cars in one game. For each racetrack, the number of cars $$$m_i$$$, the position of each car $$$x_j$$$ and the position of finishing line $$$e_i$$$ are given.

Now Alice and Bob wants to play this game and Alice takes the first turn. Can you tell wor the winner?

Aki is the prime minister in JOJO's Factory.

There are two types of machines in the factory, which are called A-machine and B-machine respectively. Both the number of two types of machines are $$$N$$$. One A-machine should work with exactly one B-machine and one B-machine should work with exactly one A-machine.

Unfortunately, some pairs of machines can not work together due to some unknown reason. A pair $$$(i,j)$$$ means $$$i$$$-th A-machine can not work with $$$j$$$-th B-machine.

In order to improve the efficiency, you, his staff, should find a plan that the most A-machines can run normally.

Luckily, Aki is a talented prime minister, so the number of un-working pairs is no more than $$$2N-3$$$.

Megumi is a girl who likes to eat.

Today there will be a party at Aki's home. There are $$$N$$$ cakes for Megumi of different weight on the table. She will choose one cake and eat no more than half of it every time. But out of conscience, she won't eat those cakes whose weight is smaller than $$$K$$$.

However, she knows a magic to merge two cakes. That means she can put two cakes together and combine them into a larger cake whose weight is equal to the sum of weight of previous cakes.

Now Aki wants to know the maximum total weight of cakes Megumi can eat. Please note that she can eat as many times as she can, and each time the weight she eat is a positive integer no more than the half of the weight of cake.

Labi-ribi is a newly published STG. As everyone knows, wor is a TouHouProject-Player. As a TouHouProject-Player, he must want to play such funny STG.

Labi-ribi has $$$n$$$ stages. Each stage has a boss at level $$$h_i$$$. Only when player's level is greater than or equal to boss's level, the player can beat boss and clear this stage. After beating $$$i$$$-th boss, the level of all remaining bosses will be increased $$$a_i$$$ points, and the player's level will be increased $$$b_i$$$ points.

wor want to challenge the hardest. Therefore, he wants to use the minimun initial level to clear all stages. Can you tell him the minimun initial level that he need to clear all stages?

Labi-ribi is a great game, so there is an additional DLC annually. Now there has been $$$q$$$ DLCs. For one DLC, it provides a brand new stage. wor is so patient that every time an additional DLC was provided, he would play Labi-ribi again. Similarly, for each additional DLC, wor wants to know the minimun initial level that can clear all stages. Can you help him?