This is the hard version of the problem. The difference between the versions is that in this version, (k) can be non-zero. You can hack only if you solved all versions of this problem. A toy box is a refrigerator filled with childhood delight. Like weakness, struggle, hope ... When such a sleeper is reawakened, what kind of surprises will be waiting? M received her toy box as a birthday present from her mother. A jewellery designer would definitely spare no effort in decorating yet another priceless masterpiece as a starry firmament with exquisitely shaped gemstones. In addition, (l) distinct locks secure the tiny universe of her lovely daughter: a hair clip featuring a flower design, a weathered feather pen, a balloon shaped like the letter M ... each piece obscures a precious moment. A few days ago, M rediscovered her toy box when she was reorganizing her bedroom, along with a ring of keys uniquely designed for the toy box. Attached to the key ring are ((l + k)) keys, of which (l) keys are able to open one of the (l) locks correspondingly, while the other (k) keys are nothing but counterfeits to discourage brute-force attack. To remind the correspondence, M's mother adorned each key with a gemstone of a different type. However, passing days have faded M's memory away. "... So I have to turn to you all," M said while laying that ring of keys on the table. K picked up the keys and examined them carefully. "The appearance of these keys unveils nothing fruitful. Thus, I am afraid that we shall inspect them sequentially." Although everyone is willing to help M, nobody has a plan. Observing others' reactions, T suggested, "Let's play a game. Everyone tries a key in turn, and who opens the most locks is amazing ." (n) members, including M herself, take turns to unlock the toy box recursively in the same order until all the (l) locks are unlocked. At each turn, the current member only selects a single key and tests it on exactly o