





'''simple docstring'''


from collections import deque

class    lowerCAmelCase_		:




    def __init__(	self			,     _lowerCAmelCase			,     _lowerCAmelCase			,     _lowerCAmelCase		)    ->							Tuple:
        _lowerCAmelCase				=      process_name  # process name
        _lowerCAmelCase				=      arrival_time  # arrival time of the process
        # completion time of finished process or last interrupted time
        _lowerCAmelCase				=      arrival_time
        _lowerCAmelCase				=      burst_time  # remaining burst time
        _lowerCAmelCase				=      0  # total time of the process wait in ready queue
        _lowerCAmelCase				=      0  # time from arrival time to completion time







class    lowerCAmelCase_		:




    def __init__(	self			,     _lowerCAmelCase			,     _lowerCAmelCase			,     _lowerCAmelCase			,     _lowerCAmelCase			,     )    ->							List[Any]:
        # total number of mlfq's queues
        _lowerCAmelCase				=      number_of_queues
        # time slice of queues that round robin algorithm applied
        _lowerCAmelCase				=      time_slices
        # unfinished process is in this ready_queue
        _lowerCAmelCase				=      queue
        # current time
        _lowerCAmelCase				=      current_time
        # finished process is in this sequence queue
        _lowerCAmelCase				=      deque()




    def 							_snake_case   (	self		)    ->							Union[str, Any]:
        _lowerCAmelCase				=      []
        for i in range(len(self.finish_queue		)		):
            sequence.append(self.finish_queue[i].process_name		)
        return sequence




    def 							_snake_case   (	self			,     _lowerCAmelCase		)    ->							Dict:
        _lowerCAmelCase				=      []
        for i in range(len(__snake_case		)		):
            waiting_times.append(queue[i].waiting_time		)
        return waiting_times




    def 							_snake_case   (	self			,     _lowerCAmelCase		)    ->							Optional[int]:
        _lowerCAmelCase				=      []
        for i in range(len(__snake_case		)		):
            turnaround_times.append(queue[i].turnaround_time		)
        return turnaround_times




    def 							_snake_case   (	self			,     _lowerCAmelCase		)    ->							Optional[Any]:
        _lowerCAmelCase				=      []
        for i in range(len(__snake_case		)		):
            completion_times.append(queue[i].stop_time		)
        return completion_times




    def 							_snake_case   (	self			,     _lowerCAmelCase		)    ->							Optional[Any]:
        return [q.burst_time for q in queue]




    def 							_snake_case   (	self			,     _lowerCAmelCase		)    ->							int:
        process.waiting_time += self.current_time - process.stop_time
        return process.waiting_time




    def 							_snake_case   (	self			,     _lowerCAmelCase		)    ->							Dict:
        _lowerCAmelCase				=      deque()  # sequence deque of finished process
        while len(__snake_case		) != 0:
            _lowerCAmelCase				=      ready_queue.popleft()  # current process

            # if process's arrival time is later than current time, update current time
            if self.current_time < cp.arrival_time:
                self.current_time += cp.arrival_time

            # update waiting time of current process
            self.update_waiting_time(__snake_case		)
            # update current time
            self.current_time += cp.burst_time
            # finish the process and set the process's burst-time 0
            _lowerCAmelCase				=      0
            # set the process's turnaround time because it is finished
            _lowerCAmelCase				=      self.current_time - cp.arrival_time
            # set the completion time
            _lowerCAmelCase				=      self.current_time
            # add the process to queue that has finished queue
            finished.append(__snake_case		)

        self.finish_queue.extend(__snake_case		)  # add finished process to finish queue
        # FCFS will finish all remaining processes
        return finished




    def 							_snake_case   (	self			,     _lowerCAmelCase			,     _lowerCAmelCase		)    ->							Tuple:
        _lowerCAmelCase				=      deque()  # sequence deque of terminated process
        # just for 1 cycle and unfinished processes will go back to queue
        for _ in range(len(__snake_case		)		):
            _lowerCAmelCase				=      ready_queue.popleft()  # current process

            # if process's arrival time is later than current time, update current time
            if self.current_time < cp.arrival_time:
                self.current_time += cp.arrival_time

            # update waiting time of unfinished processes
            self.update_waiting_time(__snake_case		)
            # if the burst time of process is bigger than time-slice
            if cp.burst_time > time_slice:
                # use CPU for only time-slice
                self.current_time += time_slice
                # update remaining burst time
                cp.burst_time -= time_slice
                # update end point time
                _lowerCAmelCase				=      self.current_time
                # locate the process behind the queue because it is not finished
                ready_queue.append(__snake_case		)
            else:
                # use CPU for remaining burst time
                self.current_time += cp.burst_time
                # set burst time 0 because the process is finished
                _lowerCAmelCase				=      0
                # set the finish time
                _lowerCAmelCase				=      self.current_time
                # update the process' turnaround time because it is finished
                _lowerCAmelCase				=      self.current_time - cp.arrival_time
                # add the process to queue that has finished queue
                finished.append(__snake_case		)

        self.finish_queue.extend(__snake_case		)  # add finished process to finish queue
        # return finished processes queue and remaining processes queue
        return finished, ready_queue





    def 							_snake_case   (	self		)    ->							Optional[int]:

        #  all queues except last one have round_robin algorithm
        for i in range(self.number_of_queues - 1		):
            _lowerCAmelCase				=      self.round_robin(
                self.ready_queue			,     self.time_slices[i]		)
        #  the last queue has first_come_first_served algorithm
        self.first_come_first_served(self.ready_queue		)

        return self.finish_queue


if __name__ == "__main__":
       import doctest

       _SCREAMING_SNAKE_CASE	 =							Process("P1", 0, 53)
       _SCREAMING_SNAKE_CASE	 =							Process("P2", 0, 17)
       _SCREAMING_SNAKE_CASE	 =							Process("P3", 0, 68)
       _SCREAMING_SNAKE_CASE	 =							Process("P4", 0, 24)
       _SCREAMING_SNAKE_CASE	 =							3
       _SCREAMING_SNAKE_CASE	 =							[17, 25]
       _SCREAMING_SNAKE_CASE	 =							deque([Pa, Pa, Pa, Pa])

       if len(time_slices) != number_of_queues - 1:
              raise SystemExit(0)

       doctest.testmod(extraglobs={"queue": deque([Pa, Pa, Pa, Pa])})

       _SCREAMING_SNAKE_CASE	 =							Process("P1", 0, 53)
       _SCREAMING_SNAKE_CASE	 =							Process("P2", 0, 17)
       _SCREAMING_SNAKE_CASE	 =							Process("P3", 0, 68)
       _SCREAMING_SNAKE_CASE	 =							Process("P4", 0, 24)
       _SCREAMING_SNAKE_CASE	 =							3
       _SCREAMING_SNAKE_CASE	 =							[17, 25]
       _SCREAMING_SNAKE_CASE	 =							deque([Pa, Pa, Pa, Pa])
       _SCREAMING_SNAKE_CASE	 =							MLFQ(number_of_queues, time_slices, queue, 0)
       _SCREAMING_SNAKE_CASE	 =							mlfq.multi_level_feedback_queue()

       # print total waiting times of processes(P1, P2, P3, P4)
       print(
           f'''waiting time:\
        \t\t\t{MLFQ.calculate_waiting_time(mlfq, [Pa, Pa, Pa, Pa])}'''
       )
       # print completion times of processes(P1, P2, P3, P4)
       print(
           f'''completion time:\
        \t\t{MLFQ.calculate_completion_time(mlfq, [Pa, Pa, Pa, Pa])}'''
       )
       # print total turnaround times of processes(P1, P2, P3, P4)
       print(
           f'''turnaround time:\
        \t\t{MLFQ.calculate_turnaround_time(mlfq, [Pa, Pa, Pa, Pa])}'''
       )
       # print sequence of finished processes
       print(
           f'''sequence of finished processes:\
        {mlfq.calculate_sequence_of_finish_queue()}'''
       )









'''simple docstring'''


_SCREAMING_SNAKE_CASE	 =							range(2, 20 + 1)
_SCREAMING_SNAKE_CASE	 =							[10**k for k in range(ks[-1] + 1)]
_SCREAMING_SNAKE_CASE	 =							{}


def 	__a(SCREAMING_SNAKE_CASE_  :					Tuple		,       SCREAMING_SNAKE_CASE_  :					str		,       SCREAMING_SNAKE_CASE_  :					Any		,       SCREAMING_SNAKE_CASE_  :					List[str]    ):



    '''simple docstring'''





    _lowerCAmelCase				=      sum(a_i[j] for j in range(SCREAMING_SNAKE_CASE_		,       len(SCREAMING_SNAKE_CASE_    )    )    )
    _lowerCAmelCase				=      sum(a_i[j] * base[j] for j in range(min(len(SCREAMING_SNAKE_CASE_    )		,       SCREAMING_SNAKE_CASE_    )    )    )

    _lowerCAmelCase			,			_lowerCAmelCase				=      0, 0
    _lowerCAmelCase				=      n - i

    _lowerCAmelCase				=      memo.get(SCREAMING_SNAKE_CASE_    )

    if sub_memo is not None:
        _lowerCAmelCase				=      sub_memo.get(SCREAMING_SNAKE_CASE_    )

        if jumps is not None and len(SCREAMING_SNAKE_CASE_    ) > 0:
            # find and make the largest jump without going over
            _lowerCAmelCase				=      -1
            for _k in range(len(SCREAMING_SNAKE_CASE_    ) - 1		,       -1		,       -1    ):
                if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
                    _lowerCAmelCase				=      _k
                    break

            if max_jump >= 0:
                _lowerCAmelCase			,			_lowerCAmelCase			,			_lowerCAmelCase				=      jumps[max_jump]
                # since the difference between jumps is cached, add c
                _lowerCAmelCase				=      diff + c
                for j in range(min(SCREAMING_SNAKE_CASE_		,       len(SCREAMING_SNAKE_CASE_    )    )    ):
                    _lowerCAmelCase			,			_lowerCAmelCase				=      divmod(SCREAMING_SNAKE_CASE_		,       10    )
                if new_c > 0:
                    add(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_    )

        else:
            _lowerCAmelCase				=      []
    else:
        _lowerCAmelCase				=      {c: []}
        _lowerCAmelCase				=      sub_memo

    if dn >= max_dn or c + diff >= base[k]:
        return diff, dn

    if k > ks[0]:
        while True:
            # keep doing smaller jumps
            _lowerCAmelCase			,			_lowerCAmelCase				=      next_term(SCREAMING_SNAKE_CASE_		,       k - 1		,       i + dn		,       SCREAMING_SNAKE_CASE_    )
            diff += _diff
            dn += terms_jumped

            if dn >= max_dn or c + diff >= base[k]:
                break
    else:
        # would be too small a jump, just compute sequential terms instead
        _lowerCAmelCase			,			_lowerCAmelCase				=      compute(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       i + dn		,       SCREAMING_SNAKE_CASE_    )
        diff += _diff
        dn += terms_jumped

    _lowerCAmelCase				=      sub_memo[c]

    # keep jumps sorted by # of terms skipped
    _lowerCAmelCase				=      0
    while j < len(SCREAMING_SNAKE_CASE_    ):
        if jumps[j][1] > dn:
            break
        j += 1

    # cache the jump for this value digitsum(b) and c
    sub_memo[c].insert(SCREAMING_SNAKE_CASE_		,       (diff, dn, k)    )
    return (diff, dn)


def 	__a(SCREAMING_SNAKE_CASE_  :					Dict		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					Dict		,       SCREAMING_SNAKE_CASE_  :					Union[str, Any]    ):



    '''simple docstring'''





    if i >= n:
        return 0, i
    if k > len(SCREAMING_SNAKE_CASE_    ):
        a_i.extend([0 for _ in range(k - len(SCREAMING_SNAKE_CASE_    )    )]    )

    # note: a_i -> b * 10^k + c
    # ds_b -> digitsum(b)
    # ds_c -> digitsum(c)
    _lowerCAmelCase				=      i
    _lowerCAmelCase			,			_lowerCAmelCase			,			_lowerCAmelCase				=      0, 0, 0
    for j in range(len(SCREAMING_SNAKE_CASE_    )    ):
        if j >= k:
            ds_b += a_i[j]
        else:
            ds_c += a_i[j]

    while i < n:
        i += 1
        _lowerCAmelCase				=      ds_c + ds_b
        diff += addend
        _lowerCAmelCase				=      0
        for j in range(SCREAMING_SNAKE_CASE_    ):
            _lowerCAmelCase				=      a_i[j] + addend
            _lowerCAmelCase			,			_lowerCAmelCase				=      divmod(SCREAMING_SNAKE_CASE_		,       10    )

            ds_c += a_i[j]

        if addend > 0:
            break

    if addend > 0:
        add(SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_		,       SCREAMING_SNAKE_CASE_    )
    return diff, i - start_i


def 	__a(SCREAMING_SNAKE_CASE_  :					List[Any]		,       SCREAMING_SNAKE_CASE_  :					int		,       SCREAMING_SNAKE_CASE_  :					Any    ):



    '''simple docstring'''





    for j in range(SCREAMING_SNAKE_CASE_		,       len(SCREAMING_SNAKE_CASE_    )    ):
        _lowerCAmelCase				=      digits[j] + addend
        if s >= 10:
            _lowerCAmelCase			,			_lowerCAmelCase				=      divmod(SCREAMING_SNAKE_CASE_		,       10    )
            _lowerCAmelCase				=      addend // 10 + quotient
        else:
            _lowerCAmelCase				=      s
            _lowerCAmelCase				=      addend // 10

        if addend == 0:
            break

    while addend > 0:
        _lowerCAmelCase			,			_lowerCAmelCase				=      divmod(SCREAMING_SNAKE_CASE_		,       10    )
        digits.append(SCREAMING_SNAKE_CASE_    )


def 	__a(SCREAMING_SNAKE_CASE_  :					int = 10**15    ):



    '''simple docstring'''





    _lowerCAmelCase				=      [1]
    _lowerCAmelCase				=      1
    _lowerCAmelCase				=      0
    while True:
        _lowerCAmelCase			,			_lowerCAmelCase				=      next_term(SCREAMING_SNAKE_CASE_		,       20		,       i + dn		,       SCREAMING_SNAKE_CASE_    )
        dn += terms_jumped
        if dn == n - i:
            break

    _lowerCAmelCase				=      0
    for j in range(len(SCREAMING_SNAKE_CASE_    )    ):
        a_n += digits[j] * 10**j
    return a_n


if __name__ == "__main__":
       print(f'''{solution() = }''')


