You have $$$n$$$ coins, each of the same value of $$$1$$$.

Distribute them into packets such that any amount $$$x$$$ ($$$1 \leq x \leq n$$$) can be formed using some (possibly one or all) number of these packets.

Each packet may only be used entirely or not used at all. No packet may be used more than once in the formation of the single $$$x$$$, however it may be reused for the formation of other $$$x$$$'s.

Find the minimum number of packets in such a distribution.

You are given an array $$$a$$$ of $$$n$$$ integers and an integer $$$s$$$. It is guaranteed that $$$n$$$ is odd.

In one operation you can either increase or decrease any single element by one. Calculate the minimum number of operations required to make the median of the array being equal to $$$s$$$.

The median of the array with odd length is the value of the element which is located on the middle position after the array is sorted. For example, the median of the array $$$6, 5, 8$$$ is equal to $$$6$$$, since if we sort this array we will get $$$5, 6, 8$$$, and $$$6$$$ is located on the middle position.

You are given two binary strings $$$a$$$ and $$$b$$$ of the same length. You can perform the following two operations on the string $$$a$$$:

• Swap any two bits at indices $$$i$$$ and $$$j$$$ respectively ($$$1 \le i, j \le n$$$), the cost of this operation is $$$|i - j|$$$, that is, the absolute difference between $$$i$$$ and $$$j$$$.
• Select any arbitrary index $$$i$$$ ($$$1 \le i \le n$$$) and flip (change $$$0$$$ to $$$1$$$ or $$$1$$$ to $$$0$$$) the bit at this index. The cost of this operation is $$$1$$$.

Find the minimum cost to make the string $$$a$$$ equal to $$$b$$$. It is not allowed to modify string $$$b$$$.

The BFS algorithm is defined as follows.

1. Consider an undirected graph with vertices numbered from $$$1$$$ to $$$n$$$. Initialize $$$q$$$ as a new queue containing only vertex $$$1$$$, mark the vertex $$$1$$$ as used.
2. Extract a vertex $$$v$$$ from the head of the queue $$$q$$$.
3. Print the index of vertex $$$v$$$.
4. Iterate in arbitrary order through all such vertices $$$u$$$ that $$$u$$$ is a neighbor of $$$v$$$ and is not marked yet as used. Mark the vertex $$$u$$$ as used and insert it into the tail of the queue $$$q$$$.
5. If the queue is not empty, continue from step 2.
6. Otherwise finish.

Since the order of choosing neighbors of each vertex can vary, it turns out that there may be multiple sequences which BFS can print.

In this problem you need to check whether a given sequence corresponds to some valid BFS traversal of the given tree starting from vertex $$$1$$$. The tree is an undirected graph, such that there is exactly one simple path between any two vertices.

There are $$$n$$$ persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.

We want to plan a trip for every evening of $$$m$$$ days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold:

• Either this person does not go on the trip,
• Or at least $$$k$$$ of his friends also go on the trip.

Note that the friendship is not transitive. That is, if $$$a$$$ and $$$b$$$ are friends and $$$b$$$ and $$$c$$$ are friends, it does not necessarily imply that $$$a$$$ and $$$c$$$ are friends.

For each day, find the maximum number of people that can go on the trip on that day.

Given an array $$$a$$$ of $$$n$$$ integers and an integer $$$k$$$ ($$$2 \le k \le n$$$), where each element of the array is denoted by $$$a_i$$$ ($$$0 \le i \lt n$$$). Perform the operation $$$z$$$ given below on $$$a$$$ and print the value of $$$z(a,k)$$$ modulo $$$10^{9}+7$$$.

function z(array a, integer k):
    if length(a) < k:
        return 0
    else:
        b = empty array
        ans = 0
        for i = 0 .. (length(a) - k):
            temp = a[i]
            for j = i .. (i + k - 1):
                temp = max(temp, a[j])
            append temp to the end of b
            ans = ans + temp
        return ans + z(b, k)

Alice and Bob are playing a game on strings.

Initially, they have some string $$$t$$$. In one move the first player selects the character $$$c$$$ present in $$$t$$$ and erases all it's occurrences in $$$t$$$, thus splitting $$$t$$$ into many smaller strings. The game then goes independently with each of the strings — to make the move player selects one of the strings and one of the characters there, deletes all occurrences and adds the remaining string back to the game.

Alice always starts the game, and then Alice and Bob take turns making moves. The player who is unable to make a move (because there is no string left) loses.

Alice and Bob used to always start with a string $$$s$$$, but recently they found out that this became too boring. Now before each game they choose two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le |s|$$$ and play the game with the string $$$s_{l} s_{l+1} s_{l+2} \ldots s_{r}$$$ instead.

Given the string $$$s$$$ and integers $$$l$$$, $$$r$$$ for each game. Find who is going to win each game assuming they are smart and are playing optimally.

Some programming website is establishing a secure communication protocol. For security reasons, they want to choose several more or less random strings.

Initially, they have a string $$$s$$$ consisting of lowercase English letters. Now they want to choose $$$q$$$ strings using the following steps, and you are to help them.

1. A string $$$x$$$ consisting of lowercase English letters and integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq |s|$$$) are chosen.
2. Consider all non-empty distinct substrings of the $$$s_l s_{l + 1} \ldots s_r$$$, that is all distinct strings $$$s_i s_{i+1} \ldots s_{j}$$$ where $$$l \le i \le j \le r$$$. Among all of them choose all strings that are lexicographically greater than $$$x$$$.
3. If there are no such strings, you should print $$$-1$$$. Otherwise print the lexicographically smallest among them.

String $$$a$$$ is lexicographically less than string $$$b$$$, if either $$$a$$$ is a prefix of $$$b$$$ and $$$a \ne b$$$, or there exists such a position $$$i$$$ ($$$1 \le i \le min(|a|, |b|)$$$), such that $$$a_i \lt b_i$$$ and for all $$$j$$$ ($$$1 \le j \lt i$$$) $$$a_j = b_j$$$. Here $$$|a|$$$ denotes the length of the string $$$a$$$.