Juan just recently started studying in JUST (Juan University for Sarcasm and Technology) and obviously Abd told him he should try Alfino, the most legendary sandwich on planet earth.

Juan is very social, so he already made infinitely many friends.

He wants to buy his friends Alfinos, an Alfino costs $$$c$$$ JOD. and he has $$$m$$$ JOD.

How many friends can he buy an Alfino for?

Paulo is always trying to sabotage the Juan group, this time he is trying to sabotage Mateo's precious strings.

Mateo has a small string $$$T$$$ consisting of distinct characters, and a big string $$$S$$$ consisting of the same characters as $$$T$$$.

Let's say that a pair of strings $$$(A, B)$$$ is good if we can duplicate the characters of $$$B$$$ a finite number of times without changing their order so that $$$A = B$$$, e.g, $$$(aabb, ab), (aabbbbbccc, abc)$$$ are good pairs, $$$(abcccc, ab), (acccb, abc)$$$ are not.

Let's define $$$cost(A, B)$$$ as the minimum number of swaps of adjacent characters in $$$A$$$ so that $$$(A, B)$$$ becomes a good pair.

Paulo knows Mateo will do anything to make the pair a good pair, Paulo can reorder the characters in $$$S$$$ and $$$T$$$ as he wishes, tell him what is the best pair $$$(S', T')$$$ such that $$$cost(S', T')$$$ is maximum.

It's guaranteed that the $$$(S, T)$$$ can be made a good pair.

Paulo was teaching Ahmad that if he was ever mad he should just flip some tables, but Paulo did not listen to his own advice, and now he is in prison, so Ahmad is MAD!

You're given a binary string $$$S$$$, the $$$i_{th}$$$ character is the state of the $$$i_{th}$$$ table either $$$1$$$ flipped, or $$$0$$$ not flipped.

Every time Ahmad wants to flip some tables, he will chose some pair $$$(l, r)$$$ uniformly at random from all the pairs such that $$$(1 \leq l \leq r \leq |S|)$$$, and flip every table $$$i$$$ such that $$$(l \leq i \leq r)$$$.

You have to answer $$$Q$$$ queries:

• $$$1$$$ $$$i$$$: flip the $$$i_{th}$$$ table.
• $$$2$$$ $$$k$$$: Ahmad will flip some tables $$$k$$$ $$$(k \leq 200)$$$ times, what is the expected number of tables that are flipped at the end of $$$k$$$ flips?

Note: when Ahmad flips some tables, every time he flips he will choose $$$(l, r)$$$ again.

Note: only query of type $$$1$$$ will change the string, meaning Ahmad's flips will not have any effect on the string.

This is the easy version of the problem. The difference is that, $$$L = \inf$$$.

Eduardo has been looking for Juan for a long time, he finally found out that Juan is on some mountain The Horse Land but before he heads looking for him there he asked Ahmad for help, but he is too busy so it's your responsibility to help him.

Eduardo knows that The Horse Land is $$$n$$$ lands connected by $$$n - 1$$$ roads and there is a unique path between every two lands.

Furthermore, each land has a height $$$a_i$$$, Eduardo will travel from $$$u$$$ to $$$v$$$, but he can only do that if the multiplication of the height of the nodes on the way is a perfect square.

In a formal way let $$$p_1, ..., p_k$$$ the lands in the simple path from $$$u$$$ to $$$v$$$, where $$$p_1 = u$$$ and $$$p_k = v$$$, $$$\prod_{i=1}^{k} a_{p_i}$$$ should be a perfect square.

Eduardo hates surprises, so he will ask you about $$$q$$$ scenarios:

• $$$u$$$ $$$v$$$: what is the minimum number of operations so that the multiplication on the simple path from $$$u$$$ to $$$v$$$ is a perfect square? In one operation, you can choose a land $$$i$$$ and multiply its height by some number $$$1 \leq x \leq L$$$.

This is the hard version of the problem. The difference is that $$$L$$$ will be in the input.

Eduardo has been looking for Juan for a long time, he finally found out that Juan is on some mountain The Horse Land but before he heads looking for him there he asked Ahmad for help, but he is too busy so it's your responsibility to help him.

Eduardo knows that The Horse Land is $$$n$$$ lands connected by $$$n - 1$$$ roads and there is a unique path between every two lands.

Furthermore, each land has a height $$$a_i$$$, Eduardo will travel from $$$u$$$ to $$$v$$$, but he can only do that if the multiplication of the height of the nodes on the way is a perfect square.

In a formal way let $$$p_1, ..., p_k$$$ the lands in the simple path from $$$u$$$ to $$$v$$$, where $$$p_1 = u$$$ and $$$p_k = v$$$, $$$\prod_{i=1}^{k} a_{p_i}$$$ should be a perfect square.

Eduardo hates surprises, so he will ask you about $$$q$$$ scenarios:

• $$$u$$$ $$$v$$$: what is the minimum number of operations so that the multiplication on the simple path from $$$u$$$ to $$$v$$$ is a perfect square? In one operation, you can choose a land $$$i$$$ and multiply its height by some number $$$1 \leq x \leq L$$$.

Mateo and Juan are trapped in a maze, and they can only escape the maze if they draw a certain pattern on it, so they are desperate for your help!

The maze is represented as a grid $$$G$$$ of size $$$n \times m$$$, each cell is a lowercase English letter, you can move from a cell to any other cell adjacent to it (diagonally, horizontally and vertically), you can visit the cell more than once, but you can't move to the same cell that you are currently on.

Let's define a pattern of a path as the concatenation of the characters on the cells on that path.

In a more formal way let the cells on the path be $$$P = [(r_1, c_1), (r_2, c_2), ..., (r_k, c_k)]$$$ such that for each $$$2 \leq i \leq k$$$ $$$P_i \neq P_{i - 1}$$$ that then the pattern is $$$S = G_{r_1c_1}G_{r_2c_2}...G_{r_kc_k}$$$.

Mateo and Juan are studying $$$q$$$ patterns, for each one they ask you if they can draw that pattern on the maze.

Carlo is trying to escape the barn, so he must find a password to the door.

Given a list $$$s$$$ of $$$n$$$ small strings, a password is acceptable if it's a subsequence of one of the strings in the list.

Given $$$m$$$ possible password, for each password, you should tell Carlo if it's acceptable or not.

Man is trying so hard to become the boss, so he is always trying to beat Juan in any game, this time he came up with the following game.

Man will give Juan two integers $$$n$$$ and $$$m$$$, for Juan to win he should create an array $$$a$$$ with the following constrains:

• The length of the array is $$$n$$$.
• For every element in the array $$$1 \leq a_i \leq m$$$ must hold.
• There should be no subarray where the sum is divisible my $$$m$$$, in a more formal way there is no $$$i$$$ and $$$j$$$ $$$(1 \leq i \leq j \leq n)$$$ such that $$${\sum_{k = i}^j a_k} \equiv 0 \mod m$$$.

Again, Ahmad is really busy so you should help Juan create the array or tell him it's not possible.

Man gave Abd a string $$$s$$$ of length $$$n$$$, and he asked him a very hard problem. Let's say that a string is good if its characters can be reordered so that it becomes a palindrome.

You must do the following operation exactly once: choose some index $$$i$$$ $$$(1 \leq i \leq n - 1)$$$ and split the string into two strings $$$A = s_1, ..., s_i$$$ and $$$B = s_{i+1}, ..., s_n$$$.

In how many ways can you do the operation such that the resulting strings are both good strings.

Juan stayed up late thinking of how to steal Ahmad's problem, and he figured if he just changed one character no one will know.

You are given an array $$$a$$$ of $$$n$$$ integers.

Let's define a function $$$JCD(l, r)$$$ as the greatest common divisor of the sub array $$$(a_l, .., a_r)$$$, i.e $$$GCD(a_l, a_{l + 1}, ..., a_r)$$$.

Calculate $$${\sum_{l = 1}^n {\sum_{r = l}^n JCD(l, r)}}$$$, since the answer can be very large output it modulo $$$10^9 + 7$$$.

Pèppito is a bird stuck on a tree because he can't fly, he travels only on the tree by walking on branches.

Pèppito's tree is a tree of $$$n$$$ vertices, the $$$i_{th}$$$ node has an integer $$$a_i$$$, he gets bored sometimes, so he came up with this problem:

Given four integers $$$u$$$ $$$v$$$ $$$l$$$ $$$r$$$: let's define $$$f(x)$$$ as the number of occurrences of $$$x$$$ on the simple path between nodes $$$u$$$ and $$$v$$$, calculate $$$\sum_{x = l}^r f(x)^2$$$.

Pèppito thought that it might be too easy to solve it, so you have to answer $$$q$$$ of these problems.

You are given $$$N$$$ points on a 2D plane, what is the minimum area of a rectangle that covers all the points and one of its sides is parallel to the x-axis and the other to the y-axis.