403556: GYM101193 G Hard exam

Being a teaching professor is a hard and thankless job. Throughout the semester students do not attend lectures because they prefer staying in their warm beds. If only they notified the staff they would be absent! But no, students always think it is only they who want to sleep… And in the end professors are forced to listen to their ridiculous answers during exams. The old professor is pretty tired of this iniquity, so he came up with a new way to give and grade exams.

There are n² students in the group to which the professor gives exam. There are only two grades possible: "pass" and "fail". The professor has a square table of n² cells; each cell represents the final grade of one of the students. Initially all cells contain "fail". The unaware prefect of the student group is asked to pick an arbitrary number k, and then the fun begins. The professor chooses an arbitrary row or column in the table and inverses all grades in it. He repeats this operation until exactly k students have "pass". At this point the exam is over, and the k lucky students go to celebrate the finals being over. However, there are cases when it is not possible for k students to pass the exam according to the professor’s scheme. In such cases everyone needs to retake the exam.

The best student have to help the prefect to find out if anyone would pass the exam if he picks number k.

The first input line contains two integer numbers n and t, where n is the size of the professor’s table and t is the number of tests. Second line contains four integer numbers q₀ a b m. These numbers are used by the prefect to generate t numbers k_i according to the following rule:

Output the number of numbers among k_i (1 ≤ i ≤ t) for which it is possible for someone to pass the exam.

5 6
9 1 2 999999993

4

85 155
88 120 53 980090303

42