The kid Andrew doesn't like coins. His country currently uses n different coin types, each with a different value. It is guaranteed that the coin with value 1 is one of the different coin types.

Andrew's weekly taco-pizza grocery list contains r - l + 1 items with costs l, l + 1, ..., r. Unfortunately, Andrew needs to buy each of these items separately as they are sold at different stores. Furthermore, these stores do not give any change, so Andrew must pay the exact amount in coins. Andrew is rather unhappy with the amount of coins he needs to handle every week, so he wants to convince his country to start using a new coin type to minimize the total number of coins needed to buy groceries for his weekly taco-pizza needs.

Andrew is too busy infiltrating UBC, so he wants you to tell him the best coin type to add, or that no new coin types can decrease the amount of coins he needs to use.

Paul is running a quaint business that delivers badminton rackets. There are n places of interest between which he will deliver rackets. These n places are connected by only n - 1 bidirectional roads because Paul's country does not believe in roads.

Paul has m employees. The i'th employee has an order to deliver rackets from place a_i to place b_i, making one trip from place a_i to place b_i every day, from day s_i to day t_i inclusive.

Paul's country believes in tolls. Every day, if any of Paul's employees uses the j'th road, Paul must pay an exorbitant toll of $1 for that road. Fortunately, each toll must only be paid once per day. In other words, if Paul pays the toll for road j for some day, then any number of his employees may use that road during that day with no extra cost.

Paul wants to know some details on the amount of money he needs to pay for these tolls, so he gives you q queries. For the jth query, he asks you how much money he needs to pay from day c_j to day d_j inclusive. Send help.

Eugene is inventing a new type of musical piece which has a few interesting properties.

A valid song of Type $$$N$$$ has the following properties:

• The song only contains the notes $$$A$$$ and $$$B$$$, all of equal length.
• The song will be repeated indefinitely. For example, if the song is $$$AAB$$$, then a musician will play $$$AABAABAABAABAAB...$$$ until Eugene falls asleep, which is once in a blue moon. This constitutes a performance.
• If we consider all the substrings of length $$$N$$$ of the performance, the performance will contain all $$$2^N$$$ possible strings of length $$$N$$$.
• The representation of the song is as short as possible.

Here are some examples of valid and invalid songs:

• $$$AB$$$ is a valid song of Type 1. It contains all substrings of length 1 ($$$A$$$ and $$$B$$$) and it is as short as possible.
• $$$ABAB$$$ is not a valid song of Type 1, because a shorter representation ($$$AB$$$) exists.
• $$$ABA$$$ is not a valid song of Type 2, because it is missing the substring $$$BB$$$.

Eugene would like you to create a special song of type $$$N$$$. He will specify two substrings $$$S$$$ and $$$T$$$ of length $$$N$$$. During a performance, the time between a performance of $$$S$$$ and the next performance of $$$T$$$ should be minimized. The performance of $$$S$$$ and $$$T$$$ can possibly overlap.

Formally, let $$$X$$$ be the set of indices at which a substring equal to $$$S$$$ begins, and let $$$Y$$$ be the set of indices at which a substring equal to $$$T$$$ begins. Then we want to minimize $$$\min\{y-x:x\in X\text{ and }y\in Y\text{ and }y\ge x\}$$$.

For example, for $$$N = 3$$$, $$$S=AAB$$$, and $$$S=ABA$$$, then $$$AABABBBA$$$ makes Eugene happy (because $$$AAB$$$ appears at position 1 and $$$ABA$$$ appears at position 2, so the time between their performances is only 1), but $$$AABBBABA$$$ makes Eugene sad (because $$$AAB$$$ appears at position 1, but $$$ABA$$$ appears at position 6, so the time between their performances is 5, which is not minimal)

Eugene will be very happy if you can help him write a special song of Type $$$N$$$ which minimizes the time from a performance of $$$S$$$ to a performance of $$$T$$$.

David and David are playing a game. This game is played with two piles of stones, which we name pile 1 and pile 2. First, David and David decide on some non-negative number $$$k$$$ which is called the tolerance. Then, David and David take turns making moves with David going first, and whoever cannot make a move loses. Each move is one of the following:

1. Remove any positive number of stones from one of the two piles
2. Remove $$$a$$$ stones from pile 1 and $$$b$$$ stones from pile 2, where $$$|a-b|\le k$$$ and $$$a,b \gt 0$$$

David and David will play $$$n$$$ games with different starting configurations. They want to check whether they played optimally, so for each game, they want you to tell them who should win with optimal play (and the answer is not print('David')).

Enegue is enjoying life as he strolls down a mildly overgrown path through the forest. At times, he could catch glimpses of the waning moon through gaps in the canopy. As the he followed the winding path through the undergrowth, Enegue suddenly felt the presence of a being somewhere just beyond his vision. Pausing momentarily, Enegue heard the rustling of leaves somewhere in the distance. Then, $$$n$$$ lanterns appeared in a row in front of Enegue.

"Who," a voice asked.

"Enegue the eyqs," responded Enegue, "who are you?"

The voice simply replied "who." Then, with a bright flash, Enegue saw the silhouette of an owl before all the lanterns went dark. After a brief moment of darkness, $$$k$$$ of the lanterns turned on again, and the owl was nowhere to be seen or heard. Suddenly struck by inspiration, Enegue decides to make you guess which $$$k$$$ of the $$$n$$$ lanterns are shining.

Enegue has a row of $$$n$$$ lanterns, of which $$$k$$$ are on. He wants you to guess which $$$k$$$ of the $$$n$$$ lanterns are on, but he will only answer your questions in a very cryptic fashion. For each question, you are allowed to choose any subset $$$S$$$ of the $$$n$$$ lanterns. Enegue will then count the number of lanterns on in $$$S$$$. Let this number be $$$x$$$, but Enegue will not tell you $$$x$$$. Instead, he will tell you the number of composite divisors of $$$x$$$. (eg. the composite divisors of 12 are $$$\{4,6,12\}$$$, so if $$$x=12$$$, then Enegue will answer with 3).

Since Enegue is a cactus, he will get bored after $$$2\times10^5$$$ questions, so you'll need to guess the $$$k$$$ lanterns that are on before he gets bored.

This is an interactive problem. Your program should use standard input and output to communicate with the judge's program.

You are allowed $$$2\times10^5$$$ queries. Each query should contain the character '?' and a string $$$S$$$ of length $$$n$$$, separated by one space. The string $$$S$$$ represents the chosen subset, where the $$$i$$$-th character of $$$S$$$ is a '1' if and only if the $$$i$$$-th lantern is in the subset.

The response to each query will be a single integer as described above. A response of $$$-1$$$ means the query is malformed or you have submitted more than $$$2\times10^5$$$ queries, in which case your program should exit immediately and get a "Wrong Answer".

Once you are ready to guess the $$$k$$$ lanterns, output a single line starting with the character '!' and a string $$$T$$$ of length $$$n$$$, separated by one space. The string $$$T$$$ represents the subset of $$$k$$$ lanterns in the same format as the string $$$S$$$ above. You will get "Accepted" if the guess is correct.

Welcome to ACM Class! ACM Class has s students (1 ≤ s ≤ 10⁶) of different ages, lined up along the wall to take attendance. The instructors Henry and Eugene each go from left to right and tick off everybody's name. They are bored of this menial task so they decide to play a game.

As Henry goes from left to right, he circles some students' names, following the rule that each student (after the first) is older than the last one he circled. Eugene circles some students' names so that each student is younger than the last one he circled. They are quite competitive, so using their they each circle as many names as possible, as they know every student's age.

They will be very happy if Henry circles exactly n (1 ≤ n ≤ s) names and Eugene circles exactly m (1 ≤ m ≤ s), their respective favourite numbers. Furthermore, they are quite high achievers so cumulatively they are hoping to circle lots of names. Thus n + m ≥ s - 50.

The class lines up differently every day. (Two lineups are different if at least one student is in a different position.) You'd like to keep Henry and Eugene happy for as long as possible to keep them from moving onto their next plan of starting World War 3. How long can you do this?

Jonathan and Jason are huge weeaboos who spend all their time at home watching anime and reading light novels. But one day, the Google restaurant "Charlie's" was closed to all employees due to an invasion of wild UBC interns, so Jonathan and Jason spontaneously decided to go bowling. Unfortunately, the wild UBC interns got to the Google bowling alley "Gooowling Galley" first, and all the lanes were out of order, although actually they were out of order for several months already and the entire building was just a front for Baidu's secret invasion, but that's a problem for another time...

Basically Jonathan and Jason somehow ended up at a mysterious and sketchy location in Jupiter, the bowling alley "Jowling Jalley". The Martians are very skilled bowlers, so instead of using a mere 10 pins arranged in a triangle, with sides of length 4, the Martians use up to 210 pins arranged in a triangle, with sides of length 4 ≤ n ≤ 20. Jonathan is very bad at bowling, so he forced Jason to play the "easy mode" variation with him, which is only popular among little children who watch cartoons.

In the "easy mode" variation, a hi-tech forcefield made out of op-amps and shafts under fatigue loading physically prevents the ball from knocking down any pins other than the first one, at the tip of the triangle. However, that first pin can still knock down the pins behind it, which can knock down more pins behind it, like a pile of Panago's. Basically, due to the hi-tech physics involved (it involves calculations of the von Mises stress using the Coulomb–Mohr criterion), the forcefield mysteriously warps causality in such a way that a pin can only be knocked down if both pins in front of it are also knocked down.

For example, after rolling the bowling ball, the first three positions below are possible, where o is an upright pin and x is a knocked-down pin. However, the last three positions are impossible, because at least one of the pins in front of pin X are not knocked down.

____o____ ____x____ ____x____ ____o____ ____x____ ____x____
___o_o___ ___x_o___ ___x_x___ ___X_o___ ___x_o___ ___x_o___
__o_o_o__ __x_o_o__ __x_x_o__ __o_o_o__ __o_X_o__ __x_o_o__
_o_o_o_o_ _o_o_o_o_ _x_o_o_o_ _o_o_o_o_ _o_o_o_o_ _x_X_o_o_

After every roll, a JeleVision (a telly made of jelly) displays a mysterious and sketchy animated video of a cartoon bowling ball knocking over cartoon bowling pins. This made Jonathan and Jason very excited because they are huge weeaboos. But they were also UBC students in the past, so naturally they wondered, how many animated videos did Jmazon (the company that owns the bowling alley "Jowling Jalley") have to produce? Jmazon has to produce exactly one animated video for every possible position that the pins can end up in, after Jonathan or Jason rolls the bowling ball once.

Eugene, the number theorist, is studying some quirky integers. An integer x is quirky if there is no integer k such that k² is a factor of x, and there is no prime number p ≥ 300 such that p divides x.

Eugene is playing with a sequence a₁, a₂, ..., a_n of quirky integers. Henry challenged Eugene to answer the following queries:

• Query of type 1 l r x: for all a_i in the range [l, r], change a_i to x if the sorted sequence of divisors of x is lexicographically smaller than the sorted sequence of divisors of a_i. It is guaranteed that x is quirky.

  For example, if Eugene had the integers 6, 10, 13 and the query 1 1 3 14, he would not change 6 or 10 since their sequences of divisors ( and respectively) are lexicographically smaller than 14's sequence , but he would change 13 to 14 since is lexicographically larger than .

• Query of type 2 l r: output modulo 10⁹ + 7.