biu biu biu

今天可怕心情还算可以，有西瓜吃，再多的TLE都过去了。

这是谁出的题！给我站到教室后面去！！！

先给大家分享一道昨天超时差点超哭的一道题：

Abood's birthday has come, and his n friends are aligned in a single line from 1 to n, waiting for their cookies, Abood has x cookies to give to his friends.

Here is an example to understand how Abood gives away the cookies. Suppose Abood has 4 friends and x cookies, then Abood will do the following:

Give a cookie to the 1st friend.
Give a cookie to the 2nd friend.
Give a cookie to the 3rd friend.
Give a cookie to the 4th friend.
Give a cookie to the 3rd friend.
Give a cookie to the 2nd friend.
Give a cookie to the 1st friend.
Give a cookie to the 2nd friend.
And so on until all the x cookies are given away.

Your task is to find how many cookies each friend will get. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

Each test case consists of a single line containing two integers x and n (1 ≤ x ≤ 1018, 1 ≤ n ≤ 1000), in which x is the number of cookies Abood has, and n is the number of his friends.

Output

For each test case, print a single line containing n space-separated integers a1, ..., an, in which ai represents how many cookies the ith friend got.

Example

input

Copy

1
5 3

output

Copy

2 2 1
数据太大，还必须要用unsigned long long,一开始一直用Int交的我不说话！
最开始使用模拟做的，但是它数据太大于是超时了，呜呜。
然后用的然龟龟儿的方法，两排一组，最后觉得这个方法挺难得的，然然不愧是高数满分的大佬！%%%
这道题还卡cin和cout，气死我了
···c++

#include <bits/stdc++.h>
using namespace std;
unsigned long long a[2005], b[2005];
int main(int argc, char const *argv[])
{
	int t;
	cin >> t;
	while (t--)
	{
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		long long x, n;
		cin >> x >> n;
		if(n == 1)
        {
            cout << x <<endl;
            continue;
        }
		for (int i = 0; i < n; i++)
			b[i] = i + 1;
		int c = 2;
		for (int i = 2 * n - 3; i >= n; i--)
			b[i] = c++;
       unsigned long long s = x / (2*n-2); 
        unsigned long long y = x % (2*n-2); 
        for(int i = 0; i < (2*n-2); i++)
            a[b[i]] += s;
		for (int i = 0; i < y; i++)
		{
			a[b[i]]++;
		}
		printf("%llu", a[1]);
		for (int i = 2; i <= n; ++i)
		{
			printf(" %lld", a[i]);
		}
		printf("
");
	}
	return 0;
}

```

Polycarp likes numbers that are divisible by 3.

He has a huge number $s$

For example, if the original number is $s = 3121$

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $3$

Input

The first line of the input contains a positive integer $s$

Output

Print the maximum number of numbers divisible by $3$

Examples

Input

Output

Input

Output

Input

1000000000000000000000000000000000

Output

Input

201920181

Output

4
这个题也蛮巧妙的，看着挺眼熟的。
像这种看似很复杂的题其实很多代码都挺简单的。
一位一位的向后判断，可能第一个数被三整除了，可能第一个数和第二个数被三整除了，但其实判断最多只有三个数的情况。
如果第一位和第二位都不能被三整除，那么它对3取余就只可能是11和22两种，然后讨论第三个数的情况，一共有四种：111取三个数的情况，112取后两个数，221取后两个数，222取三个数，所以无论数多大都最多每次讨论三位。

···c++
#include<iostream>
#include<stdio.h>
#include<string.h> 
#include<math.h> 
#include<algorithm> 
using namespace std; 
int main() 
{ 
string s; 
int i; 
cin>>s; 
int count=0,cnt=0; 
int kepa=0; 
for(i=0;i<s.length();i++) 
{ 
count++; 
int k=(s[i]-'0')%3; 
cnt+=k; 
if(k==0||cnt%3==0||count==3) 
{ kepa++; 
  count=0; 
  cnt=0; 
} 
} 
cout<<kepa<<endl; 
return 0; 
}
···

还有一道是今下午紧都超时的一道题，差点就放弃了，后来，沛沛过来拿我的麻花的时候语重心长的告诉了我他的解法，还有一些容易引起超时的小细节，然后好不容易才过的
我现在怕超时都不怕wa的，超时真的太痛苦了

You are given an array a consisting of n integers a1, ..., an. In one operation, you can choose 2 elements ai and aj in which ai is divisible byaj and transform ai to aj.

A number x is said to be divisible by a number y if x can be divided by y and the result is an exact whole number. For example, 15 is divisible by 3, because 15÷ 3 = 5 exactly, but 9 is not divisible by 2 because 9÷ 2 is 4 with 1 left over.

Your task is to find the minimum sum of the array a that can be obtained by making as many transform operations as you want. Can you?

Input

The first line contains an integer T (1 ≤ T ≤ 100) specifying the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105), in which n is the size of array a. Then a line follows containing n integersa1, ..., an (1 ≤ ai ≤ 106), giving array a.

The sum of n overall test cases does not exceed 3 × 106.

Output

For each test case, print a single line containing the minimum sum of the array a that can be obtained after making as many transform operations as you want.

Example

input

Copy

1
5
2 2 3 6 6

output

Copy

11

···c++

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
long long a[100005],vis[1000005]={0};
int n,t,i,j;
scanf("%d",&t);
while(t--)
{
memset(a, 0, sizeof(a));
memset(vis, 0, sizeof(vis));
long long sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
vis[a[i]]++;
}
for(i=0;i<=1000000;i++)
{
if(vis[i])
{
for(j=2;i*j<=1000000;j++)
{
if(vis[i*j])
{
vis[i]+=vis[i*j];
vis[i*j]=0;
}
}
}
}
for(i=1;i<1000005;i++)
{
sum+=vis[i]*i;
}
printf("%lld ",sum);
}
return 0;
}

```

最后补一句

zxy一点都不NB!!!呜呜呜