Problem Solution Dytechlab Cup 2022

                                             Dytechlab Cup 2022

A. Ela Sorting Books

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Ela loves reading a lot, just like her new co-workers in DTL! On her first day after becoming an engineer in DTL, she is challenged by a co-worker to sort a heap of books into different compartments on the shelf.

n$n$ books must be split into k$k$ compartments on the bookshelf (n$n$ is divisible by k$k$). Each book is represented by a lowercase Latin letter from 'a' to 'y' inclusively, which is the beginning letter in the title of the book.

Ela must stack exactly nk$\frac{n}{k}$ books in each compartment. After the books are stacked, for each compartment indexed from 1$1$ to k$k$, she takes the minimum excluded (MEX) letter of the multiset of letters formed by letters representing all books in that compartment, then combines the resulting letters into a string. The first letter of the resulting string is the MEX letter of the multiset of letters formed by the first compartment, the second letter of the resulting string is the MEX letter of the multiset of letters formed by the second compartment, ... and so on. Please note, under the constraint of this problem, MEX letter can always be determined for any multiset found in this problem because 'z' is not used.

What is the lexicographically greatest resulting string possible that Ela can create?

A string a$a$ is lexicographically greater than a string b$b$ if and only if one of the following holds:

• b$b$ is a prefix of a$a$, but b≠a$b\ne a$;
• in the first position where a$a$ and b$b$ differ, the string a$a$ has a letter that appears later in the alphabet than the corresponding letter in b$b$.

The minimum excluded (MEX) letter of a multiset of letters is the letter that appears earliest in the alphabet and is not contained in the multiset. For example, if a multiset of letters contains 7$7$ letters 'b', 'a', 'b', 'c', 'e', 'c', 'f' respectively, then the MEX letter of this compartment is 'd', because 'd' is not included in the multiset, and all letters comes before 'd' in the alphabet, namely 'a', 'b' and 'c', are included in the multiset.

Input

Each test contains multiple test cases. The first line contains the number of test cases t$t$ (1≤t≤100$1\le t\le 100$). Description of the test cases follows.

The first line of each test case contains two integers n$n$ and k$k$ (1≤n≤200$1\le n\le 200$; 1≤k≤n$1\le k\le n$). It is guaranteed that n$n$ is divisible by k$k$.

The second line of each test case contains a string of n$n$ lowercase Latin letters from 'a' to 'y' inclusively. Each letter represents the starting letter of the title of a book in the initial heap.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 1000$1000$.

Output

For each test case, output a string of k$k$ letters which is the most optimal string that Ela can find.

Example

input

Copy

5
12 3
cabccadabaac
12 6
cabccadabaac
12 12
cabccadabaac
25 1
abcdefghijklmnopqrstuvwxy
10 5
bcdxedbcfg

output

Copy

edb
ccbbba
bbbbbaaaaaaa
z
aaaaa

Note

In the first test case, the books can be divided into 3$3$ compartments as below:

• the first compartment contains the books with indices 1,2,3,7$1,2,3,7$: multiset1={$multise{t}_1=\{$'c', 'a', 'b', 'd'}$\}$ →$\to$ MEX(multiset1)=$MEX(multise{t}_1)=$ 'e'
• the second compartment contains the books with indices 4,5,6,9$4,5,6,9$ : multiset2={$multise{t}_2=\{$'c', 'c', 'a', 'b'}$\}$ →$\to$ MEX(multiset2)=$MEX(multise{t}_2)=$ 'd'
• the third compartment contains the remaining books 8,10,11,12$8,10,11,12$ : multiset3={$multise{t}_3=\{$ 'a', 'a', 'a', 'c'}$\}$ →$\to$ MEX(multiset3)=$MEX(multise{t}_3)=$ 'b'

Therefore, the answer is 'edb'. It can be proven that there is no way that Ela can arrange the books so that it results in a lexicographically greater string.

B. Ela's Fitness and the Luxury Number

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

While working at DTL, Ela is very aware of her physical and mental health. She started to practice various sports, such as Archery, Yoga, and Football.

Since she started engaging in sports activities, Ela switches to trying a new sport on days she considers being "Luxury" days. She counts the days since she started these activities, in which the day she starts is numbered as day 1$1$. A "Luxury" day is the day in which the number of this day is a luxurious number.

An integer x$x$ is called a luxurious number if it is divisible by ⌊x−−√⌋$\lfloor \sqrt{x}\rfloor$.

Here ⌊r⌋$\lfloor r\rfloor$ denotes the "floor" of a real number r$r$. In other words, it's the largest integer not greater than r$r$.

For example: 8$8$, 56$56$, 100$100$ are luxurious numbers, since 8$8$ is divisible by ⌊8–√⌋=⌊2.8284⌋=2$\lfloor \sqrt{8}\rfloor =\lfloor 2.8284\rfloor =2$, 56$56$ is divisible ⌊56−−√⌋=⌊7.4833⌋=7$\lfloor \sqrt{56}\rfloor =\lfloor 7.4833\rfloor =7$, and 100$100$ is divisible by ⌊100−−−√⌋=⌊10⌋=10$\lfloor \sqrt{100}\rfloor =\lfloor 10\rfloor =10$, respectively. On the other hand 5$5$, 40$40$ are not, since 5$5$ are not divisible by ⌊5–√⌋=⌊2.2361⌋=2$\lfloor \sqrt{5}\rfloor =\lfloor 2.2361\rfloor =2$, and 40$40$ are not divisible by ⌊40−−√⌋=⌊6.3246⌋=6$\lfloor \sqrt{40}\rfloor =\lfloor 6.3246\rfloor =6$.

Being a friend of Ela, you want to engage in these fitness activities with her to keep her and yourself accompanied (and have fun together, of course). Between day l$l$ and day r$r$, you want to know how many times she changes the activities.

Input

Each test contains multiple test cases. The first line has the number of test cases t$t$ (1≤t≤10 000$1\le t\le 10000$). The description of the test cases follows.

The only line of each test case contains two integers l$l$ and r$r$ (1≤l≤r≤1018$1\le l\le r\le {10}^{18}$) — the intervals at which you want to know how many times Ela changes her sports.

Output

For each test case, output an integer that denotes the answer.

Example

input

Copy

5
8 19
8 20
119 121
1 100000000000000000
1234567891011 1000000000000000000

output

Copy

5
6
2
948683296
2996666667

Note

In the first test case, 5$5$ luxury numbers in range [8,19]$[8,19]$ are: 8,9,12,15,16$8,9,12,15,16$.

C. Ela and Crickets

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Ela likes Chess a lot. During breaks, she usually challenges her co-worker in DTL to some chess games. She's not an expert at classic chess, but she's very interested in Chess variants, where she has to adapt to new rules and test her tactical mindset to win the game.

The problem, which involves a non-standard chess pieces type that is described below, reads: given 3$3$ white crickets on a n⋅n$n\cdot n$ board, arranged in an "L" shape next to each other, there are no other pieces on the board. Ela wants to know with a finite number of moves, can she put any white cricket on the square on row x$x$, column y$y$?

An "L"-shape piece arrangement can only be one of the below:

For simplicity, we describe the rules for crickets on the board where only three white crickets are. It can move horizontally, vertically, or diagonally, but only to a square in some direction that is immediately after another cricket piece (so that it must jump over it). If the square immediately behind the piece is unoccupied, the cricket will occupy the square. Otherwise (when the square is occupied by another cricket, or does not exist), the cricket isn't allowed to make such a move.

See an example of valid crickets' moves on the pictures in the Note section.

Input

Each test contains multiple test cases. The first line contains the number of test cases t$t$ (1≤t≤104$1\le t\le {10}^4$). The description of the test cases follows.

The first line of each test case contains n$n$ (4≤n≤105$4\le n\le {10}^5$) — denotes the size of the chessboard.

The second line of each test case contains 6 numbers: r1$r_1$, c1$c_1$, r2$r_2$, c2$c_2$, r3$r_3$, c3$c_3$ (1≤r1,c1,r2,c2,r3,c3≤n$1\le r_1,c_1,r_2,c_2,r_3,c_3\le n$) — coordinates of the crickets. The input ensures that the three crickets are arranged in an "L" shape that the legend stated.

The third line of each test case contains 2 numbers: x$x$, y$y$ (1≤x,y≤n$1\le x,y\le n$) — coordinates of the target square.

Output

For each test case, print "YES" or "NO" to denotes whether Ela can put a cricket on the target square.

Example

input

Copy

6
8
7 2 8 2 7 1
5 1
8
2 2 1 2 2 1
5 5
8
2 2 1 2 2 1
6 6
8
1 1 1 2 2 1
5 5
8
2 2 1 2 2 1
8 8
8
8 8 8 7 7 8
4 8

output

Copy

YES
NO
YES
NO
YES
YES

Note

Here's the solution for the first test case. The red square denotes where the crickets need to reach. Note that in chess horizontals are counted from bottom to top, as well as on this picture.

D. Ela and the Wiring Wizard

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Ela needs to send a large package from machine 1$1$ to machine n$n$ through a network of machines. Currently, with the network condition, she complains that the network is too slow and the package can't arrive in time. Luckily, a Wiring Wizard offered her a helping hand.

The network can be represented as an undirected connected graph with n$n$ nodes, each node representing a machine. m$m$ wires are used to connect them. Wire i$i$ is used to connect machines ui$u_i$ and vi$v_i$, and has a weight wi$w_i$. The aforementioned large package, if going through wire i$i$, will move from machine ui$u_i$ to machine vi$v_i$ (or vice versa) in exactly wi$w_i$ microseconds. The Wiring Wizard can use his spell an arbitrary number of times. For each spell, he will choose the wire of index i$i$, connecting machine ui$u_i$ and vi$v_i$, and rewire it following these steps:

• Choose one machine that is connected by this wire. Without loss of generality, let's choose vi$v_i$.
• Choose a machine that is currently connecting to vi$v_i$ (including ui$u_i$), call it ti$t_i$. Disconnect the wire indexed i$i$ from vi$v_i$, then using it to connect ui$u_i$ and ti$t_i$.

The rewiring of wire i$i$ will takes wi$w_i$ microseconds, and the weight of the wire will not change after this operation. After a rewiring, a machine might have some wire connect it with itself. Also, the Wiring Wizard has warned Ela that rewiring might cause temporary disconnections between some machines, but Ela just ignores it anyway. Her mission is to send the large package from machine 1$1$ to machine n$n$ as fast as possible. Note that the Wizard can use his spell on a wire zero, one, or many times. To make sure the network works seamlessly while transferring the large package, once the package starts transferring from machine 1$1$, the Wiring Wizard cannot use his spell to move wires around anymore.

Ela wonders, with the help of the Wiring Wizard, what is the least amount of time needed to transfer the large package from machine 1$1$ to n$n$.

Input

Each test contains multiple test cases. The first line contains the number of test cases t$t$ (1≤t≤100$1\le t\le 100$). The description of the test cases follows.

The first line contains n$n$ and m$m$ (2≤n≤500$2\le n\le 500$, n−1≤m≤250000$n-1\le m\le 250000$), the number of nodes and number of wires, respectively.

For the next m$m$ lines, i$i$-th line will contains ui$u_i$, vi$v_i$ and wi$w_i$ (1≤ui,vi≤n$1\le u_i,v_i\le n$, 1≤wi≤109$1\le w_i\le {10}^9$) - the indices 2 machines that are connected by the i$i$-th edge and the weight of it.

It is guaranteed that the sum of n$n$ over all test cases does not exceed 500$500$ and the sum of m$m$ over all test cases does not exceed 250000$250000$. The graph in each test case is guaranteed to be connected, no self-loops, but it can contain multiple edges.

Output

For each test case, output one integer denotes the least amount of time needed to transfer the large package from machine 1$1$ to n$n$.

Example

input

Copy

3
8 9
1 2 3
6 4 5
3 5 6
6 1 3
7 4 4
3 8 4
2 3 3
7 8 5
4 5 2
4 5
1 2 1
2 4 1
3 4 1
3 1 1
1 3 2
8 8
4 6 92
7 1 65
6 5 43
6 7 96
4 3 74
4 8 54
7 4 99
2 5 22

output

Copy

9
2
154

Note

Here is the graph in the first test case in the sample input:

Ela can ask the Wiring Wizard to use his spell on wire with the index of 7$7$, which is connecting machines 2$2$ and 3$3$. Then, since the machine 8$8$ is connected to machine 3$3$, the Wiring Wizard can disconnect wire 7$7$ from machine 3$3$ and connect it to machine 8$8$ in 3$3$ microseconds (weight of wire 3$3$).

After that, the package can be sent from machine 1$1$ to machine 8$8$ in 6$6$ microseconds. Therefore, the answer is 3+6=9$3+6=9$ microseconds.

Here is the graph in the third test case in the sample input:

E. Ela Goes Hiking

time limit per test

2.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Ela likes to go hiking a lot. She loves nature and exploring the various creatures it offers. One day, she saw a strange type of ant, with a cannibalistic feature. More specifically, an ant would eat any ants that it sees which is smaller than it. Curious about this feature from a new creature, Ela ain't furious. She conducts a long, non-dubious, sentimental experiment.

She puts n$n$ cannibalistic ants in a line on a long wooden stick. Initially, the ants have the same weight of 1$1$. The distance between any two consecutive ants is the same. The distance between the first ant in the line to the left end and the last ant in the line to the right end is also the same as the distance between the ants. Each ant starts moving towards the left-end or the right-end randomly and equiprobably, at the same constant pace throughout the experiment. Two ants will crash if they are standing next to each other in the line and moving in opposite directions, and ants will change direction immediately when they reach the end of the stick. Ela can't determine the moving direction of each ant, but she understands very well their behavior when crashes happen.

• If a crash happens between two ants of different weights, the heavier one will eat the lighter one, and gain the weight of the lighter one. After that, the heavier and will continue walking in the same direction. In other words, if the heavier one has weight x$x$ and walking to the right, the lighter one has weight y$y$ and walking to the left (x>y$x>y$), then after the crash, the lighter one will diminish, and the heavier one will have weight x+y$x+y$ and continue walking to the right.
• If a crash happens between two ants with the same weight, the one walking to the left end of the stick will eat the one walking to the right, and then continue walking in the same direction. In other words, if one ant of weight x$x$ walking to the left, crashes with another ant of weight x$x$ walking to the right, the one walking to the right will disappear, and the one walking to the left will have to weight 2x$2x$ and continue walking to the left.

Please, check the example in the "Note" section, which will demonstrate the ants' behavior as above.

We can prove that after a definite amount of time, there will be only one last ant standing. Initially, each ant can randomly and equiprobably move to the left or the right, which generates 2n$2^n$ different cases of initial movements for the whole pack. For each position in the line, calculate the probability that the ant begins in that position and survives. Output it modulo 109+7${10}^9+7$.

Formally, let M=109+7$M={10}^9+7$. It can be shown that the answer can be expressed as an irreducible fraction pq$\frac{p}{q}$, where p$p$ and q$q$ are integers and q≢0(modM)$q\not\equiv 0(\mathrm{mod}M)$. Output the integer equal to p⋅q−1modM$p\cdot q^{-1}modM$. In other words, output such an integer x$x$ that 0≤x<M$0\le x<M$ and x⋅q≡p(modM)$x\cdot q\equiv p(\mathrm{mod}M)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases t$t$ (1≤t≤103$1\le t\le {10}^3$). The description of the test cases follows.

The only line of each test contains an integer n$n$ (1≤n≤106$1\le n\le {10}^6$) — the number of ants in the experiment.

It is guaranteed that the sum of n$n$ in all tests will not exceed 106${10}^6$.

Output

For each test, print n$n$ lines. i$i$-th line contains a single number that denotes the survival probability of the i$i$-th ant in the line modulo 109+7${10}^9+7$.

Example

input

Copy

3
4
5
2

output

Copy

0
250000002
250000002
500000004
0
250000002
250000002
250000002
250000002
0
1

Note

Here is the example of 6$6$ ants moving on the branch. An ant's movement will be denoted by either a character L$L$ or R$R$. Initially, the pack of ants on the branch will move as RLRRLR$RLRRLR$. Here's how the behavior of the pack demonstrated:

Initially, the ants are positioned as above.

After a while, the ant with index 2$2$ (walking to the left) will crash with the ant with index 1$1$ (walking to the right). The two ants have the same weight, therefore, ant 2$2$ will eat ant 1$1$ and gain its weight to 2$2$. The same thing happens with ant 5$5$ and ant 4$4$.

The ant 6$6$ will walk to the end of the stick, therefore changing its direction.

After that, the ant with index 5$5$ will crash with the ant with index 3$3$. Since ant 5$5$ is more heavy (weight=2$2$) than ant 3$3$ (weight=1$1$), ant 5$5$ will eat ant 3$3$ and gain its weight to 3$3$.

Ant 2$2$ will walk to the end of the stick, therefore changing its direction.

After that, the ant with index 5$5$ will crash with the ant with index 2$2$. Since ant 5$5$ is more heavy (weight=3$3$) than ant 2$2$ (weight=2$2$), ant 5$5$ will eat ant 2$2$ and gain its weight to 5$5$.

Lastly, after ant 5$5$ walk to the end of the branch and changes its direction, ant 5$5$ will eat ant 6$6$ and be the last ant standing.

F. Ela and Prime GCD

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

After a long, tough, but fruitful day at DTL, Ela goes home happily. She entertains herself by solving Competitive Programming problems. She prefers short statements, because she already read too many long papers and documentation at work. The problem of the day reads:

You are given an integer c$c$. Suppose that c$c$ has n$n$ divisors. You have to find a sequence with n−1$n-1$ integers [a1,a2,...an−1]$[a_1,a_2,...a_{n-1}]$, which satisfies the following conditions:

• Each element is strictly greater than 1$1$.
• Each element is a divisor of c$c$.
• All elements are distinct.
• For all 1≤i<n−1$1\le i<n-1$, gcd(ai,ai+1)$gcd(a_i,a_{i+1})$ is a prime number.

In this problem, because c$c$ can be too big, the result of prime factorization of c$c$ is given instead. Note that gcd(x,y)$gcd(x,y)$ denotes the greatest common divisor (GCD) of integers x$x$ and y$y$ and a prime number is a positive integer which has exactly 2$2$ divisors.

Input

The first line contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) - the number of test cases.

The first line of each test case contains one integer m$m$ (1≤m≤16$1\le m\le 16$) - the number of prime factor of c$c$.

The second line of each test case contains m$m$ integers b1,b2,…,bm$b_1,b_2,\dots ,b_m$ (1≤bi<220$1\le b_i<2^{20}$) — exponents of corresponding prime factors of c$c$, so that c=pb11⋅pb22⋅…⋅pbmm$c=p_1^{b_1}\cdot p_2^{b_2}\cdot \dots \cdot p_m^{b_m}$ and n=(b1+1)(b2+1)…(bm+1)$n=(b_1+1)(b_2+1)\dots (b_m+1)$ hold. pi$p_i$ is the i$i$-th smallest prime number.

It is guaranteed that the sum of n⋅m$n\cdot m$ over all test cases does not exceed 220$2^{20}$.

Output

Print the answer for each test case, one per line. If there is no sequence for the given c$c$, print −1$-1$.

Otherwise, print n−1$n-1$ lines. In i$i$-th line, print m$m$ space-separated integers. The j$j$-th integer of i$i$-th line is equal to the exponent of j$j$-th prime number from ai$a_i$.

If there are multiple answers, print any of them.

Example

input

Copy

5
2
1 1
1
1
3
1 1 1
1
4
2
2 1

output

Copy

0 1 
1 1 
1 0 
1 
0 1 1 
0 0 1 
1 0 1 
1 1 0 
0 1 0 
1 1 1 
1 0 0 
-1
2 0 
1 1 
0 1 
2 1 
1 0 

Note

In each test case, the values of c$c$ are 6$6$, 2$2$, 30$30$, 16$16$, and 12$12$ in that order.

In the first test case, 1$1$, 2$2$, 3$3$, 6$6$ are divisors of 6$6$. Here, sequences [2,6,3]$[2,6,3]$ and [3,6,2]$[3,6,2]$ can be answer. Permutation [3,2,6]$[3,2,6]$ is invalid because gcd(a1,a2)=1$gcd(a_1,a_2)=1$ is not a prime number.

In the forth test case, 1$1$, 2$2$, 4$4$, 8$8$, 16$16$ are divisors of 16$16$. Among the permutation of sequence [2,4,8,16]$[2,4,8,16]$, no valid answer exist.

G. Ela Takes Dancing Class

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

DTL engineers love partying in the weekend. Ela does, too! Unfortunately, she didn't know how to dance yet. Therefore, she decided to take a dancing class.

There are n$n$ students in the dancing class, including Ela. In the final project, n$n$ students will participate in a choreography described below.

n$n$ students are positioned on the positive side of the Ox$Ox$-axis. The i$i$-th dancer is located at ai>0$a_i>0$. Some dancers will change positions during the dance (we'll call them movable dancers), and others will stay in the same place during a choreography (we'll call them immovable dancers). We distinguish the dancers using a binary string s$s$ of length n$n$: if si$s_i$ equals '1', then the i$i$-th dancer is movable, otherwise the i$i$-th dancer is immovable.

Let's call the "positive energy value" of the choreography d>0$d>0$. The dancers will perform "movements" based on this value.

Each minute after the dance begins, the movable dancer with the smallest x$x$-coordinate will start moving to the right and initiate a "movement". At the beginning of the movement, the dancer's energy level will be initiated equally to the positive energy value of the choreography, which is d$d$. Each time they move from some y$y$ to y+1$y+1$, the energy level will be decreased by 1$1$. At some point, the dancer might meet other fellow dancers in the same coordinates. If it happens, then the energy level of the dancer will be increased by 1$1$. A dancer will stop moving to the right when his energy level reaches 0$0$, and he doesn't share a position with another dancer.

The dancers are very well-trained, and each "movement" will end before the next minute begins.

To show her understanding of this choreography, Ela has to answer q$q$ queries, each consisting of two integers k$k$ and m$m$. The answer to this query is the coordinate of the m$m$-th dancer of both types from the left at k$k$-th minute after the choreography begins. In other words, denote xk,1,xk,2,…,xk,n$x_{k,1},x_{k,2},\dots ,x_{k,n}$ as the sorted coordinates of the dancers at k$k$-th minute from the beginning, you need to print xk,m$x_{k,m}$.

Input

The first line contains three integers n$n$, d$d$ and q$q$ (1≤n≤105$1\le n\le {10}^5$; 1≤d≤109$1\le d\le {10}^9$; 1≤q≤105$1\le q\le {10}^5$) — the number of dancers, the positive energy value of the choreography, and the number of queries.

The second line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤a1<a2<⋯<an≤109$1\le a_1<a_2<\cdots <a_n\le {10}^9$) — the coordinates of each dancer.

The third line contains a binary string s$s$ of length n$n$ — the movability of each dancer. Each character is either '0' or '1'. It is guaranteed that s$s$ contains at least one character '1'.

Then q$q$ lines follow, the i$i$-th of them contains two integers ki$k_i$ and mi$m_i$ (1≤ki≤109$1\le k_i\le {10}^9$, 1≤mi≤n$1\le m_i\le n$) — the content of each query.

Output

Output q$q$ lines, each contains a single integer — the answer for the corresponding query.

Examples

input

Copy

4 3 8
1 3 6 7
1011
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4

output

Copy

3
5
6
7
3
6
7
10

input

Copy

1 1 5
2
1
1 1
2 1
3 1
4 1
5 1

output

Copy

3
4
5
6
7

Note

Let's consider the first example test case.

In the first minute, 1$1$ is the lowest coordinate between movable dancers. The energy level is initiated with 3$3$. Then the following happens:

• The dancer moves from 1$1$ to 2$2$. The energy level decreased to 2$2$.
• The dancer moves from 2$2$ to 3$3$. The energy level decreased to 1$1$, then increased to 2$2$ when she met another dancer at 3$3$.
• The dancer moves from 3$3$ to 4$4$. The energy level decreased to 1$1$.
• The dancer moves from 4$4$ to 5$5$. The energy level decreased to 0$0$.

At the end of the first minute, the sorted coordinates of the dancers become [3,5,6,7]$[3,5,6,7]$, and their respective movability is '0111'.

In the second minute, 5$5$ is the lowest coordinate between movable dancers. The energy level is initiated with 3$3$. Then the following happens:

• The dancer moves from 5$5$ to 6$6$. The energy level decreased to 2$2$, then increased to 3$3$ when she met another dancer at 6$6$.
• The dancer moves from 6$6$ to 7$7$. The energy level decreased to 2$2$, then increased to 3$3$ when she met another dancer at 7$7$.
• The dancer moves from 7$7$ to 8$8$. The energy level decreased to 2$2$.
• The dancer moves from 8$8$ to 9$9$. The energy level decreased to 1$1$.
• The dancer moves from 9$9$ to 10$10$. The energy level decreased to 0$0$.

At the end of the second minute, the sorted coordinates of the dancers become [3,6,7,10]$[3,6,7,10]$, and their respective movability is '0111'.