Eungae (EASY)

Time limit2sMemory limit1024 MB

Summary

Members stand in a circle, and a member greets next round only if exactly one neighbor greeted this round. Count the greeters after K rounds.

Level: Easy3 of 10
Topics: Simulation, Array
Solved: No attempts yet

Problem

This problem is the same as Eungae (HARD) except for the constraints on $N$ , $M$ , and $K$ .

Every member of the SCSC club is an Eungae. Each Eungae greets others with Eungae! whenever it sees another person.

When a person greets with Eungae!, the friends on both sides must also greet with Eungae!. However, if someone receives Eungae! from both sides at the same time, they become so flustered that they forget to greet and cannot greet at all.

There are $N$ SCSC club members standing in a circle. At the start, $M$ of them greet with Eungae!. After $K$ rounds of greetings, find the number of people who will greet in the next round.

Everyone greets at the same time. The members are numbered from $0$ to $N - 1$ in clockwise order.

Input

The first line contains $N$ , $M$ , and $K$ separated by spaces. $(3 \le N \le 200; 1 \le M \le N; 0 \le K \le 10^6)$

From the second line, $M$ lines follow, each containing the number of a person who greets first, one per line. The same input is not given more than once.

Output

Print the number of people who will greet in the next round after $K$ rounds of greetings.

Examples3

Example 1
Input
```
5 3 2
3
0
4
```
Expected output
```
2
```
Example 2
Input
```
4 1 3
3
```
Expected output
```
0
```
Example 3
Input
```
4 4 0
0
1
2
3
```
Expected output
```
4
```