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