A. Vicious Keyboard

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Tonio has a keyboard with only two letters, “V” and “K”.

One day, he has typed out a string s with only these two letters. He really likes it when the string “VK” appears, so he wishes to change at most one letter in the string (or do no changes) to maximize the number of occurrences of that string. Compute the maximum number of times “VK” can appear as a substring (i. e. a letter “K” right after a letter “V”) in the resulting string.

Input

The first line will contain a string s consisting only of uppercase English letters “V” and “K” with length not less than 1 and not greater than 100.

Output

Output a single integer, the maximum number of times “VK” can appear as a substring of the given string after changing at most one character.

Examples

Input

VK
Copy the code

Output

1
Copy the code

Input

VV
Copy the code

Output

1
Copy the code

Input

V
Copy the code

Output

0
Copy the code

Input

VKKKKKKKKKVVVVVVVVVK
Copy the code

Output

3
Copy the code

Input

KVKV
Copy the code

Output

1
Copy the code

Note

For the first case, we do not change any letters. “VK” appears once, which is the maximum number of times it could appear.

For the second case, we can change the second character from a “V” to a “K”. This will give us the string “VK”. This has one occurrence of the string “VK” as a substring.

For the fourth case, we can change the fourth character from a “K” to a “V”. This will give us the string “VKKVKKKKKKVVVVVVVVVK”. This has three occurrences of the string “VK” as a substring. We can check no other moves can give us strictly more occurrences.

Title links: codeforces.com/contest/801…

Analysis: No one was here earlier than me! Boring of very, do a few questions, feeling retreated a lot, have to refueling! The meaning of this problem is to find the KV this combination, determine a [I + 1) = = ‘K’ | | (a [I] = = ‘V’ && a [I + 2]! =’K’ is set, set +1, otherwise output combination case number!

Here is the AC code:

1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 char a[105]; 6 cin>>a; 7 int len=strlen(a); 8 int ans=0; 9 int flag=0; 10 for(int i=0; i<len-1; i++) 11 { 12 if(a[i]=='V'&&a[i+1]=='K') 13 { 14 ans++; 15 i++; 16 } 17 else if(a[i+1]=='K'||(a[i]=='V'&&a[i+2]! ='K')) 18 flag=1; 19 } 20 cout<<flag+ans<<endl; 21 return 0; 22}Copy the code

B. Valued Keys

Time limit per test: 2 seconds

Memory limit per test: 256 megabytes

Input: standard input

Output: the standard output

You found a mysterious function f. The function takes two strings s1 and s2. These strings must consist only of lowercase English letters, and must be the same length.

The output of the function f is another string of the same length. The i-th character of the output is equal to the minimum of the i-th character of s1 and the i-th character of s2.

For example, f(“ab”, “ba”) = “aa”, and f(“nzwzl”, “zizez”) = “niwel”.

You found two strings x and y of the same length and consisting of only lowercase English letters. Find any string z such that f(x, z) = y, or print -1 if no such string z exists.

Input

The first line of input contains the string x.

The second line of input contains the string y.

Both x and y consist only of lowercase English letters, x and y have same length and this length is between 1 and 100.

Output

If there is no string z such that f(x, z) = y, print -1

Otherwise, print a string z such that f(x, z) = y. If there are multiple possible answers, print any of them. The string z should be the same length as x and y and consist only of lowercase English letters.

Examples

Input

ab 
aa
Copy the code

Output

ba
Copy the code

Input

nzwzl 
niwel
Copy the code

Output

xiyez
Copy the code

Input

ab 
ba
Copy the code

Output

- 1Copy the code

Note

The first case is from the statement.

Another solution for the second case is “zizez”

There is no solution for the third case. That is, there is no z such that f(“ab”, z) =  “ba”.

Title links: codeforces.com/contest/801…

Analysis:

If x[I] is smaller than y[I], then y is output. If x[I] is smaller than y, then y is output. If x[I] is smaller than y, then y is output.

To tell the truth, I don’t quite understand what that is! That’s the way to do it! \

1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 string x,y; 6 cin>>x>>y; 7 for(int i=0; i<x.size(); i++) 8 if(x[i]<y[i]) 9 { 10 cout<<-1<<endl; 11 return 0; 12 } 13 cout<<y<<endl; 14 return 0; 15}Copy the code