Longest Arithmetic Progressions

Problem code: ARITHPR

All submissions for this problem are available.

You are given positive integers L, R, k such that k <= R - L. Consider all strictly increasing arithmetic progressions with difference not less than k composed of numbers from the set {L, L+1, ..., R}. At first you need to find the length of the longest such progression. Easy as pie, right? Now consider all such longest progressions and write them down in lexicographical order. You need to find first two terms of the nth such progression. (Note that because of the condition k <= R - L the length of the longest progression is at least two.)

Remark. We say that sequence a = (a[0], a[1], ..., a[n]) is lexicographically smaller than b = (b[0], b[1], ..., b[n]) if there exists some i such that 0 <= i <= n, a[j] = b[j] for 0 <= j < i and a[i] < b[i].

Input

The first line contains a single integer T <= 10000, the number of test cases. T test cases follow. The only line of each test case contains four positive integers L, R, k and n where R <= 109, k <= R - L and n <= 1018.

Output

For each test case, output a single line containing the length of the longest strictly increasing arithmetic progressions with difference not less than k composed of numbers from the set {L, L+1, ..., R} followed by the first two terms of the nth such progression in lexicographical order. If the total number of such progressions is less than n then simply output two zeros instead of the first two terms of the progression.

Example

Input:
3
2 6 2 1
2 6 2 2
1 32 8 12

Output:
3 2 4
3 0 0
4 5 14

Author: anton_lunyov
Date Added: 10-06-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

:)

fragote @ 19 Jun 2011 09:36 PM
:)

R>L? is it always true?

iensen @ 19 Jun 2011 10:35 PM
R>L? is it always true?

@iensen. Yes.

anton_adm @ 19 Jun 2011 10:39 PM
@iensen. Yes.

which is lexicographically

theeporithirumugam @ 19 Jun 2011 11:05 PM
which is lexicographically small ? {9, 13} or {8 14} ?

8, 14 is smaller

rajiv_adm @ 19 Jun 2011 11:09 PM
8, 14 is smaller

@theeporithirumugam. {8 14}

anton_adm @ 19 Jun 2011 11:10 PM
@theeporithirumugam. {8 14} is smaller. At first we compare first numbers of the sequences.

Admin do you think using

foofoo @ 20 Jun 2011 11:20 AM
Admin do you think using maximal instead of longest at some places would have been better?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions