Background Story

Friendly reminder: This section is not directly related to the problem; readers may choose whether or not to read it.

What is happiness?

Little D likes to ponder life philosophy, and today he is lost in deep thought again.

As for why he is thinking about this, the main reason is that he was caught playing games in the computer lab.

The teacher educated him earnestly: do not waste time on these boring things; you should live a meaningful life.

But the question arises: what kind of life is a meaningful life?

Or, what is the meaning of life after all?

Is it the pursuit of fame and fortune? Perhaps not. After all, Little D knows that such people have long been despised by countless others.

Is it working tirelessly for one's goals? But what exactly is a "goal"? And why must one have a goal? Why must one always "work hard"? Living easily without a goal is living, and giving one's all for a goal is also living; why must one choose the painful way of life? If it is, why do those who pursue fame and fortune become targets of public criticism? They are just living for their own goals; why do fame and fortune become synonymous with vulgarity? Little D finds it hard to understand, but perhaps this is just sour grapes—unable to see others being wealthier or more powerful than themselves, they slander and smear those who strive for so-called fame and fortune; unable to see others living easily yet prosperously, they preach that one must work hard to succeed. A "rich second generation" is always worthless, while a poor student who studies hard becomes a model. This is not because anyone is morally superior, but simply because the poor student is living a harder life. Better results require higher costs—it seems reasonable, but it is actually full of loopholes. Such fallacies are merely self-consolation for those who are not living as they wish. There is no such thing as fairness in the world. A rich second generation inherits wealth from their parents, and a poor student inherits talent from their parents. Your life was decided before the moment you were born; even the ability to work hard is a talent, already carved into your genes. This truth is probably hard to accept, but it is already better than most other creatures on Earth, as they don't even have the qualification to discuss fairness. Taking hard work as the meaning of life is truly a joke.

Then what about helping others or contributing to society? Perhaps that is good. But if this is the meaning of life, Little D cannot agree. Humans are selfish after all; those who can identify with this view without hesitation often lack independent thought and have unconsciously accepted this view under the subtle influence of their environment. So why would someone propose such a view, and how did this view become the creed of the majority, who believe in it firmly? Actually, it is not hard to imagine: letting others help others and contribute to society means that one also has the opportunity to be helped, and one is also a beneficiary. The cost is merely being morally kidnapped oneself and having to do the same thing. This is, after all, a business that doesn't lose money, so even if one thinks to this level, it is not hard to accept this deal. But if one were to take helping others and sacrificing oneself as the meaning of life, that would be a losing business, and Little D won't do it.

So what should the meaning of life be?

Perhaps life has no special meaning. Humans, organisms, and all things in the world are merely a form of existence of matter. You living in this world is as natural as the sun rising from the east—meaningless, and even dispensable.

Then what the meaning of life is, or what to live for, doesn't really matter. If he could choose, Little D would want to live for his own happiness. As for why, it doesn't matter that much either. After all, he is also a form of existence of matter that humans call a living organism. He will perform a series of actions for survival, for reproduction, or for no reason at all; this is called biological instinct. Little D now instinctively wants to seek happiness.

But what is happiness, and why do humans have the instinct to seek happiness?

It is hard to understand. Happiness might help humans survive and reproduce better in some situations, but what is the use of the happiness gained from playing games? —Probably there is no special meaning. The purpose of all biological actions is not survival and reproduction, and there is not even any special purpose. Everything is just a beautiful coincidence. By chance, they performed some inexplicable actions and gained a survival advantage, eventually leading to the trend that the actions of surviving organisms are "for the sake of survival and reproduction." This is a fact that humans only discovered recently, to the extent that most people today still cannot fully understand it, and even Little D himself cannot always consider this theory first when thinking about problems.

In the end, is everything meaningless? Any thought can only lead to the result that the object of thought is meaningless; this result itself is meaningless, the thinking is meaningless, and the question is meaningless.

How pathetic.

Although Little D wants to pursue happiness, he really cannot be happy right now. It is not because he thought of too many pathetic realities, but mainly because the teacher gave him a half-hour ideological education. Although he fell into his own ocean of thoughts after hearing only the first sentence.

Little D opens a search engine and searches aimlessly for what happiness is.

The webpage displays a lot of information, but most of it is chicken soup for the soul that Little D disdains to look at.

Because he is too bored, Little D decides to do something he has never done before: he will use a program to extract feature codes from this information and analyze the mystery of happiness from a mathematical perspective.

Before long, Little D extracts several sequences. He vaguely senses that some mysterious pattern seems to be hidden in each sequence. Perhaps cracking the pattern could reveal the essence of happiness.

But this task might have to be left to you. Because Little D learned a lot from the teacher's teachings, he does not want to waste time on such boring things; he wants to live a meaningful life.

After all, the teacher has finished scolding the classmate who was playing games with him and has walked out of the computer lab.

After all, for Little D, the meaning of life might just be happiness.

After all, games are the true happiness.

Note: All text in this article is for the sake of the story plot and has no direct connection to the author or any actual things. Readers should treat the thoughts and views of the story characters with caution according to their own ideas.

Description

This is an answer-submission problem.

You will be given several sequences, each of which follows a definite pattern. You need to find this pattern and calculate a specific term of the sequence based on it.

There are a total of $10$ input files, numbered $0 \sim 9$. Each input file contains $5$ sequences. The patterns of the sequences in each input file have a certain correlation and exist in a certain difficulty gradient.

You need to calculate the specified term for each sequence. For each correctly calculated answer, you will receive $2$ points. The answer is based on the standard answer. If the answer you calculated for a query is different from the standard answer, you will receive $0$ points for that query, even if the pattern you discovered makes every term of the given sequence satisfy it.

Input

The input file numbered $i$ is named happy$i$.in. Each input file provides $5$ queries in sequence.

Each query consists of two lines. The first line contains three integers $n, p, k$. $n$ indicates that the data provides the $1 \sim n$-th terms of the sequence. $p$ indicates whether the sequence is under a modulo and the specific modulus; if $p=0$, the sequence is in the range of integers; otherwise, the sequence is modulo $p$, and all numbers are integers between $0 \sim p-1$; it is guaranteed that $p \geq 0$. $k$ indicates the $k$-th term of the sequence to be calculated. Note that $k$ may not be a positive integer, and its meaning can be derived from the pattern of the sequence. The second line contains $n$ integers, representing the given sequence. For ease of observation, an extra empty line is provided after each query.

Output

For the input file numbered $i$, you need to submit an answer file named happy$i$.out. If you do not submit it, you will receive $0$ points for this input file.

Each answer file must contain at least five lines, where each of the first five lines must contain exactly one integer, representing the answers to each query in the corresponding input file in order. If you cannot find the correct answer for a query, it is recommended to output $-1$. If your submitted answer does not strictly follow this format, there is no guarantee that the correct evaluation result will be returned.

The part after the fifth line allows contestants to submit some additional information, which can include the discovered patterns or personal thoughts, etc. This part has no impact on the contestant's score.

Examples

Input 1

5 0 10
1 2 3 4 5

5 0 0
1 2 3 4 5

5 9 10
1 2 3 4 5

10 0 66
2 3 3 3 3 2 3 3 3 3

10 0 666
2 3 3 3 3 3 3 3 3 3

Output 1

10
0
1
2
3

Note

Contestants are requested to consciously refrain from using any search tools.