世上只有一种英雄主义，就是在认清生活真相之后依然热爱生活。

 

A dragon symbolizes wisdom, power and wealth. On Lunar New Year's Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.

A performer holding the rod low is represented by a 1, while one holding it high is represented by a 2. Thus, the line of performers can be represented by a sequence a1, a2, ..., an.

Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n), then reverse al, al + 1, ..., ar so that the length of the longest non-decreasing subsequence of the new sequence is maximum.

A non-decreasing subsequence is a sequence of indices p1, p2, ..., pk, such that p1 < p2 < ... < pk and ap1 ≤ ap2 ≤ ... ≤ apk. The length of the subsequence is k.

Input

The first line contains an integer n (1 ≤ n ≤ 2000), denoting the length of the original sequence.

The second line contains n space-separated integers, describing the original sequence a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n).

Output

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.

Examples

input

Copy

4 1 2 1 2

output

Copy

4

input

Copy

10 1 1 2 2 2 1 1 2 2 1

output

Copy

9

Note

In the first example, after reversing [2, 3], the array will become [1, 1, 2, 2], where the length of the longest non-decreasing subsequence is 4.

In the second example, after reversing [3, 7], the array will become [1, 1, 1, 1, 2, 2, 2, 2, 2, 1], where the length of the longest non-decreasing subsequence is 9.

#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; int n,jg; int a[2010],dp[2010],p[2010],nx[2010]; int main() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) { dp[i]=1; for(int j=1; j<i; j++) if(a[j]<=a[i]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; p[i]=max(dp[i],p[i-1]); } for(int i=n; i>=1; i--) { dp[i]=1; for(int j=n; j>i; j--) if(a[j]>=a[i]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; nx[i]=max(dp[i],nx[i+1]); } for(int i=1; i<=n; i++) jg=max(jg,p[i]+nx[i+1]); cout<<jg<<endl; return 0; }

Fifa and Fafa are sharing a flat. Fifa loves video games and wants to download a new soccer game. Unfortunately, Fafa heavily uses the internet which consumes the quota. Fifa can access the internet through his Wi-Fi access point. This access point can be accessed within a range of r meters (this range can be chosen by Fifa) from its position. Fifa must put the access point inside the flat which has a circular shape of radius R. Fifa wants to minimize the area that is not covered by the access point inside the flat without letting Fafa or anyone outside the flat to get access to the internet.

The world is represented as an infinite 2D plane. The flat is centered at (x1, y1) and has radius R and Fafa's laptop is located at (x2, y2), not necessarily inside the flat. Find the position and the radius chosen by Fifa for his access point which minimizes the uncovered area.

Input

The single line of the input contains 5 space-separated integers R, x1, y1, x2, y2 (1 ≤ R ≤ 105, |x1|, |y1|, |x2|, |y2| ≤ 105).

Output

Print three space-separated numbers xap, yap, r where (xap, yap) is the position which Fifa chose for the access point and r is the radius of its range.

Your answer will be considered correct if the radius does not differ from optimal more than 10 - 6 absolutely or relatively, and also the radius you printed can be changed by no more than 10 - 6 (absolutely or relatively) in such a way that all points outside the flat and Fafa's laptop position are outside circle of the access point range.

Examples

input

Copy

5 3 3 1 1

output

Copy

3.7677669529663684 3.7677669529663684 3.914213562373095

input

Copy

10 5 5 5 15

output

Copy

5.0 5.0 10.0 #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; double R,x,y,x2,y2; double dis(double x,double y,double a,double b) { return sqrt((x-a)*(x-a)+(y-b)*(y-b)); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>R>>x>>y>>x2>>y2; double d=dis(x,y,x2,y2); if(d>=R) { cout<<fixed<<setprecision(8)<<x<<' '<<y<<' '<<R<<endl; return 0; } double r=(d+R)*0.5; double a=(x-x2)*(R-r)/d +x; double b=(y-y2)*(R-r)/d +y; if(x==x2&&y==y2) { a=x+r; b=y; } cout<<fixed<<setprecision(8)<<a<<' '<<b<<' '<<r<<endl; return 0; }

In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must.

Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now he regrets doing this...

Given two integers p and k, find a polynomial f(x) with non-negative integer coefficients strictly less than k, whose remainder is p when divided by (x + k). That is, f(x) = q(x)·(x + k) + p, where q(x) is a polynomial (not necessarily with integer coefficients).

Input

The only line of input contains two space-separated integers p and k (1 ≤ p ≤ 1018, 2 ≤ k ≤ 2 000).

Output

If the polynomial does not exist, print a single integer -1, or output two lines otherwise.

In the first line print a non-negative integer d — the number of coefficients in the polynomial.

In the second line print d space-separated integers a0, a1, ..., ad - 1, describing a polynomial  fulfilling the given requirements. Your output should satisfy 0 ≤ ai < k for all 0 ≤ i ≤ d - 1, and ad - 1 ≠ 0.

If there are many possible solutions, print any of them.

Examples

input

Copy

46 2

output

Copy

7 0 1 0 0 1 1 1

input

Copy

2018 214

output

Copy

3 92 205 1

Note

In the first example, f(x) = x6 + x5 + x4 + x = (x5 - x4 + 3x3 - 6x2 + 12x - 23)·(x + 2) + 46.

In the second example, f(x) = x2 + 205x + 92 = (x - 9)·(x + 214) + 2018.

#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <set> #include <map> #include <vector> #include <ctime> #include <cctype> #include <bitset> #include <utility> #include <sstream> #include <complex> #include <iomanip> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; ll p,k,ct,jg[100010]; int main() { scanf("%lld%lld",&p,&k); while(p) { jg[ct]=(p%k+k)%k; p=-(p-jg[ct])/k; ct++; } printf("%lld\n",ct); for(int i=0; i<ct; i++) { if(i) printf(" "); printf("%lld",jg[i]); } return 0; }