# Codeforces Round #606 (Div. 2)

## A. Happy Birthday, Polycarp!

time limit per test1 second memory limit per test256 megabytes

Hooray! Polycarp turned n years old! The Technocup Team sincerely congratulates Polycarp!

Polycarp celebrated all of his n birthdays: from the 1-th to the n-th. At the moment, he is wondering: how many times he turned beautiful number of years?

According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: 1, 77, 777, 44 and 999999. The following numbers are not beautiful: 12, 11110, 6969 and 987654321.

Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).

Help Polycarpus to find the number of numbers from 1 to n (inclusive) that are beautiful.

Input

The first line contains an integer $$t (1 \le t \le 10^4)$$ — the number of test cases in the input. Then t test cases follow.

Each test case consists of one line, which contains a positive integer $$n (1 \le n \le 10^9)$$ — how many years Polycarp has turned.

Output

Print t integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between 1 and n, inclusive.

Exampleinput

6
18
1
9
100500
33
1000000000

output

10
1
9
45
12
81

Note

In the first test case of the example beautiful years are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 11.

#### 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
void solve(){
scanf("%d",&n);
int ans=0;
rep(i,1,100) rep(j,1,9){
ll tmp=0;
rep(k,1,i) tmp=tmp*10+j;
if(tmp>n) return (void)printf("%d\n",ans);
ans++;
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## B. Make Them Odd

time limit per test3 seconds memory limit per test256 megabytes

There are n positive integers $$a_1, a_2, \dots, a_n$$. For the one move you can choose any even value c and divide by two all elements that equal c.

For example, if a=[6,8,12,6,3,12] and you choose c=6, and a is transformed into a=[3,8,12,3,3,12] after the move.

You need to find the minimal number of moves for transforming a to an array of only odd integers (each element shouldn’t be divisible by 2).

Input

The first line of the input contains one integer $$t (1 \le t \le 10^4)$$ — the number of test cases in the input. Then t test cases follow.

The first line of a test case contains $$n (1 \le n \le 2\cdot10^5)$$ — the number of integers in the sequence a. The second line contains positive integers $$a_1, a_2, \dots, a_n (1 \le a_i \le 10^9)$$.

The sum of n for all test cases in the input doesn’t exceed $$2\cdot10^5$$.

Output

For t test cases print the answers in the order of test cases in the input. The answer for the test case is the minimal number of moves needed to make all numbers in the test case odd (i.e. not divisible by 2).

Exampleinput

4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7

output

4
10
4
0

Note

In the first test case of the example, the optimal sequence of moves can be as follows:

• before making moves a=[40, 6, 40, 3, 20, 1];
• choose c=6;
• now a=[40, 3, 40, 3, 20, 1];
• choose c=40;
• now a=[20, 3, 20, 3, 20, 1];
• choose c=20;
• now a=[10, 3, 10, 3, 10, 1];
• choose c=10;
• now a=[5, 3, 5, 3, 5, 1] — all numbers are odd.

Thus, all numbers became odd after 4 moves. In 3 or fewer moves, you cannot make them all odd.

#### 最优策略肯定是先除大的，set搞一搞就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,a[maxn];
void solve(){
scanf("%d",&n);
set<int,greater<int> > s;
int ans=0;
rep(i,1,n){
scanf("%d",&a[i]);
if(a[i]%2==0) s.insert(a[i]);
}
while(!s.empty()){
auto it=s.begin();int u=*it,v=u/2;
if(v%2==0) s.insert(v);
s.erase(it);ans++;
}
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## C. As Simple as One and Two

time limit per test3 seconds memory limit per test256 megabytes

You are given a non-empty string $$s=s_1s_2\dots s_n$$, which consists only of lowercase Latin letters. Polycarp does not like a string if it contains at least one string “one” or at least one string “two” (or both at the same time) as a substring. In other words, Polycarp does not like the string s if there is an integer$$j (1 \le j \le n-2)$$, that$$s_{j}s_{j+1}s_{j+2}=”one”$$or $$s_{j}s_{j+1}s_{j+2}=”two”$$.

For example:

• Polycarp does not like strings “oneee”, “ontwow”, “twone” and “oneonetwo” (they all have at least one substring “one” or “two”),
• Polycarp likes strings “oonnee”, “twwwo” and “twnoe” (they have no substrings “one” and “two”).

Polycarp wants to select a certain set of indices (positions) and remove all letters on these positions. All removals are made at the same time.

For example, if the string looks like s=”onetwone”, then if Polycarp selects two indices 3 and 6, then “onetwone” will be selected and the result is “ontwne”.

What is the minimum number of indices (positions) that Polycarp needs to select to make the string liked? What should these positions be?

Input

The first line of the input contains an integer $$t (1 \le t \le 10^4)$$ — the number of test cases in the input. Next, the test cases are given.

Each test case consists of one non-empty string s. Its length does not exceed $$1.5\cdot10^5$$. The string s consists only of lowercase Latin letters.

It is guaranteed that the sum of lengths of all lines for all input data in the test does not exceed $$1.5\cdot10^6$$.

Output

Print an answer for each test case in the input in order of their appearance.

The first line of each answer should contain $$r (0 \le r \le |s|)$$ — the required minimum number of positions to be removed, where |s| is the length of the given line. The second line of each answer should contain r different integers — the indices themselves for removal in any order. Indices are numbered from left to right from 1 to the length of the string. If r=0, then the second line can be skipped (or you can print empty). If there are several answers, print any of them.

Examplesinput

4
onetwone
testme
oneoneone
twotwo


output

2
6 3
0

3
4 1 7
2
1 4


input

10
onetwonetwooneooonetwooo
two
one
twooooo
ttttwo
ttwwoo
ooone
onnne
oneeeee
oneeeeeeetwooooo


output

6
18 11 12 1 6 21
1
1
1
3
1
2
1
6
0

1
4
0

1
1
2
1 11


Note

In the first example, answers are:

• “onetwone”,
• “testme” — Polycarp likes it, there is nothing to remove,
• oneoneone”,
• twotwo”.

In the second example, answers are:

• onetwonetwooneooonetwooo”,
• two”,
• one”,
• twooooo”,
• “ttttwo”,
• “ttwwoo” — Polycarp likes it, there is nothing to remove,
• “ooone”,
• “onnne” — Polycarp likes it, there is nothing to remove,
• oneeeee”,
• oneeeeeeetwooooo”.

#### 两种情况，首先处理形如”twone”的，显然去掉o就好了；再就是单独的”one”或者”two”的情况，去掉之间的就好了(因为去掉两边的话可能会组成新的)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
char s[maxn];
int n;
void solve(){
scanf("%s",s+1);
n=strlen(s+1);
vector<int> ans;
rep(i,1,n-4) if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o'&&s[i+3]=='n'&&s[i+4]=='e'){
ans.pb(i+2);s[i+2]='#';
}
rep(i,1,n-2){
if(s[i]=='o'&&s[i+1]=='n'&&s[i+2]=='e') s[i+1]='#',ans.pb(i+1);
if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o') s[i+1]='#',ans.pb(i+1);
}
printf("%d\n",(int)ans.size());
for(auto u:ans) printf("%d ",u);puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## D. Let’s Play the Words?

time limit per test3 seconds memory limit per test256 megabytes

Polycarp has n different binary words. A word called binary if it contains only characters ‘0’ and ‘1’. For example, these words are binary: “0001”, “11”, “0” and “0011100”.

Polycarp wants to offer his set of n binary words to play a game “words”. In this game, players name words and each next word (starting from the second) must start with the last character of the previous word. The first word can be any. For example, these sequence of words can be named during the game: “0101”, “1”, “10”, “00”, “00001”.

Word reversal is the operation of reversing the order of the characters. For example, the word “0111” after the reversal becomes “1110”, the word “11010” after the reversal becomes “01011”.

Probably, Polycarp has such a set of words that there is no way to put them in the order correspondent to the game rules. In this situation, he wants to reverse some words from his set so that:

• the final set of n words still contains different words (i.e. all words are unique);
• there is a way to put all words of the final set of words in the order so that the final sequence of n words is consistent with the game rules.

Polycarp wants to reverse minimal number of words. Please, help him.

Input

The first line of the input contains one integer $$t (1 \le t \le 10^4)$$ — the number of test cases in the input. Then t test cases follow.

The first line of a test case contains one integer $$n (1 \le n \le 2\cdot10^5)$$— the number of words in the Polycarp’s set. Next n lines contain these words. All of n words aren’t empty and contains only characters ‘0’ and ‘1’. The sum of word lengths doesn’t exceed $$4\cdot10^6$$. All words are different.

Guaranteed, that the sum of n for all test cases in the input doesn’t exceed $$2\cdot10^5$$. Also, guaranteed that the sum of word lengths for all test cases in the input doesn’t exceed $$4\cdot10^6$$.

Output

Print answer for all of t test cases in the order they appear.

If there is no answer for the test case, print -1. Otherwise, the first line of the output should contain $$k (0 \le k \le n)$$ — the minimal number of words in the set which should be reversed. The second line of the output should contain k distinct integers — the indexes of the words in the set which should be reversed. Words are numerated from 1 to n in the order they appear. If k=0 you can skip this line (or you can print an empty line). If there are many answers you can print any of them.

Exampleinput

4
4
0001
1000
0011
0111
3
010
101
0
2
00000
00001
4
01
001
0001
00001


output

1
3
-1
0

2
1 2 

#### 按题意模拟即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
vector<string> a;
int n;
void solve(){
int cnt={0,};//01,10,00,11
set<string> s1,s2;
a.clear();
scanf("%d",&n);
rep(i,1,n){
char s[maxn];scanf("%s",s+1);
int len=strlen(s+1);
string str=s+1;a.pb(str);
if(s=='0'&&s[len]=='0') cnt++;
if(s=='1'&&s[len]=='1') cnt++;
if(s=='0'&&s[len]=='1') cnt++;s1.insert(str);
if(s=='1'&&s[len]=='0') cnt++;s2.insert(str);
}
if(cnt==0&&cnt==0){
if(cnt&&cnt) return (void)puts("-1");
else return (void)printf("0\n\n");
}
if(abs(cnt-cnt)<=1) return (void)printf("0\n\n");
vector<int> ans;
int num=abs(cnt-cnt)/2,pos=0;
if(cnt>cnt){
for(auto u:a){
++pos;
if(u=='0'&&u[u.length()-1]=='1'){
reverse(u.begin(),u.end());
if(num&&s2.find(u)==s2.end()) num--,ans.pb(pos);
}
}
if(num!=0) return (void)puts("-1");
printf("%d\n",(int)ans.size());
for(auto u:ans) printf("%d ",u);puts("");
}
else{
for(auto u:a){
++pos;
if(u=='1'&&u[u.length()-1]=='0'){
reverse(u.begin(),u.end());
if(num&&s1.find(u)==s1.end()) num--,ans.pb(pos);
}
}
if(num!=0) return (void)puts("-1");
printf("%d\n",(int)ans.size());
for(auto u:ans) printf("%d ",u);puts("");
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## E. Two Fairs

time limit per test3 seconds memory limit per test256 megabytes

There are n cities in Berland and some pairs of them are connected by two-way roads. It is guaranteed that you can pass from any city to any other, moving along the roads. Cities are numerated from 1 to n.

Two fairs are currently taking place in Berland — they are held in two different cities a and b $$(1 \le a, b \le n; a \ne b)$$.

Find the number of pairs of cities x and y $$(x \ne a, x \ne b, y \ne a, y \ne b)$$such that if you go from x to y you will have to go through both fairs (the order of visits doesn’t matter). Formally, you need to find the number of pairs of cities x,y such that any path from x to y goes through a and b (in any order).

Print the required number of pairs. The order of two cities in a pair does not matter, that is, the pairs (x,y) and (y,x) must be taken into account only once.

Input

The first line of the input contains an integer t $$(1 \le t \le 4\cdot10^4)$$ — the number of test cases in the input. Next, t test cases are specified.

The first line of each test case contains four integers n, m, a and b$$(4 \le n \le 2\cdot10^5, n – 1 \le m \le 5\cdot10^5, 1 \le a,b \le n, a \ne b)$$ — numbers of cities and roads in Berland and numbers of two cities where fairs are held, respectively.

The following m lines contain descriptions of roads between cities. Each of road description contains a pair of integers $$u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i)$$— numbers of cities connected by the road.

Each road is bi-directional and connects two different cities. It is guaranteed that from any city you can pass to any other by roads. There can be more than one road between a pair of cities.

The sum of the values of n for all sets of input data in the test does not exceed $$2\cdot10^5$$. The sum of the values of m for all sets of input data in the test does not exceed $$5\cdot10^5$$.

Output

Print t integers — the answers to the given test cases in the order they are written in the input.

Exampleinput

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


output

4
0
1


#### 答案显然就是(只能被点a访问的点数)*(只能被点b访问的点数)，两次dfs即可，签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)5e5+100;
const int mod=(int)1e9+7;
int n,m,a,b,op[maxn];
struct node{
int u,v,nxt;
}g[maxn<<1];
void init(){
cnt=2;
}
void dfs(int u,int o,int t){
op[u][o]=1;
int v=g[i].v;
if(op[v][o]==0&&v!=t) dfs(v,o,t);
}
}
void solve(){
scanf("%d%d%d%d",&n,&m,&a,&b);
init();
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
}
dfs(a,0,b);dfs(b,1,a);
ll aa=-1,bb=-1;
rep(i,1,n){
if(op[i]&&op[i]==0) aa++;
if(op[i]==0&&op[i]) bb++;
}
printf("%lld\n",aa*bb);
}
int main(){
int T;cin>>T;
while(T--) solve();
}


## F. Beautiful Rectangle

time limit per test1 second memory limit per test256 megabytes

You are given n integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the n numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

Input

The first line contains $$n (1 \le n \le 4\cdot10^5)$$. The second line contains n integers $$(1 \le a_i \le 10^9)$$.

Output

In the first line print$$x (1 \le x \le n)$$— the total number of cells of the required maximum beautiful rectangle. In the second line print p and $$q (p \cdot q=x)$$: its sizes. In the next p lines print the required rectangle itself. If there are several answers, print any.

Examplesinput

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


output

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


input

5
1 1 1 1 1


output

1
1 1
1

#### 那么如何确定长宽呢，其实很简单，我们枚举w，然后考虑每个数字出现的次数cnt，如果$$cnt>w$$那么显然这个数只能用w次，否则就是cnt次；那么这样做完之后就可以知道一共可以用多少数，除以w就是高度h了；这样枚举完所有的w之后就可以得到一个$$w*h$$的最大值，之后就可以按照上述方法构造了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)4e5+100;
const int mod=(int)1e9+7;
int n,a[maxn],w,h;
map<int,int> mp;
vector<int> v;
vector<vector<int> > ans;
struct node{
int cnt,num;
bool operator<(node b)const{return cnt>b.cnt;}
};
vector<node> s;
set<int> ss;
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]),mp[a[i]]++,ss.insert(a[i]);
for(auto u:ss) s.pb({mp[u],u});
sort(s.begin(),s.end());
ll tmp=0;
rep(i,1,(int)ss.size()){
ll num=0,hh;
for(auto u:s) num+=min(i,u.cnt);
hh=num/i;
if(hh<i) break;
if(i*hh>tmp) tmp=i*hh,h=hh,w=i;
}
vector<vector<int> > ans(h+10);
rep(i,0,h) ans[i].resize(w+10);
v.pb(-1);
for(auto u:s) rep(i,1,min(w,u.cnt)) v.pb(u.num);
rep(i,1,w) rep(j,1,h){
ans[(i-2+j)%h+1][i]=v[i+w*(j-1)];
}
printf("%d\n%d %d\n",w*h,h,w);
rep(i,1,h) rep(j,1,w) printf(j==w?"%d\n":"%d ",ans[i][j]);
}