# CF1047A - Little C Loves 3 I

## 题目描述

Little C loves number «3» very much. He loves all things about it.

Now he has a positive integer n. He wants to split n into 3 positive integers a,b,c such that a+b+c=n and none of the 3 integers is a multiple of 3. Help him to find a solution.

## 输入

A single line containing one integer n (3≤n≤10^9^) — the integer Little C has.

## 输出

Print 3 positive integers a,b,c in a single line, such that a+b+c=n and none of them is a multiple of 3.

It can be proved that there is at least one solution. If there are multiple solutions, print any of them.

Input

Output

Input

Output

## English单词积累

multiple—倍数；多种多样的

# CF1047B - Cover Points

## 题目描述

There are n points on the plane, (x1,y1),(x2,y2),…,(xn,yn).

You need to place an isosceles triangle with two sides on the coordinate axis to cover all points (a point is covered if it lies inside the triangle or on the side of the triangle). Calculate the minimum length of the shorter side of the triangle.

## 输入

First line contains one integer n (1≤n≤10^5^).

Each of the next n lines contains two integers xi and yi (1≤xi,yi≤10^9^).

## 输出

Print the minimum length of the shorter side of the triangle. It can be proved that it’s always an integer.

Input

Output

Input

Output

plane—飞机；平面

isosceles—等边

# CF1047C - Enlarge GCD

## 题目描述

Mr. F has n positive integers, a1,a2,…,an.

He thinks the greatest common divisor of these integers is too small. So he wants to enlarge it by removing some of the integers.

But this problem is too simple for him, so he does not want to do it by himself. If you help him, he will give you some scores in reward.

Your task is to calculate the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

## 输入

The first line contains an integer n (2≤n≤3⋅10^5^) — the number of integers Mr. F has.

The second line contains n integers, a1,a2,…,an (1≤ai≤1.5⋅10^7^).

## 输出

Print an integer — the minimum number of integers you need to remove so that the greatest common divisor of the remaining integers is bigger than that of all integers.

You should not remove all of the integers.

If there is no solution, print «-1» (without quotes).

Input

Output

Input

Output

Input

Output

## 注意

In the first example, the greatest common divisor is 1 in the beginning. You can remove 1 so that the greatest common divisor is enlarged to 2. The answer is 1.

In the second example, the greatest common divisor is 3 in the beginning. You can remove 6 and 9 so that the greatest common divisor is enlarged to 15. There is no solution which removes only one integer. So the answer is 2.

In the third example, there is no solution to enlarge the greatest common divisor. So the answer is −1.