題干：

One way to create a task is to learn from math. You can generate some random math statement or modify some theorems to get something new and build a new task from that.

For example, there is a statement called the "Goldbach's conjecture". It says: "each even number no less than four can be expressed as the sum of two primes". Let's modify it. How about a statement like that: "each integer no less than 12 can be expressed as the sum of two composite numbers." Not like the Goldbach's conjecture, I can prove this theorem.

You are given an integer?n?no less than 12, express it as a sum of two composite numbers.

Input

The only line contains an integer?n?(12?≤?n?≤?106).

Output

Output two composite integers?x?and?y?(1?<?x,?y?<?n)?such that?x?+?y?=?n. If there are multiple solutions, you can output any of them.

Examples

Input

12

Output

4 8

Input

15

Output

6 9

Input

23

Output

8 15

Input

1000000

Output

500000 500000

Note

In the first example, 12 = 4 + 8 and both 4, 8 are composite numbers. You can output "6 6" or "8 4" as well.

In the second example, 15 = 6 + 9. Note that you can't output "1 14" because 1 is not a composite number.

題目大意：

? 給你一個不小于12的整數，讓你分解成兩個合數。

解題報告：

? 看似不顯然，，但是其實很顯然啊，如果是偶數那就輸出4和n-4? 或者6 和n-6這樣的都行。如果是奇數那就輸出9 和 n-9。做題的時候傻了吧唧的寫了個素數打表。得虧數據給的小是1e6，，要是1e18這樣的還真不好辦了（不過要是給那樣的數據也就回去想規律了2333）。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e6 + 5; bool is[MAX]; void prime() {memset(is,1,sizeof is);is[0]=is[1]=0;for(int i = 2; i<=1000000; i++) {if(is[i]) {for(int j = i+i; j<=1000000; j+=i) is[j]=0; }} } int main() {prime();int n;cin>>n;for(int i = 3; i*2<=n; i++) {if(is[i]==0 && is[n-i] == 0) {printf("%d %d\n",i,n-i);break;}}return 0 ;}

?

總結

以上是生活随笔為你收集整理的【CodeForces - 472A】Design Tutorial: Learn from Math （tricks，思维，数论，打表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。