← 返回题目列表

Codeforces · 261/D

D. 最大值和递增子序列

中文机器翻译题面 查看原题

Maxim 喜欢序列,尤其是那些严格递增的序列。 He is wondering, what is the length of the longest increasing subsequence of the given sequence a?

序列a给出如下:

- 序列的长度等于n × t;
- $$a_i = b_{((i-1) \mod n)+1}$$ (1 ≤ i ≤ n × t),其中操作 $$( x \mod y )$$ 表示取数字 x 除以数字 y 后的余数。

长度为 r 的序列 s1, s2, ..., sr 是序列 a1, a2, ..., an 的子序列,如果存在索引 i1, i2, ..., ir 的递增序列 (1 ≤ i1 < i2 < ... < ir ≤ n),则 aij = sj。 In other words, the subsequence can be obtained from the sequence by crossing out some elements.

Sequence s1, s2, ..., sr is increasing, if the following inequality holds: s1 < s2 < ... < sr.

Maxim 有序列 a 的 k 个变体。帮助Maxim确定每个序列的最长递增子序列的长度。

输入

第一行包含四个整数 k、n、maxb 和 t (1 ≤ k ≤ 10; 1 ≤ n, maxb ≤ 105; 1 ≤ t ≤ 109; n × maxb ≤ 2·107)。接下来的 k 行每行包含 n 个整数 b1, b2, ..., bn (1 ≤ bi ≤ maxb)。

请注意,对于序列 a 的每个变体,值 n、maxb 和 t 一致,唯一的数组 bs 不同。

行中的数字由单个空格分隔。

输出

打印 k 个整数 — 序列 a 的变体的答案。按照变体在输入中遵循的顺序打印答案。

示例

输入 #1

3 3 5 2
3 2 1
1 2 3
2 3 1

输出 #1

2
3
3