The nickname back then

Each time the user set or changed their nickname, a record [time, nickname] was added to logs, in order of time. The first record holds the nickname chosen at sign-up. If several records have the same time, the one later in logs is the later change.

The nickname shown at time t is the nickname of the record that comes last in logs among the records whose time is at most t. If t is earlier than the time of the first record, the user had not signed up yet, so the nickname shown is an empty string "".

times holds the times when this user's comments were reported. Complete the function solution, which returns a list of the nickname shown at each time, in the same order as times.

Function

solution(logs, times)

Constraints

• The length of logs is from 1 to 100,000, and the records are in ascending order of time.
• Each element of logs has the form [time, nickname]. The time is an integer from 0 to 1,000,000,000, and the nickname is a string of lowercase English letters and digits, with a length from 1 to 10.
• The length of times is from 1 to 10,000, and each element is an integer from 0 to 1,000,000,000.

Examples

Starter code

def solution(logs, times):
    answer = []
    return answer