Kth cheapest item

Problem

A binary search tree holds item prices. Print the kth smallest price.

Input: Line 1: the tree in level order, keys separated by spaces, with # for a missing child. The children of a missing node are not listed, and trailing # may be left out. A single # is an empty tree. Line 2: k.
Output: The kth smallest key.
Constraints: 1 ≤ number of nodes ≤ 300
1 ≤ k ≤ number of nodes
1 ≤ each key ≤ 1000000, all different

Example 1

Input

8 3 10 1 6 # 14 # # 4 7 13
3

Output

Example 2

Input

2 1 3
1

Output

Try the problem first. Open one hint at a time.

Hint 1

Inorder lists keys in increasing order.

Hint 2

itertools.islice can skip k - 1 keys from a generator.

Write your Python code, run it on the examples and submit it to hidden tests.