A.

Input

The only line contains the integer?xx?(1≤x≤100)(1≤x≤100).

Output

You should output two integers?aa?and?bb, satisfying the given conditions, separated by a space. If no pair of integers satisfy the conditions above, print "-1" (without quotes).

Examples

Input

10

Output

6 3

Input

1

Output

-1

解題報(bào)告：

? ?就是給你一個(gè)x，讓你構(gòu)造一個(gè)a和b，滿足和x的這仨關(guān)系就行了。

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 = 2e5 + 5;int main() {int x,a,b;cin>>x;int flag = 0;for(int i = 1; i<=x; i++) {for(int j = i; j<=x; j+=i) {if(i*j>x && j/i < x) {flag = 1;a=j;b=i;break;}}if(flag) break;}if(flag) printf("%d %d\n",a,b);else puts("-1");return 0 ;}

?

---

B.

給你n個(gè)數(shù)的數(shù)組，給一個(gè)k。讓你重復(fù)執(zhí)行k次下列操作：每次選中序列中不為0的最小的數(shù)并輸出，然后把序列中所有非零的數(shù)都減去這個(gè)選中的數(shù)。如果序列已經(jīng)都是0了，那就輸出0.

Examples

Input

3 5 1 2 3

Output

1 1 1 0 0

Input

4 2 10 3 5 3

Output

3 2

Note

In the first sample:

In the first step: the array is?[1,2,3][1,2,3], so the minimum non-zero element is 1.

In the second step: the array is?[0,1,2][0,1,2], so the minimum non-zero element is 1.

In the third step: the array is?[0,0,1][0,0,1], so the minimum non-zero element is 1.

In the fourth and fifth step: the array is?[0,0,0][0,0,0], so we printed 0.

In the second sample:

In the first step: the array is?[10,3,5,3][10,3,5,3], so the minimum non-zero element is 3.

In the second step: the array is?[7,0,2,0][7,0,2,0], so the minimum non-zero element is 2.

解題報(bào)告：

? 先別看哪個(gè)Node，，有的時(shí)候會(huì)誤導(dǎo)你的思路。。其實(shí)這題就是將減的數(shù)給可持久化一下、、因?yàn)槟阆氚∧憧偛荒軠p一個(gè)數(shù)，就將序列中的數(shù)都變化一下吧，，所以解決方法就是用一個(gè)sub來動(dòng)態(tài)記錄變化的數(shù)的值。為啥可以這樣呢？因?yàn)槟汶m然要變化整個(gè)數(shù)組中的值，，但是其實(shí)你就算不變化，，也不會(huì)影響下次你取數(shù)組中的最小值（因?yàn)榇蠹叶紲p同一個(gè)數(shù)，相對(duì)的大小關(guān)系肯定沒變啊）所以就用一個(gè)變量記錄就行了。

AC代碼1：（排序版）

#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 = 2e5 + 5; ll a[MAX]; int main() {int n,k;cin>>n>>k;for(int i=1; i<=n; i++) scanf("%lld",a+i);ll sub=0;sort(a+1,a+n+1);for(int i=1,j=1;j<=k;i++,j++) {if(i>n) {printf("0\n");} else {while(1) {if(a[i]!=sub) break;i++;if(i > n) {printf("0\n");break;}}if(i<=n) {a[i]-=sub;printf("%lld\n",a[i]);sub+=a[i];}}}return 0; }

或者用優(yōu)先隊(duì)列也可以寫:

AC代碼2：

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<set> #include<map> #include<queue> #include<cmath> #define ll long long #define mod 1000000007 #define inf 0x3f3f3f3f using namespace std; priority_queue<int, vector<int>, greater<int> > pq; int n,k; int main() {cin>>n>>k;for(int i = 1,tmp; i <= n; i ++) {scanf("%d",&tmp);if(tmp) pq.push(tmp);}int sub = 0;while(k--) {if(!pq.empty()) {int cur = pq.top();while(cur - sub == 0 && !pq.empty()) {pq.pop();cur=pq.top();}printf("%d\n",cur-sub);sub += (cur-sub);}else puts("0");}return 0; }

不過更適合我的方式其實(shí)是先判斷一堆直到只能變成0。然后再看看剩余的次數(shù)是否大于0，如果大于0再輸出k次的0就行了、

?

---

C.

不想寫題意了。。**構(gòu)造一眼題

You're given an array?aa?of length?nn. You can perform the following operations on it:

• choose an index?ii?(1≤i≤n)(1≤i≤n), an integer?xx?(0≤x≤106)(0≤x≤106), and replace?ajaj?with?aj+xaj+x?for all?(1≤j≤i)(1≤j≤i), which means add?xx?to all the elements in the prefix ending at?ii.
• choose an index?ii?(1≤i≤n)(1≤i≤n), an integer?xx?(1≤x≤106)(1≤x≤106), and replace?ajaj?with?aj%xaj%x?for all?(1≤j≤i)(1≤j≤i), which means replace every element in the prefix ending at?ii?with the remainder after dividing it by?xx.

Can you make the array?strictly increasing?in no more than?n+1n+1?operations?

Input

The first line contains an integer?nn?(1≤n≤2000)(1≤n≤2000), the number of elements in the array?aa.

The second line contains?nn?space-separated integers?a1a1,?a2a2,?……,?anan?(0≤ai≤105)(0≤ai≤105), the elements of the array?aa.

Output

On the first line, print the number of operations you wish to perform. On the next lines, you should print the operations.

To print an adding operation, use the format "11?ii?xx"; to print a modding operation, use the format "22?ii?xx". If?ii?or?xx?don't satisfy the limitations above, or you use more than?n+1n+1?operations, you'll get?wrong answer?verdict.

Examples

Input

3 1 2 3

Output

0

Input

3 7 6 3

Output

2 1 1 1 2 2 4

Note

In the first sample, the array is already increasing so we don't need any operations.

In the second sample:

In the first step: the array becomes?[8,6,3][8,6,3].

In the second step: the array becomes?[0,2,3][0,2,3].

好吧我還是寫一下題意。。就是說給你n個(gè)數(shù)，給你兩種操作：1.任取一個(gè)x，讓區(qū)間內(nèi)所有的數(shù)都加上這個(gè)x。2.任取一個(gè)x，讓區(qū)間內(nèi)所有的數(shù)都取模這個(gè)x。(其中x<=1e6)。使得這個(gè)序列變成一個(gè)嚴(yán)格遞增序列，讓你輸出每次操作是什么，和怎么操作、、

解題報(bào)告：

? ?1分鐘出標(biāo)算，，10分鐘WA兩發(fā)，，剛開始這個(gè)大數(shù)去了1e7，，（沒讀題），，后來WA1，改成1e6，感覺該沒問題了吧，WA2，，發(fā)現(xiàn)后面在取模的時(shí)候去的x會(huì)超過1e6，，再改成5e5，AC。。

其實(shí)這題上來就取個(gè)5000左右就行了啊。。

不難構(gòu)造，，題意都提示的很明顯了，，n+1次操作，那肯定猜一個(gè)n次一個(gè)1次唄，，然后不難想到加一個(gè)大數(shù)，然后每次都取模，讓他構(gòu)造成一個(gè)1~n的序列就完事了。

（白白丟掉100分啊，，，心疼）（另外，應(yīng)該輸出a[i]-i，，別寫成了a[i]-1，，，）

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 = 2e5 + 5; ll a[MAX]; int main() {int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i); printf("%d\n",n+1);printf("1 %d 500000\n",n);for(int i = 1; i<=n; i++) a[i] += 500000;for(int i = 1; i<=n; i++) {printf("2 %d %lld\n",i,a[i]-i);}return 0 ;}

---

D.

?未補(bǔ)。抽空學(xué)學(xué)交互題吧、、

總結(jié)

以上是生活随笔為你收集整理的*【CodeForces - 1088 ABC】套题比赛，A水题B模拟C构造D交互的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。