apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The cows have just learned what a primitive root is! Given a prime p, a primitive root $$\bmod p$$ is an integer x (1 ≤ x < p) such that none of integers x - 1, x2 - 1, ..., xp - 2 - 1 are divisible by p, but xp - 1 - 1 is.

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime p, help the cows find the number of primitive roots $$\bmod p$$.

## Input Format
The input contains a single line containing an integer p (2 ≤ p < 2000). It is guaranteed that p is a prime.

## Output Format
Output on a single line the number of primitive roots $$\bmod p$$.

## Examples
```input
3
```
```output
1
```
-----
```input
5
```
```output
2
```

## Note
The only primitive root $$\bmod 3$$ is 2.

The primitive roots $$\bmod 5$$ are 2 and 3.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There are n cows playing poker at a table. For the current betting phase, each player's status is either "ALLIN", "IN", or "FOLDED", and does not change throughout the phase. To increase the suspense, a player whose current status is not "FOLDED" may show his/her hand to the table. However, so as not to affect any betting decisions, he/she may only do so if all other players have a status of either "ALLIN" or "FOLDED". The player's own status may be either "ALLIN" or "IN".

Find the number of cows that can currently show their hands without affecting any betting decisions.

## Input Format
The first line contains a single integer, n (2 ≤ n ≤ 2·105). The second line contains n characters, each either "A", "I", or "F". The i-th character is "A" if the i-th player's status is "ALLIN", "I" if the i-th player's status is "IN", or "F" if the i-th player's status is "FOLDED".

## Output Format
The first line should contain a single integer denoting the number of players that can currently show their hands.

## Examples
```input
6
AFFAAA
```
```output
4
```
-----
```input
3
AFI
```
```output
1
```

## Note
In the first sample, cows 1, 4, 5, and 6 can show their hands. In the second sample, only cow 3 can show her hand.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Ksusha is a beginner coder. Today she starts studying arrays. She has array a1, a2, ..., an, consisting of n positive integers.

Her university teacher gave her a task. Find such number in the array, that all array elements are divisible by it. Help her and find the number!

## Input Format
The first line contains integer n (1 ≤ n ≤ 105), showing how many numbers the array has. The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the array elements.

## Output Format
Print a single integer — the number from the array, such that all array elements are divisible by it. If such number doesn't exist, print -1.

If there are multiple answers, you are allowed to print any of them.

## Examples
```input
3
2 2 4
```
```output
2
```
-----
```input
5
2 1 3 1 6
```
```output
1
```
-----
```input
3
2 3 5
```
```output
-1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Ksusha the Squirrel is standing at the beginning of a straight road, divided into n sectors. The sectors are numbered 1 to n, from left to right. Initially, Ksusha stands in sector 1.

Ksusha wants to walk to the end of the road, that is, get to sector n. Unfortunately, there are some rocks on the road. We know that Ksusha hates rocks, so she doesn't want to stand in sectors that have rocks.

Ksusha the squirrel keeps fit. She can jump from sector i to any of the sectors i + 1, i + 2, ..., i + k.

Help Ksusha! Given the road description, say if she can reach the end of the road (note, she cannot stand on a rock)?

## Input Format
The first line contains two integers n and k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ 3·105). The next line contains n characters — the description of the road: the i-th character equals ".", if the i-th sector contains no rocks. Otherwise, it equals "#".

It is guaranteed that the first and the last characters equal ".".

## Output Format
Print "YES" (without the quotes) if Ksusha can reach the end of the road, otherwise print "NO" (without the quotes).

## Examples
```input
2 1
..
```
```output
YES
```
-----
```input
5 2
.#.#.
```
```output
YES
```
-----
```input
7 3
.#.###.
```
```output
NO
```

Now solve the problem and return the code.