# http:codeforces.comcontest834

Walking through the streets of Marshmallow City, Slastyona have spotted some merchants selling a kind of useless toy which is very popular nowadays– caramel spinner! Wanting to join the craze, she has immediately bought the strange contraption.

Spinners in Sweetland have the form of V-shaped pieces of caramel. Each spinner can, well, spin around an invisible magic axis. At a specific point in time, a spinner can take 4 positions shown below (each one rotated 90 degrees relative to the previous, with the fourth one followed by the first one):

After the spinner was spun, it starts its rotation, which is described by a following algorithm: the spinner maintains its position for a second then majestically switches to the next position in clockwise or counter-clockwise order, depending on the direction the spinner was spun in.

Slastyona managed to have spinner rotating for exactlynseconds. Being fascinated by elegance of the process, she completely forgot the direction the spinner was spun in! Lucky for her, she managed to recall the starting position, and wants to deduct the direction given the information she knows. Help her do this.

Input

There are two characters in the first string– the starting and the ending position of a spinner. The position is encoded with one of the following characters:v(ASCII code118, lowercase v),(ASCII code60),^(ASCII code94) or(ASCII code62) (see the picture above for reference). Characters are separated by a single space.

In the second strings, a single numbernis given (0?≤?n?≤?109)– the duration of the rotation.

It is guaranteed that the ending position of a spinner is a result of ansecond spin in any of the directions, assuming the given starting position.

Output

Outputcw, if the direction is clockwise,ccw– if counter-clockwise, andundefinedotherwise.

Examples
input
`^ 1`

output
`cw`

input
` ^3`

output
`ccw`

input
`^ v6`

output
`undefined`

```#includeiostream
#includecstring
#includecstdio
#includecmath
#includealgorithm
#includeiomanip
#includevector
#define ld long double
#define ll long long
const int inf=0x3f3f3f3f;
const int maxn=1e3+5;
using namespace std;
int n;
char a,b;
int slove(char x)
{
if(x==‘v‘)return 0;
else if(x==‘‘)return 1;
else if(x==‘^‘)return 2;
else return 3;
}
int main()
{
scanf("%c %c",a,b);
scanf("%d",n);
int tmp1=slove(a);
int tmp2=slove(b);
//    couttmp1" "tmp2endl;
if((tmp1+n)%4==tmp2((tmp1-n)%4+4)%4==tmp2)
{
printf("undefined\n");return 0;
}
if((tmp1+n)%4==tmp2)
{
printf("cw\n");return 0;
}
if(((tmp1-n)%4+4)%4==tmp2)
{
printf("ccw\n");return 0;
}
printf("undefined\n");
return 0;
} ```

B. The Festive Evening
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It‘s the end of July– the time when a festive evening is held at Jelly Castle! Guests from all over the kingdom gather here to discuss new trends in the world of confectionery. Yet some of the things discussed here are not supposed to be disclosed to the general public: the information can cause discord in the kingdom of Sweetland in case it turns out to reach the wrong hands. So it‘s a necessity to not let any uninvited guests in.

There are 26 entrances in Jelly Castle, enumerated with uppercase English letters fromAtoZ. Because of security measures, each guest is known to be assigned an entrance he should enter the castle through. The door of each entrance is opened right before the first guest‘s arrival and closed right after the arrival of the last guest that should enter the castle through this entrance. No two guests can enter the castle simultaneously.

For an entrance to be protected from possible intrusion, a candy guard should be assigned to it. There areksuch guards in the castle, so if there are more thankopened doors, one of them is going to be left unguarded! Notice that a guard can‘t leave his post until the door he is assigned to is closed.

Slastyona had a suspicion that there could be uninvited guests at the evening. She knows the order in which the invited guests entered the castle, and wants you to help her check whether there was a moment when more thankdoors were opened.

Input

Two integers are given in the first string: the number of guestsnand the number of guardsk(1?≤?n?≤?106,1?≤?k?≤?26).

In the second string,nuppercase English letterss1s2...snare given, wheresiis the entrance used by thei-th guest.

Output

Output ?YES? if at least one door was unguarded during some time, and ?NO? otherwise.

You can output each letter in arbitrary case (upper or lower).

Examples
input
`5 1AABBB`

output
`NO`

input
`5 1ABABB`

output
`YES`

Note

In the first sample case, the door A is opened right before the first guest‘s arrival and closed when the second guest enters the castle. The door B is opened right before the arrival of the third guest, and closed after the fifth one arrives. One guard can handle both doors, as the first one is closed before the second one is opened.

In the second sample case, the door B is opened before the second guest‘s arrival, but the only guard can‘t leave the door A unattended, as there is still one more guest that should enter the castle through this door.

```#includeiostream
#includecstring
#includecstdio
#includecmath
#includealgorithm
#includeiomanip
#includevector
#define ld long double
#define ll long long
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
using namespace std;
char a[maxn];
int b[27];
bool vis[27];
int n,k;
int main()
{
scanf("%d %d",n,k);
scanf("%s",a);
for(int i=0;in;i++)
{
b[a[i]-‘A‘]=i;
}
bool flag=true;
for(int i=0;in;i++)
{
if(!vis[a[i]-‘A‘])
{
k--;
vis[a[i]-‘A‘]=true;
if(k0)
{
flag=false;break;
}
if(i==b[a[i]-‘A‘])k++;
}
else if(i==b[a[i]-‘A‘])
{
k++;
}
}
if(flag)puts("NO");
else puts("YES");
}```

C. The Meaningless Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Slastyona and her loyal dog Pushok are playing a meaninglessgamethat is indeed very interesting.

Thegameconsists of multiplerounds. Its rules are very simple: in each round, a natural numberkis chosen. Then, the one who says (or barks) it faster than the other wins theround. After that, the winner‘s score is multiplied byk2, and the loser‘s score is multiplied byk. In the beginning of thegame, both Slastyona and Pushok have scores equal to one.

Unfortunately, Slastyona had lost her notepad where the history of allngameswas recorded. She managed to recall the final results for each games, though, but all of her memories of them are vague. Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.

Input

In the first string, the number of gamesn(1?≤?n?≤?350000)is given.

Eachgameis represented by a pair of scoresa,b(1?≤?a,?b?≤?109)– the results of Slastyona and Pushok, correspondingly.

Output

For each pair of scores, answer "Yes" if it‘s possible for a game to finish with given score, and "No" otherwise.

You can output each letter in arbitrary case (upper or lower).

Example
input
`62 475 458 816 16247 9941000000000 1000000`

output
`YesYesYesNoNoYes`

Note

Firstgamemight have been consisted of one round, in which the number2would have been chosen and Pushok would have won.

The secondgameneeds exactly two rounds to finish with such result: in the first one, Slastyona would have said the number5, and in the second one, Pushok would have barked the number3.

```#includeiostream
#includecstring
#includecstdio
#includecmath
#includealgorithm
#includeiomanip
#includevector
#define ld long double
#define ll long long
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
const ll N=1e18;
using namespace std;
ll num[maxn];
int n;
ll x,y;
ll slove(ll l,ll r,ll m)
{
while(l=r)
{
ll mid=(l+r)1;
if(num[mid]==m)return mid;
else if(num[mid]m)
{
r=mid-1;
}
else
{
l=mid+1;
}
//    coutl" "rendl;
}
return -1;
}
int main()
{
scanf("%d",n);
ll cnt;
for(cnt=1;cnt*cnt*cnt=N;cnt++)
num[cnt]=cnt*cnt*cnt;
while(n--)
{
scanf("%I64d %I64d",x,y);
ll ans=slove(1,cnt-1,x*y);
if((x/ans)*(y/ans)==ans)
{
puts("Yes");
}
else
{
puts("No");
}
}
return 0;
}```

D. The Bakery
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Some time ago Slastyona the Sweetmaid decided to open her own bakery! She bought required ingredients and a wonder-oven which can bake several types of cakes, and opened the bakery.

Soon the expenses started to overcome the income, so Slastyona decided to study the sweets market. She learned it‘s profitable to pack cakes in boxes, and that the moredistinctcake types a box contains (let‘s denote this number as thevalueof the box), the higher price it has.

She needs to change the production technology! The problem is that the oven chooses the cake types on its own and Slastyona can‘t affect it. However, she knows the types and order ofncakes the oven is going to bake today. Slastyona has to pack exactlykboxes with cakes today, and she has to put in each box several (at least one) cakes the oven produced oneright after another(in other words, she has to put in a box a continuous segment of cakes).

Slastyona wants to maximize the total value of all boxes with cakes. Help her determine this maximum possible total value.

Input

The first line contains two integersnandk(1?≤?n?≤?35000,1?≤?k?≤?min(n,?50))– the number of cakes and the number of boxes, respectively.

The second line containsnintegersa1,?a2,?...,?an(1?≤?ai?≤?n)– the types of cakes in the order the oven bakes them.

Output

Print the only integer– the maximum total value of all boxes with cakes.

Examples
input
`4 11 2 2 1`

output
`2`

input
`7 21 3 3 1 4 4 4`

output
`5`

input
`8 37 7 8 7 7 8 1 7`

output
`6`

Note

In the first example Slastyona has only one box. She has to put all cakes in it, so that there are two types of cakes in the box, so the value is equal to2.

In the second example it is profitable to put the first two cakes in the first box, and all the rest in the second. There are two distinct types in the first box, and three in the second box then, so the total value is5.

```#includeiostream
#includecstring
#includecstdio
#includecmath
#includealgorithm
#includeiomanip
#includevector
#define ld long double
#define ll long long
using namespace std;
const int maxn=4e4+5e3+5;
int n,k;
int a[maxn];
int now[maxn],last[maxn];
int dp[55][maxn];
int tree[maxn2];
void push(int rt)
{
tree[rt]=max(tree[rt1],tree[rt1|1]);
return;
}
void push_down(int rt)
{
{
}
return ;
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L=lr=R)
{
tree[rt]+=c;
return ;
}
push_down(rt);
int m=(l+r)/2;
if(L=m)
update(L,R,c,l,m,rt1);
if(Rm)
update(L,R,c,m+1,r,rt1|1);
push(rt);
return ;
}
int query(int L,int R,int l,int r,int rt)
{
if(L=lr=R)
{
return tree[rt];
}
push_down(rt);
int m=(l+r)1;
int ans=0;
if(Rm)
ans=max(ans,query(L,R,m+1,r,rt1|1));
if(L=m)
ans=max(ans,query(L,R,l,m,rt1));
return ans;
}
int main()
{
scanf("%d %d",n,k);
for(int i=1;i=n;i++)
{
scanf("%d",a[i]);
}
for(int i=1;i=n;i++)
{
last[i]=now[a[i]];
now[a[i]]=i;
}
for(int i=1;i=k;i++)
{
memset(tree,0,sizeof(tree));
for(int j=1;j=n;j++)
{
update(j,j,dp[i-1][j],0,n,1);
}
for(int j=i;j=n;j++)
{
update(max(i-1,last[j]),j-1,1,0,n,1);
dp[i][j]=query(i-1,j-1,0,n,1);
}
}
printf("%d\n",dp[k][n]);
return 0; ```

http://codeforces.com/contest/834