版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

仓库源文站点原文


title: "比赛记录 - CodeCraft-22 and Codeforces Round #795 (Div. 2) (A-D)" categories:


比赛链接

<!-- more -->

A - Beat The Odds

Given a sequence $a_1, a_2, \ldots, a_n$, find the minimum number of elements to remove from the sequence such that after the removal, the sum of every $2$ consecutive elements is even

Input

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

The first line of each test case contains a single integer $n$ ($3 \le n \le 10^5$)

The second line of each test case contains $n$ integers $a_1, a_2,\dots,a_n$ ($1\leq a_i\leq10^9$) — elements of the sequence

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$

Output

For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every $2$ consecutive elements is even

Example

input

2
5
2 4 3 6 8
6
3 5 9 7 1 3

output

1
0

Note

In the first test case, after removing $3$, the sequence becomes $[2,4,6,8]$. The pairs of consecutive elements are ${[2, 4], [4, 6], [6, 8]}$. Each consecutive pair has an even sum now. Hence, we only need to remove $1$ element to satisfy the condition asked

In the second test case, each consecutive pair already has an even sum so we need not remove any element

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:CodeForces_1691A CodeForces/1691A/0.cpp %} </details>

B - Shoe Shuffling

A class of students got bored wearing the same pair of shoes every day, so they decided to shuffle their shoes among themselves. In this problem, a pair of shoes is inseparable and is considered as a single object

There are $n$ students in the class, and you are given an array $s$ in non-decreasing order, where $s_i$ is the shoe size of the $i$-th student. A shuffling of shoes is valid only if no student gets their own shoes and if every student gets shoes of size greater than or equal to their size

You have to output a permutation $p$ of ${1,2,\ldots,n}$ denoting a valid shuffling of shoes, where the $i$-th student gets the shoes of the $p_i$-th student ($p_i \ne i$). And output $-1$ if a valid shuffling does not exist

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array)

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Description of the test cases follows

The first line of each test case contains a single integer $n$ ($1\leq n\leq10^5$) — the number of students

The second line of each test case contains $n$ integers $s_1, s_2,\ldots,s_n$ ($1\leq s_i\leq10^9$, and for all $1\le i<n$, $si\le s{i+1}$) — the shoe sizes of the students

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$

Output

For each test case, print the answer in a single line using the following format

If a valid shuffling does not exist, print the number $-1$ as the answer

If a valid shuffling exists, print $n$ space-separated integers — a permutation $p$ of $1,2,\ldots,n$ denoting a valid shuffling of shoes where the $i$-th student gets the shoes of the $p_i$-th student. If there are multiple answers, then print any of them

Example

input

2
5
1 1 1 1 1
6
3 6 8 13 15 21

output

5 1 2 3 4
-1

Note

In the first test case, any permutation $p$ of $1,\ldots,n$ where $p_i\ne i$ would represent a valid shuffling since all students have equal shoe sizes, and thus anyone can wear anyone's shoes

In the second test case, it can be shown that no valid shuffling is possible

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:CodeForces_1691B CodeForces/1691B/0.cpp %} </details>

C - Sum of Substrings

You are given a binary string $s$ of length $n$

Let's define $d_i$ as the number whose decimal representation is $si s{i+1}$ (possibly, with a leading zero). We define $f(s)$ to be the sum of all the valid $di$. In other words, $f(s) = \sum\limits{i=1}^{n-1} d_i$

For example, for the string $s = 1011$:

In one operation you can swap any two adjacent elements of the string. Find the minimum value of $f(s)$ that can be achieved if at most $k$ operations are allowed

Input

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

First line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $0 \le k \le 10^9$) — the length of the string and the maximum number of operations allowed

The second line of each test case contains the binary string $s$ of length $n$, consisting of only zeros and ones

It is also given that sum of $n$ over all the test cases doesn't exceed $10^5$

Output

For each test case, print the minimum value of $f(s)$ you can obtain with at most $k$ operations

Example

input

3
4 0
1010
7 1
0010100
5 2
00110

output

21
22
12

Note

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:CodeForces_1691C CodeForces/1691C/0.cpp %} </details>

D - Max GEQ Sum

You are given an array $a$ of $n$ integers. You are asked to find out if the inequality

$$ \max(ai, a{i + 1}, \ldots, a{j - 1}, a{j}) \geq ai + a{i + 1} + \dots + a{j - 1} + a{j} $$

holds for all pairs of indices $(i, j)$, where $1 \leq i \leq j \leq n$

Input

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the size of the array

The next line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$)

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$

Output

For each test case, on a new line output "YES" if the condition is satisfied for the given array, and "NO" otherwise. You can print each letter in any case (upper or lower)

Example

input

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

output

YES
YES
NO

Note

In test cases $1$ and $2$, the given condition is satisfied for all $(i, j)$ pairs

In test case $3$, the condition isn't satisfied for the pair $(1, 2)$ as $\max(2, 3) < 2 + 3$

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:CodeForces_1691D CodeForces/1691D/0.cpp %} </details>

E - Number of Groups

You are given $n$ colored segments on the number line. Each segment is either colored red or blue. The $i$-th segment can be represented by a tuple $(c_i, l_i, r_i)$. The segment contains all the points in the range $[l_i, r_i]$, inclusive, and its color denoted by $c_i$:

We say that two segments of different colors are connected, if they share at least one common point. Two segments belong to the same group, if they are either connected directly, or through a sequence of directly connected segments. Find the number of groups of segments

Input

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

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of segments

Each of the next $n$ lines contains three integers $c_i, l_i, r_i$ ($0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9$), describing the $i$-th segment

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$

Output

For each test case, print a single integer $k$, the number of groups of segments

Example

input

2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4

output

2
3

Note

In the first example there are $5$ segments. The segments $1$ and $2$ are connected, because they are of different colors and share a point. Also, the segments $2$ and $3$ are connected, and so are segments $4$ and $5$. Thus, there are two groups: one containing segments ${1, 2, 3}$, and the other one containing segments ${4, 5}$

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> </details>

F - K-Set Tree

You are given a tree $G$ with $n$ vertices and an integer $k$. The vertices of the tree are numbered from $1$ to $n$

For a vertex $r$ and a subset $S$ of vertices of $G$, such that $|S| = k$, we define $f(r, S)$ as the size of the smallest rooted subtree containing all vertices in $S$ when the tree is rooted at $r$. A set of vertices $T$ is called a rooted subtree, if all the vertices in $T$ are connected, and for each vertex in $T$, all its descendants belong to $T$

You need to calculate the sum of $f(r, S)$ over all possible distinct combinations of vertices $r$ and subsets $S$, where $|S| = k$. Formally, compute the following:

$$ \sum{r \in V} \sum{S \subseteq V, |S| = k} f(r, S), $$

where $V$ is the set of vertices in $G$

Output the answer modulo $10^9 + 7$

Input

The first line contains two integers $n$ and $k$ ($3 \le n \le 2 \cdot 10^5$, $1 \le k \le n$)

Each of the following $n - 1$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$), denoting an edge between vertex $x$ and $y$

It is guaranteed that the given edges form a tree

Output

Print the answer modulo $10^9 + 7$

Examples

input

3 2
1 2
1 3

output

25

input

7 2
1 2
2 3
2 4
1 5
4 6
4 7

output

849

Note

The tree in the second example is given below:

We have $21$ subsets of size $2$ in the given tree. Hence,

$$ S \in \left{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7} \right}. $$

And since we have $7$ vertices, $1 \le r \le 7$. We need to find the sum of $f(r, S)$ over all possible pairs of $r$ and $S$

Below we have listed the value of $f(r, S)$ for some combinations of $r$ and $S$

代码参考

<details open> <summary><font color='orange'>Show code</font></summary> </details>