import sys # Set a higher recursion depth limit to handle potentially deep recursive calls. # The maximum length of the binary representation is 10^5. The depth of recursion might # be related to this length, possibly linear in the worst case (e.g., N = 2^k - 1). # A value like 2*10^5 + 100 should be safe for L=10^5. # Use try-except block in case setting the limit fails (e.g., due to OS restrictions). try: sys.setrecursionlimit(2 * 10**5 + 100) except Exception as e: # If setting the limit fails, print a warning to stderr. The program might still work # for smaller inputs or if the actual recursion depth is within the default limit. print(f"Warning: Could not set high recursion depth: {e}", file=sys.stderr) pass # Memoization cache (dictionary) to store results of compare_int(N, M). # Keys are tuples (N, M), values are boolean results (True if N < M, False otherwise). memo = {} def get_components_int(n): """ Computes the components (N0, N1) for a positive integer n, where n is uniquely represented as n = (2 * N0 + 1) * 2^N1. N1 is the exponent of 2 in the prime factorization of n (v_2(n)). N0 = ( (n / 2^N1) - 1 ) / 2. Assumes n > 0. """ # The function should not be called with n=0. The main comparison logic handles n=0 as a base case. if n == 0: raise ValueError("get_components_int called with 0") # Find N1: the number of trailing zeros in the binary representation of n. # The expression (n & -n) isolates the lowest set bit. For n > 0, this value is 2^N1. # Example: n=12 (1100). -n is two's complement. In Python large ints it works conceptually. # -12 is ...11110100. n & -n = 1100 & ...0100 = 0100 = 4. Value is 2^2. lowest_set_bit = n & -n # The bit_length() method returns the number of bits required to represent an integer in binary, excluding the sign and leading zeros. # For a power of two, 2^k, its bit_length is k+1. # So, N1 = bit_length(2^N1) - 1. n1 = lowest_set_bit.bit_length() - 1 # Calculate the odd part of n: temp_n = n / 2^N1 # Right shifting by n1 performs integer division by 2^n1. temp_n = n >> n1 # Compute N0 from the odd part temp_n. Since temp_n = 2*N0 + 1: # N0 = (temp_n - 1) / 2 # Right shifting by 1 performs integer division by 2. N0_val = (temp_n - 1) >> 1 # Return the computed components (N0, N1) as a tuple of integers. return (N0_val, N1_val) def compare_int(N, M): """ Recursively compares non-negative integers N and M based on the rule derived from the problem structure: N < M if and only if the pair (N1, N0) is lexicographically smaller than (M1, M0). Uses memoization to store results and avoid redundant computations. """ # Create a state tuple (N, M) to use as a key in the memoization dictionary. state = (N, M) # Check if the result for this state is already in the cache. if state in memo: return memo[state] # Base cases for the recursion: if N == M: # If N equals M, then N is not strictly less than M. result = False elif N == 0: # If N is 0, and M must be non-zero (since N != M), then N < M is true. result = True elif M == 0: # If M is 0, and N must be non-zero (since N != M), then N < M is false. result = False else: # Recursive step: Both N > 0 and M > 0. # Compute components (N0, N1) for N and (M0, M1) for M. N0, N1 = get_components_int(N) M0, M1 = get_components_int(M) # Perform lexicographical comparison of pairs (N1, N0) and (M1, M0). # This means we compare N1 and M1 first. If they are equal, we compare N0 and M0. # Recursively compare N1 and M1. N1_lt_M1 = compare_int(N1, M1) if N1_lt_M1: # If N1 < M1, then the pair (N1, N0) is lexicographically smaller than (M1, M0). result = True else: # N1 >= M1. We need to determine if N1 == M1 or N1 > M1. # We can do this by checking the opposite comparison: M1 < N1. # Note: `compare_int(M1, N1)` might already be computed or will be computed and memoized. M1_lt_N1 = compare_int(M1, N1) # If N1 is not less than M1 (N1_lt_M1 is False) AND M1 is not less than N1 (M1_lt_N1 is False), # then N1 must be equal to M1. if not M1_lt_N1: # Case N1 == M1: The comparison depends on N0 and M0. # Recursively compare N0 and M0. The result is True if N0 < M0. result = compare_int(N0, M0) else: # Case N1 > M1 (since M1 < N1 is True). # The pair (N1, N0) is lexicographically larger than (M1, M0). result = False # Store the computed result in the memoization cache before returning. memo[state] = result return result # Main execution block: reads input, calls the comparison function, and prints the result. if __name__ == '__main__': # Read N and M from standard input. They are given as binary strings. N_bin = sys.stdin.readline().strip() M_bin = sys.stdin.readline().strip() # Convert the binary strings to Python's arbitrary precision integers. # Python handles large integers automatically. N = int(N_bin, 2) M = int(M_bin, 2) # Call the compare_int function to determine if N < M according to the problem's logic. if compare_int(N, M): # If compare_int returns True, it means N < M (which corresponds to f(N) \in f(M)). print("Yes") else: # Otherwise, N is not less than M. print("No")