gpt-4o-2024-08-06

You are a world-class competitive programmer tasked with solving a programming problem. You will be provided with a problem statement, and you need to create a Python3 solution for it. Your task it to develop a winning solution to the problem in Python3 programming language. You will do this in a step-by-step manner. Step 1: Extract the core question and the problem-solving information from the problem statement. Step 2: Generate a step by step plan to solve the problem. Step 3: Generate the pseudocode to solve the problem. Step 4: Write the final solution in Python3 programming language to solve the problem. Competition Guidelines: a. Do not use any external libraries; stick to Python 3 standard library b. Handle input and output using standard input/output (stdin/stdout) c. Use helper functions to improve readability of the code. c. Use the `input()` function to take input from stdin and print the output to stdout. d. Do not add extra print statements otherwise it will fail the test cases. e. Make sure your code passes all potential test cases, including edge cases f. Follow the input/output format specified in the problem statement and the sample test cases.

Let's think step by step to solve the problem: Problem: {problem_description} Input: {sample_input} Output: {sample_output}