D. Kawaii the Rinbot
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, two very productive (even peakly productive) Rinbot'ers have been optimizing Rinbot. They realized that instead of buying a sentient supercomputer, they could use hangman strats instead. These two highly productive Rinbot'ers made a giant cloud-hosted database where they stored the title for every anime in Rinbot. Unfortunately, the AC turned off, marking the end of the laptop.

Can you write a program to access their database?

In this link, there is a text file with all anime titles for shows in Rinbot (up until the Spring 2024 season).

For $$$T$$$ titles, determine which line in the file the title is modulo $$$P$$$. For instance, "86" is on line $$$75$$$ and "?" is on line $$$5$$$.

The Teamscode Online Judge has a submission size limit of 50 kB.

Input

The first line of input will contain a single integer $$$T$$$ $$$(1 \leq T \leq 2 \cdot 10^4)$$$ — the number of titles to consider.

The second line of input will contain a single integer $$$P$$$ $$$(P \in {\{2, 10, 10^5\}})$$$ — the modulus applied to the line numbers you find.

The following $$$T$$$ lines will each contain a title. It is guaranteed that the title is present character for character (including punctuation, spaces, and correct uppercase/lowercase distinction) in the above text file.

It is guaranteed that the sum of all inputted title lengths does not exceed $$$10^6$$$.

—

Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1$$$ will only ask for titles within the second sample test.

Tests $$$2 - 3$$$ will only ask for titles within the first $$$100$$$ lines.

Tests $$$4 - 5$$$ will only ask for titles within the first $$$3366$$$ lines and satisfy $$$P = 2$$$.

Tests $$$6 - 8$$$ will only ask for titles within the first $$$3366$$$ lines and satisfy $$$P = 10$$$.

Tests $$$9 - 10$$$ will only ask for titles within the first $$$3366$$$ lines.

Tests $$$11 - 13$$$ will satisfy $$$P = 2$$$.

Tests $$$14 - 16$$$ will satisfy $$$P = 10$$$.

The remaining tests do not satisfy any additional constraints.

Output

For each title, let $$$\texttt{line}$$$ denote the line number that the title occurs at in the text file. Output a single integer — $$$\texttt{line} \text{ mod P}$$$.

Examples
Input
11
100000
86
?
Bakemonogatari
Hayate no Gotoku!
Shuumatsu Nani Shitemasuka? Isogashii Desuka? Sukutte Moratte Ii Desuka?
Shoujo Shuumatsu Ryokou
"Oshi no Ko"
Shiguang Dailiren II
Hajime no Ippo: The Fighting! - New Challenger
Zombie Land Saga
Lycoris Recoil
Output
75
5
666
3535
8480
8424
17
8201
3366
10591
5553
Input
11
100000
Bakemonogatari
Nisemonogatari
Nekomonogatari (Kuro): Tsubasa Family
Monogatari Series: Second Season
Hanamonogatari: Suruga Devil
Kizumonogatari
Tsukimonogatari: Yotsugi Doll
Owarimonogatari (2017)
Koyomimonogatari
Owarimonogatari
Zoku Owarimonogatari
Output
666
6686
6576
6272
3439
4968
9549
7122
5175
7128
10577
Note

—

Problem Idea: willy108

Problem Preparation: willy108

Occurrences: Novice J, Advanced D