gollark's stats

"an Egaharjb program: run on" " X"
{ "(X*) (X{,1000})$" "\1 \2 \1\2" }

// Rust Compilers Tutorial - Learn Rust by writing a high-performance Brainfuck compiler!

// Rust is a statically type-checked language, so we need to
// import the crates we're going to need at the start of the code
// `use` is short for `using namespace`, like in C++

// The `collections` crate lets us use built-ins like vectors, maps and lists
// We need this so our compiler can use fast (O(1)) data structures and algorithms
use std::collections;
// The `env` crate gives us access to environment variables and similar information
// This is used for the shell terminal interface
use std::env;
// `fs` contains filesystem I/O, like writing to files and reading from files
// Our compiler needs to use files to store compiled code
use std::fs;
// `io` is the base classes for `Read`ing and `Writ`ing to things; we also need this for files
use std::io;
// Rust is a blazingly concurrent language, so we can use threads to make it go faster
use std::thread;
// Import the base classes we need that I mentioned
use std::io::Read;
use std::io::Write;
// We're using threads, so we need our types to use the `Sync` class, from this crate
use std::sync;

// Our compiler needs to know which characters are valid in Brainfuck so we define them here
// This is a const so we can use it in multiple borrows (it's in the compile and run parts)
const CHARS: &[u8] = b"[+<.,>-]";

// Define our `main` function
// All our code needs to be in here so the borrow checker can see it
fn main() {
    let args: Vec<String> = env::args().collect();

    // Rust supports pattern matching using the `match` statement
    // This is really like a `switch`-`case`, which you probably know about, but without `break`
    // We're going to use it to detect if our program is being given the
    // `-c` flag (compile) or the `-r` flag (run)
    match args[1].as_str() {
        "-c" => {
            // Open our files - we'll need to read the Brainfuck code from one of them
            // and write the compiled output to the other one
            // Because these operations deal with the operating system, they can error
            // Rust's error handling requires us to put `.unwrap()` on the end of any statement which might error,
            // so that it throws an exception we can handle
            let mut input = fs::File::open(&args[2]).unwrap();
            let mut output = fs::File::create(&args[3]).unwrap();

            // We're using a streaming algorithm to compile it, for high performance
            // This means we need to define some buffers to fill with data beforehand
            // This is an important loop, so we make sure to avoid allocations during it
            // by predefining them here
            let mut buf = [0];
            let mut bits = Vec::new();

            // Repeatedly read the input of our program into the buffers
            // The `read` method returns how many bytes it takes from the file input,
            // so we keep looping as long as it keeps having bytes in it
            while let 1 = input.read(&mut buf).unwrap() {
                // For each character of the input, we need to look it up in our CHARS string
                // so we can compile it
                // Instead of using a for loop, Rust has a special type of iterator class
                // with methods which let us loop over it with less code
                // Make sure to expand them out if you're trying to be more productive in a group project
                if let Some(index) = CHARS.iter().enumerate().find_map(|(i, char)| {
                    // Sometimes you'll get a confusing error like "can't compare `u8` with `&u8`"
                    // In this case, you should add * and & to make it work - this shows `cargo` that
                    // you know how tow rite Rust code
                    if *&char == *&&buf[0] {
                        Some(i)
                    } else {
                        None
                    }
                }) {
                    // The core of our compiler algorithm. We have to sort the bits into our bits buffer.
                    // For the computer scientist theorists: it's often thought that it's impossible to compile
                    // Brainfuck, because Rice's theorem (https://www.tutorialspoint.com/automata_theory/rice_theorem.htm)
                    // shows us that no algorithm can understand programs - we would need the computer to be sentient,
                    // which philosopher John Searle showed was impossible in the Chinese Room experiment
                    // However, since Rust isn't Turing-completed, it doesn't have this issue
                    bits.push(index & 1);
                    bits.push((index >> 1) & 1);
                    bits.push((index >> 2) & 1);
                }

                // If we have enough bits, we have to write them to the output
                if bits.len() >= 8 {
                    // This is a tricky algorithm, so I looked it up
                    // at https://www.reddit.com/r/rust/comments/36ixl0/converting_a_vector_of_bits_to_an_integer/
                    let new = bits.split_off(8);
                    let byte = bits.iter().rev().fold(0, |acc, &b| acc * 2 + b as u8);
                    output.write(&[byte]);
                    bits = new;
                }
            }
        }

        "-r" => {
            // The first part of our compiler's runner part has to be quite like the compiling part
            // since we have to read and decompile the output from compilation
            let mut input = fs::File::open(&args[2]).unwrap();

            // Define our buffers - we now have an extra one to keep the program data in
            let mut buf = [0];
            let mut bits = Vec::new();
            let mut program = Vec::new();

            while let 1 = input.read(&mut buf).unwrap() {
                // This reads each of bhe bits out of the byte in order and stores them so we can use them
                for bit in 0..8 {
                    bits.push(buf[0] >> bit & 1);
                }
                // We have to take out all the new bits when we have them
                while bits.len() >= 3 {
                    let new = bits.split_off(3);
                    // Now, use the bits to look up in our character table from earlier, so they're decompiled
                    // into the actual program
                    // In a real programming language this step has to reverse the machine code instead
                    // Fortunately, BrainFuck is really simple!
                    program.push(CHARS[((bits[2] << 2) + (bits[1] << 1) + bits[0]) as usize]);
                    bits = new
                }
            }

            // We can use concurrency to make the program faster! This is a great example of how Rust can make programs beter
            // This daemon thread will help us by writing to the terminal output so the main program doesn't have to
            let (sender, receiver) = sync::mpsc::channel();
            thread::spawn(move || {
                let mut stdout = io::stdout();
                loop {
                    stdout.write(&[receiver.recv().unwrap()]).unwrap();
                }
            });

            // We need a lot of variables for running the decompiled program
            // This will store where we are in the tape and program
            let mut cursor = 0;
            let mut position = 0;
            // This will store the content of the tape - we need a `BTreeMap` because a vector isn't scaleable enough
            // This is why database software uses B-trees to store data
            let mut tape: collections::BTreeMap<i128, i128> = collections::BTreeMap::new();
            let mut stdin = io::stdin();

            loop {
                if position >= program.len() {
                    break;
                }
                match program[position] {
                    // These first two commands are really simple, since they just move t he cursor back and forward
                    b'<' => cursor -= 1,
                    b'>' => cursor += 1,
                    // These next two are actually harder because we've also got to read and write the tape
                    // We have to put them in curly braces {} so there can be a semicolon on the end, because inserting
                    // sometimes has to return a value which we were putting in the map, so it has enough free space
                    b'+' => { tape.insert(cursor, if let Some(value) = tape.get(&cursor) { *value + 1 } else { 1 }); },
                    b'-' => { tape.insert(cursor, if let Some(value) = tape.get(&cursor) { *value - 1 } else { -1 }); },
                    // This is the command to do output to the screen
                    // It only has to send our data to the daemon thread from before
                    b'.' => {
                        sender.send(if let Some(value) = tape.get(&cursor) { *value as u8 } else { 0 }).unwrap();
                    }
                    // Now we have to deal with reading input, which is kind of the opposite
                    b',' => {
                        // We have to make a buffer again to keep the text in
                        let mut buf = [0];
                        stdin.lock().read(&mut buf).unwrap();
                        tape.insert(cursor, buf[0] as i128);
                    }
                    // These are the really hard commands to compile!
                    // We have to look for a matching bracket to use or it won't work right
                    b'[' => {
                        // Fortunately, we only have to do this if the tape value is zero
                        // If we don't know it, we assume it's zero
                        let jump = if let Some(value) = tape.get(&cursor) { *value == 0 } else { true };
                        if jump {
                            // We're going to need a stack so we know which bracket is the right one
                            // Otherwise it might match too early and go in the wrong place
                            let mut stack = Vec::new();
                            // We need to go forward until we reach the right place and then stay there
                            loop {
                                // If we have a closing ] bracket, pop from the stack so the top goes down
                                if program[position] == b']' {
                                    stack.pop();
                                }
                                // For an opening bracket, push it to the stack
                                if program[position] == b'[' {
                                    stack.push(program[position]);
                                }
                                // We finally found the right bracket!
                                if stack.len() == 0 && program[position] == b']' {
                                    break;
                                }
                                position += 1;
                            }
                        }
                    }
                    b']' => {
                        // This is basically the same, so it's fine to just copy-paste the code
                        // We have to do the opposite thing in the condition, because the specification code says so
                        let jump = if let Some(value) = tape.get(&cursor) { *value != 0 } else { false };
                        if jump {
                            let mut stack = Vec::new();
                            loop {
                                // This has to look for the other bracket the other way round
                                // so we use the stack the opposite way too
                                // Otherwise it's basically the same idea as before
                                if program[position] == b'[' {
                                    stack.pop();
                                }
                                if program[position] == b']' {
                                    stack.push(program[position]);
                                }
                                if stack.len() == 0 && program[position] == b'[' {
                                    break;
                                }
                                // Go the other way here too
                                position -= 1;
                            }
                        }
                    }
                    // Nothing else can happen, so we can tell rustc that so it makes our code more optimized
                    _ => unreachable!()
                }
                // Make sure to add this!
                // Otherwise you'll just be stuck running the same bit of the code forever
                position += 1;
            }
        }
        // Only "-c" and "-r" are valid, and the user didn't put in any, so create an error
        _ => panic!("invalid argument"),
    }

    // We can define an exception handler here using this script
    // It catches any exceptions the rest of the function throws; we'll just ignore them
    // In a real code you'd have to tell the user about them but this is simpler
    std::panic::catch_unwind(|| {});
}

import json, numpy, math, functools, base64

real_bped = numpy.frombuffer(base64.b64decode('ZQAgAHQAIABzACAAdABoAGkAbgBkACAAZQByAGEAbgB5ACAAbwAgAG8AbgAgACAAbwB1AG8AcgBnACAAZQBuAGEAbAAEAQ4BYQAgAHIAZQBhAHIAaQACASAAAwF0AAkBcwB0AGkAAQFpAHQAbwBtAGEAdAAgAHcAeQAMAWgAYQBlAAUBZgAgACwAIABsAAgBdQBzAAcBBQFsACAAZQACAUkAIAAGASAAYwBoAG8AdwALAQsBZQBzAAMBAAFhAHMAZQBjAB4BIABrACAAdgAAAWwAaQB0AGkAbQAgACcAAQFsAG8ADQEgAHIAbwAnAAIBbAAAAW0AYQAKASAABwEgAGUAbAAEASAAYgB1AGEAAQFsAGUAYQBjAGkAYwBpAHMAFgEAAWkAIABtAAABDwEgAGEAYgBvACEBbgBvAGkAbAByAGEAaAAgAHAAOgEuACAAawAAAXUAbgBnAG8AQgEBAXYABgFvAHAAcwAbAaMA4gBpAAMBgwBbAV0BXQFzAGUAKwEgAGkAZABjABsBcwAJAW0ACAFvAGQAJAEAARoBOwFJACcAcgBpAGAAYAB3AGgAbwBsAGYAOQFiAGUAHwEzAXMAaABhAAIBdQByABABIwFlAG0AZQB4AGEAZwAKACwBYQBkAHMAaQB0AHQAYgAAAT4AIABgACAACgEAAU4BAQEGAQABdQBjAOIAjQAUAQABAwEVAXQABgEMAQEBbgA3AXAAIABuAGUAEAEgAAwBbABkAG8AYwA/ASkAKQBmAA0BAwFDAQ8BdABpAHIAcABwAAoBNwE0AVQBKgEgAGIAMAFhAAgBWgFlAC4ALgAkAQEBXAEgAHAAZQB0AHIAbwBmAHAAbwBtAGUAAwERAWEAZgFpACEBYwAKAR8BAQFkAGUAZAAJAXAAbACXAaMBMQAxAHMAdQB0AGEAiwEFAWQAaQBzAAEBZACUAWcAZQBtAG8AHAFpAHQAbwAPAQEBcQB1AG4ACQEdAWgAXgFeAQQBZwAwADAAYQBtAGMAZQFiAG8AbgAgAHkAJwFnAGgAdQBsAEEAQQApACAAPwAgAAcBZwBlAGEAAwFlABoBAAFoATYBcgAgAAwBbgB3AA0BEAFsAGoAmwFnAFABGwEgAG4AYAE+AD4AdQB0ABYBFQFPASYBawARAVoBAAFwABMBZgByAGUAdgBrAGUAbQBtAHAABgEvAC8AIAEXAXcAnAE8ADwAvgEAAWYAgQFwAHMABwEBAWEAeQBkAEcBYwANAXQAAgFAASYBbQBwABwBAAFoAHoBWAEIAToA4AFSAdEBYwAAAUYBIABiAXAAYQAFAZ0BWQEKACAAcwBwAGgAYAEeAcwBTAGGAWsAAgH3ATwBYwAHAWYABAFvAAUBOgAgACgAKAArACsA7wHmAQUC8QFSAWIAEAEmARgBcgBJAB0BBAGFARwBOwEYAXUAHwECAT0AIABMATwBdwByAHMAAAEWAUMBQwAgAGUAGAFuACsBdgEAARABYwEHAWQAYQBKAS0BAgFvAGIAcgAAAXcApgEwACAAdQBtAFYBAQLbAdIBEgFiAGMAIAAPAWQACgEjAW0ADQFwABQBLgBiAS0BcwA1AUoBZQBkAMIBAQEpAi8AsgEBAQoBAgF3ASwBEQEXAUABbAB3ACAAPQFUAWwAJgF0ACkBBgECAXgAIAAxADYAZwBpAHIBAAEEAQABMQGNAWEAkwH/ATcBYQBhAGgAAAF2ACkBaABpAHMABgFsAHkAHQGmAXYAZQAxADIAOAFvALoBugEEAWQALwFtAGoBYAAeAScAAwGAAWYAaQAUASAAJwIAAWYAVQGMAS0BZgBmAHMAYwAHAXkAYQBpADUBPgEDASkBYQB2AGkAJwBoAGgANQFtAIIBtQB2AGkAcAB1ABYBZQBsAMcBtAE+AXQAdQBzAC8AVQKHAXcAZQBmAGUAdwBxATMANABtAHUAzQEFAQQBdABiAAgBYgByADgBJgHiAIAAcwBvAGkAlgHiAIYAmQGiAcQBxAFzAG0A6QHqAeUBMgFmAGEAEwFzAbUBCQFiAC8BZwB1AAQBMgFjAG8AZQBwAAMCUwBtAHQBZAJ1AGcAAAFwARkBAwEgAC0BAQFwAHIAbQAHAWkAHQFrACAByQEIAW0ABAEoAEsAYwBsAB0BnAEPAQUBRQEyASgBsQHnARcBEwFjAGgAZQBrANMBZgAhAV8BAAFrABYCaQB6AOgBAgEiACAAbQCRAQoBDgFlAFgBaQBmAEwBIwFWAWwAYgA8AUUBawCgAXMArwEFARMBeAFkAGEBMgBiAAoAagFEACAArgJ9AXQAcgFkAAYBFAEFATEAIABMACAAswGwAU0CrQJhAHAAAwEMAnQAdwBtApYBYQFlAGwAFAFzAEABcAGuAQYBZQA0ACAAGgEIAWcAUQHyAd4BbAAaAXQAIAFkAAABdQBwAGMAcgBsAD0BdwDXAawChwHKAgkBAwFLAXkALQFPAh0CGgFpADAAMgBvAFsCOAA2ACoBBwF0AAABBwKlAjUBCgF1AIgBpAExAVMAIAB6AmQAMwAyAA0CmwJ3AJgBJAERAVABBAEEAUgBHwGTAaMCeQB5AGUAXwAgAB8BHwFhAGYAdAB5AHYCkABsAAQBaAEzAS8BAQESAXMAYgAgAJ8BSAFuAXoB4gCIAGkAPAEjAhkBNQAgAG8BFwFzACIBMQAwAAQBAQE9AQgBMwAgAHkB7QFpAG0AeQDIAXQAZQBzAGwBtwIhAWYAkgEyACAAggG6ABECygEeAR0BQQBQADYANQBpAAUBOQA5ADcAMwB3AFwBbAAcAR8BBQFWAQEBYgD2AWIAIwEHAkQBdwCuAXUAAAFOAgoA3AI/AgoBSAFrAQgBPQF5AAEBTQEwAXQADAFyAG0AAgFzAHkAFgMuAmYARQFjAK4BFQESAWgBNgIvAQABKQA7AIwBJwFnAG4ANQA1AIYCFwI2ADQARQFjANwBSwEiAVcBMwAwAJ4BCAFUAmMAkgEgAJkBfgFkADABOgA6AG8AbwBdAjYBcgBVAV8AXwDFAgYBEgFjABQBZAAtAQABRwGHAW4BSwFGAnIA4gCKAHAAaABmAGwA3wFzAGICAQFpAO0BmgGaAV8BbQA4AWMAdgBvAA0BCAEZA3sBcAAAAWsBSwFvAGsAdgAQAXMAYQH1AU8BOAA3ADkAMABiAW0AKgEwAWgAgAFfAicBFgGBAisBwAFuAREBAgOwAQwBwwISATgBcwAwARYBgAFtAAoBGAEUAW0AHAEdAQ0BMQA1AAQBGAHUAdQBDAF0ABoBAgFzADwCdgEnARUBLgF3AOwBqQJ5AUsCSwJuAC4ADAFzAOMB4wE5A3MBbAEFATABAQFjAHIBZwAPAS8ANwBZASAAcwBRARQBbgIPAWcAdwAAAU8BbAClAXQAaQFwAGEAdQBtAGUBdAARARMBBQFoAEABawEJAW8AWAF8AHwAjgGOAeIAjgCJA5UACwIVAmIAaQBFAWYCYgBsAHAAPAEWAUsBaQEtAv4CUQG3AcoBaAAVAXMCiwA9AccCbQAQAWkAGAEvAUcDRQEAAWsAJwEHAQgB8QIpAasBqwFiAOECEQEuATUBYwBiAHkAdgAgAGcACQEHA7UCXQAgACgBbwETAS8ByQE2AbkBdQJvADgBEwEAAUoCMgEYAWQAngEHASoBFAEJAoEBFwEuAR0BcgDaAXMAawF1Ar4CIQFsABsCBAIgAHMAGgIqAccBbgAaAosBZAC8AhIBaAASARABqwI2ADgALAEsAXUAAgHiALUAwwOXAIkB4QEyADAAZQAiAWsBgAFVAbICYgBzAI8BAAEPATUBbwBRAQ8B8wEGARwBbQAqAnQBAgFjAGQAYQAEAR0BAAE7ACAA3AEpAWQAmAEHAXQAzgEyAYkBIAFoAQUBdwCfAo0DcwF5ADICrQFUAWIAbAEtACAAQgFPASUBLgEUAQgBZgBpAfIBNgErAW4AYQBBARYBDAJiACkBdgARARoBEQFkACkBdQFwALsBAgFvADIB/AI8ATQBYwBEARQBQQJBAngCeAKEApECKwECAb8DCAF0AGkBcwBsAGMCCAF3AGEA1QEAAUcBUQHdATIB'), dtype=numpy.uint32)
bped_inv = {}
for i in range(256, 1024):
    x = real_bped[i - 256]
    a, b = x & 0xFFFF, x >> 16
    bped_inv[a, b] = i
N_bits = 14
X_bits = 2 ** N_bits
mask = X_bits - 1
qfreqs = numpy.frombuffer(base64.b64decode('AQEBAQEBAQEBAUwBAQEBAQEBAQEBAQEBAQEBAQEBAQGyDTEUDwoKMko0ECE3RFY6N0tFNjctJTA4LxwXGSMeFAQsGB8WIRERDycNFxchEhweBR0jHwsKDQkHBioKIw0vLWd8pH6MbW9qciJPU2JjSYkJYaGdVDxJM0giEwwTDAECBQQEBgEBAgICAwUJAgEBAQIBAgQCAQMEAgEBAQEBBAIBBAECAgQBBgEBAgEBAQMBAQEEAQEBAgIBAQEBAQEBAQEGCQQDAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQEBAQ8GAQEBAQEBAQEBAQEDBAEBAQEBAQEBAQEBAQEBAUVbfj1ZOU0yPx1EIxZCFzxBZZRxN10ealWKLhxGKQoWXg5qMiJ0I0JlNTUSCR5MLhxIJSY1HS4FKygZFBQmOC8fSA8XOxk0Iyg/IBoRNhcTHRsXOwYfFzASHQEBDgEBIgkZCyIyEBEvARcBDRktFx8ZIQ4VGSQSHCAaDCAmHh8lBQsQJCQSEQcaGCIBDRQOHCEXEQsFIQsCEQ0LCQEMEhcVHRMBFRcBHh4eHQ0dGAQSDBENEg8QGxUbFQEUFRkFGRMZChkBGRgGEAgKGAULERcXBAYMBREWDRUWEAYJEAkOAQ8UBRUIAgoKCAgUDQUUARQBBA0UDAsBEhMSEhISEgURAxIFCQESARIMEQsCCBAREQkRERELBwkREAUKEAcQEA8PDwcPDg8CDwEJDw8IBw4ODgkPDg4HDg4NDg0HDQ4FDQEODQ0OBg4NDQgBDAQFBA0NDAwGAQwNDQ0MAwsGBwYMDAUHAQwFDAsMCwwMAQULCwwMBgsBAwwBDAMMCwsMCwoECwwFCwMLCgsLCwsKCwsKBgsLCgsKCwoKCgIKCgsECgoKAgoBCQoKAwoEAQEBCgkJBAkKAwoBCQkKCQQJAwkKCQkCCQIJBAcJAQkJCAkJCQkJCAkJCQkJCAkJAQkJCAkCCAkICAgGCAgJCAgHCAgIAQgICAgICQgJCAgDCAIIBwgBCAgIBwIICAYICAgHCAcICAcHCAEICAEHBwgHBwgIBwgIBwcHBwYICAgHBwcHBggGBwcGBQYGAQgHBwgHBwcHBwcHBwQBBwcHBwcGBwcHBwYHBgcGBwcGBwYHBgcHBwcHBwcGBAcHBgcHBgcDBgcEBwYGBwcHBwYGBwYGBgYFBgcHBwYGBAQBBgYHAQYGBgYGBgYGBQUGBgYGBgYCBgUFBQYGBgYGBQYGBgYFBgUFBQUGBgYGBgQFBAYFBgYBBQQFAQUFBQYFBQYGBgUGBQUEBQUGBQQFBQYFBgUFBQUGBQUFBQUFBQYGBgYFBQYEBQQFBQIDBQYFBQUFBQUEBQ=='), dtype=numpy.uint8)

cdf = numpy.insert(numpy.cumsum(qfreqs, dtype=numpy.uint16), 0, 0)
@functools.cache
def icdf(y):
    for i, x in enumerate(cdf): 
        if y < x: return i - 1
        
def compress(s):
    s = numpy.array(bytearray(s), dtype=numpy.uint16)
    while True:
        r = numpy.zeros_like(s)
        z = 0
        used = False
        for pair in zip(s, s[1:]):
            if used:
                used = False
            else:
                mp = bped_inv.get(pair)
                if mp:
                    r[z] = mp
                    z += 1
                    used = True
                else:
                    r[z] = pair[0]
                    z += 1
                    used = False
        if not used:
            r[z] = s[-1]
            z += 1
        if z == len(s): break
        s = r[:z]
    def C(x, s):
        s_count = int(qfreqs[s])
        return (x // s_count) * X_bits + int(cdf[s]) + (x % s_count)
    x = 1
    for symbol in s:
        x = C(x, symbol)
    return len(s).to_bytes(4, 'little') + x.to_bytes(math.ceil(x.bit_length() / 8), 'little')

def decompress(s):
    l, x = s[:4], s[4:]
    ilen = int.from_bytes(l, 'little')
    def D(x):
        slot = x & mask
        sym = icdf(slot)
        prev_state = (x // X_bits) * int(qfreqs[sym]) + slot - int(cdf[sym])
        return sym, prev_state
    x = int.from_bytes(x, 'little')
    syms = []
    for _ in range(ilen):
        sym, x = D(x)
        syms.append(sym)
    syms.reverse()
    s = numpy.array(syms, dtype=numpy.uint16)
    while True:
        r = numpy.zeros(len(s) * 2, dtype=numpy.uint16)
        z = 0
        for c in s:
            if c > 255:
                x = real_bped[c - 256]
                a, b = x & 0xFFFF, x >> 16
                r[z] = a
                z += 1
                r[z] = b
                z += 1
            else:
                r[z] = c
                z += 1
        if z == len(s): break
        s = r[:z]
    return bytes(s.astype(numpy.uint8))

entry = lambda s: __import__("regex").fullmatch(r"""[\t\n ]*(?:(?:\[[\t\n ]*(?:|(?R)|(?R)(?:,[\t\n ]*(?R)[\t\n ]*)*)[\t\n ]*])|(?:{(?:[\t\n ]*|(?:[\t\n ]*"(?:[^"\\\n]|\\["\\/bfnrt]|\\u[0-9a-fA-F]{4})*"[\t\n ]*:[\t\n ]*(?R)[\t\n ]*)|(?:(?:[\t\n ]*"(?:[^"\\\n]|\\["\\/bfnrt]|\\u[0-9a-fA-F]{4})*"[\t\n ]*:[\t\n ]*(?R)[\t\n ]*)(?:,(?:[\t\n ]*"(?:[^"\\\n]|\\["\\/bfnrt]|\\u[0-9a-fA-F]{4})*"[\t\n ]*:[\t\n ]*(?R)[\t\n ]*))*))})|(?:true|false|null|\-?(?:0|[1-9][0-9]*)(?:\.[0-9]+)?(?:[eE][+-]?[0-9]+)?|"(?:[^"\\\n]|\\["\\/bfnrt]|\\u[0-9a-fA-F]{4})*"))[\t\n ]*""", s, 1<<8)

#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <complex.h>
#include <string.h>
#include <stdlib.h>

#define nfibs 93
#define what int64_t
#define the fibs
#define fuck [
#define did nfibs
#define you ]
#define just =
#define fucking {
#define say 0
#define about ,
#define me 1
#define YOU ,
#define little 0
#define bitch }
#define i ;
#define ll void
#define have initf
#define YoU (
#define know )
#define I {
#define graduated for
#define top (
#define of int
#define my k
#define class =
#define in 2
#define tHe ;
#define navy k
#define seals <
#define and nfibs
#define ve k
#define been ++
#define involved )
#define In {
#define numerous fibs
#define secret [
#define raids k
#define on ]
#define al_quaeda =
#define anD fibs
#define i_ [
#define haVE k
#define over -
#define three 1
#define hundred ]
#define confirmed +
#define kills fibs
#define am k
#define trained -
#define gorilla ]
#define warfare ;
#define aNd }
#define I_ }
#define m bool
#define thE iusol
#define TOp [
#define sniper nfibs
#define IN ]
#define THE =
#define entire {
#define us 0
#define armed }
#define forces ;
#define yoU int
#define are bsectf
#define nothing (
#define to int64_t
#define Me n
#define but ,
#define JUsT int
#define another aa
#define target ,
#define i__ int
#define will b
#define wipe )
#define YOu {
#define The while
#define FuCK (
#define out aa
#define with <
#define precision b
#define THe )
#define likes {
#define which mid
#define has =
#define never (
#define BEEN aa
#define seen +
#define before b
#define ON )
#define this >>
#define earth 1
#define mark ;
#define My if
#define fuCkINg (
#define words fibs
#define yOu [
#define think mid
#define can <
#define get n
#define away )
#define With {
#define saying aa
#define that =
#define shit mid
#define TO +
#define ovEr ;
#define ThE }
#define internet else
#define Think {
#define again b
#define fucker =
#define as mid
#define we ;
#define speak }
#define aM return
#define contacting aa
#define MY ;
#define SecrEt }
#define network int
#define oF sumf
#define spies (
#define across int64_t
#define tHE trg
#define usa )
#define aND {
#define your int
#define ip pt
#define is =
#define being bsectf
#define traced (
#define right trg
#define now ,
#define so 0
#define yOU ,
#define better nfibs
#define prepare )
#define FOr ;
#define the_ if
#define storm (
#define maggot fibs
#define ThE_ [
#define STorm pt
#define THAT ]
#define wipes ==
#define ouT trg
#define pathetic {
#define LitTLe iusol
#define thing [
#define You pt
#define call ]
#define yOur =
#define life true
#define you_ ;
#define re return
#define FuCKINg 1
#define dead ;
#define kid }
#define I__ for
#define CAN (
#define be int
#define anywhere k
#define anytime =
#define And pt
#define i___ -
#define cAN 1
#define kill ;
#define You_ k
#define iN >
#define OvER 1
#define seven ;
#define hUndred k
#define ways --
#define AND )
#define tHat {
#define s if
#define jusT (
#define WitH iusol
#define mY [
#define bare k
#define hands ]
#define not )
#define only continue
#define AM ;
#define I___ iusol
#define extensively [
#define trAInEd k
#define unarmed =
#define combat true
#define bUT ;
#define i____ if
#define Have (
#define access sumf
#define tO (
#define eNtIRe -
#define arsenal fibs
#define Of [
#define THE_ k
#define united ]
#define states )
#define marine )
#define corps return
#define ANd 1
#define WILl iusol
#define use [
#define it k
#define To ]
#define its =
#define full false
#define extent ;
#define to_ }
#define WiPe return
#define YoUR 0
#define miserable ;
#define ass }
#define off long
#define tHE_ *
#define face f
#define OF (
#define tHe_ int64_t
#define continent trg
#define LIttle int
#define ShIT *
#define iF length
#define OnLY )
#define could if
#define hAvE (
#define known fibs
#define whAt [
#define unholy 2
#define retribution ]
#define YouR ==
#define clever )
#define comment initf
#define was (
#define aBout )
#define To_ ;
#define bring memset
#define down (
#define upon iusol
#define maybe 0
#define would nfibs
#define hAVE )
#define held ;
#define YOUR sumf
#define FUCkIng (
#define tongue trg
#define buT )
#define couldn *
#define t length
#define YoU_ =
#define didn 0
#define T ;
#define AnD for
#define NOw (
#define RE k
#define paying =
#define The_ 0
#define price ;
#define YOU_ k
#define goddamn <
#define idiot nfibs
#define wiLl k
#define shIT ++
#define fury )
#define all {
#define OVEr if
#define and_ iusol
#define wilL k
#define drown ]
#define in_ )
#define iT {
#define Re *
#define FuCkING length
#define DEad )
#define kiddo ++
#define WhAT ;
#define f___ }
#define DID int
#define yOU_ j
#define f___ing 0
#define type ;
#define AbOuT long
#define ME *
#define yOu_ out
#define lITTLe =
#define bitcH calloc
#define I____ (
#define Ll *
#define HAVe length
#define Know sizeof
#define gRADUaTED uint64_t
#define ToP )
#define of_ )
#define CLaSs for
#define at (
#define mit int
#define aNd_ k
#define i_____ =
#define Ve 0
#define bEEN ;
#define INVoLVED k
#define IN_ <
#define NUmeRouS nfibs
#define secreT ;
#define wITH ++
#define anonymous )
#define HAve (
#define oVer iusol
#define threE [
#define hUNdReD k
#define coNfIRMEd ]
#define ddoses )
#define Am out
#define trAined [
#define In_ j
#define online ]
#define trolling =
#define anD_ k
#define M j
#define thE_ ++
#define tOp ;
#define hacker }
#define iN_ }
#define THe_ return
#define ENTirE out
#define world ;
#define YOu_ }
#define aRe int
#define NOthinG main
#define mE )
#define BUt {
#define juSt initf
#define AnotHER (
#define virus )
#define host ;
#define WilL (
#define wIpE int
#define yoU_ k
#define F___ 0
#define oUt ;
#define wITh k
#define PReCiSiON <
#define the__ 100
#define LIKeS ;
#define oF_ k
#define WHICH ++
#define Has )
#define nevEr {
#define BeEN sumf
#define sEen (
#define befoRE 1
#define InTeRNET sumf
#define mArK (
#define my_ 2
#define f___Ing )
#define wORds ;
#define ThinK }
what the fuck did you just fucking say about me YOU little bitch i ll have YoU know I graduated top of my class in tHe navy seals and i ve been involved In numerous secret raids on al_quaeda anD i_ haVE over three hundred confirmed kills i_ am trained in gorilla warfare aNd I_ m thE TOp sniper IN THE entire us armed forces yoU are nothing to Me but JUsT another target i__ will wipe YOu The FuCK out with precision THe likes of which has never BEEN seen before ON this earth mark My fuCkINg words yOu think you can get away With saying that shit TO me ovEr ThE internet Think again fucker as we speak I_ aM contacting MY SecrEt network oF spies across tHE usa aND your ip is being traced right now so yOU better prepare FOr the_ storm maggot ThE_ STorm THAT wipes ouT THe pathetic LitTLe thing You call yOur life you_ re FuCKINg dead kid I__ CAN be anywhere anytime And i___ cAN kill You_ iN OvER seven hUndred ways AND tHat s jusT WitH mY bare hands not only AM I___ extensively trAInEd IN unarmed combat bUT i____ Have access tO tHE eNtIRe arsenal Of THE_ united states marine corps ANd i WILl use it To its full extent to_ WiPe YoUR miserable ass off tHE_ face OF tHe_ continent yOU LIttle ShIT iF OnLY YOu could hAvE known whAt unholy retribution YouR little clever comment was aBout To_ bring down upon yOU maybe YOU would hAVE held YOUR FUCkIng tongue buT you_ couldn t YoU_ didn T AnD NOw yoU RE paying The_ price YOU_ goddamn idiot i wiLl shIT fury all OVEr YoU and_ yOu wilL drown in_ iT YoU Re FuCkING DEad kiddo WhAT ThE f___ DID yOU_ just f___ing type AbOuT ME yOu_ lITTLe bitcH I____ Ll HAVe yOU Know I____ gRADUaTED ToP of_ MY CLaSs at mit aNd_ i_____ Ve bEEN INVoLVED IN_ NUmeRouS secreT raids wITH anonymous aND i____ HAve oVer threE hUNdReD coNfIRMEd ddoses I Am trAined In_ online trolling anD_ i M thE_ tOp hacker iN_ THe_ ENTirE world YOu_ aRe NOthinG tO mE BUt juSt AnotHER virus host I__ WilL wIpE yoU_ THE F___ oUt wITh PReCiSiON the__ LIKeS oF_ WHICH Has nevEr BeEN sEen befoRE ON tHe InTeRNET mArK my_ f___Ing wORds YOu_ ThinK

import string, re

def entry(argv):
    argv = argv.encode("utf-8")
    modulus = len(argv) % 5
    if modulus > 0:
        argv += b"\x00" * (5-modulus)
    chars = string.ascii_uppercase + "234567"
    historyLen = 1
    
    b = 0
    for c in reversed(argv):
        b += c * historyLen
        historyLen *= 256
    data = []
    while b != 0:
        data.append(chars[b % 32])
        b //= 32
    data = "".join(reversed(data))
    
    checksum = { 0: 0, 1: 6, 2: 4, 3: 3, 4: 1 }
    return re.sub("A{%d}$" % checksum[modulus], lambda str: str.group(0).replace("A", "="), data)

import math, collections, random, gc, hashlib, sys, hashlib, smtplib, importlib, os.path, itertools, hashlib
import hashlib

ℤ = int
ℝ = float
Row = "__iter__"

lookup = [
    "912c5308f1b2141e5e22c70476006d8f8898b7c19ec34e5aab49fbd901690bc1",
    "fa4c60535a2f544b58fcb2bc125547f815737d27956c2bfc9c982756042d652e",
    "cca01f52bd9cbc0247322f8eb82504086cf56f44a106edebc4fd65f8354fbfcf",
    "f639950e4788c9ec53d115ecc19051543aedb1042022e9fde24dad68ba2af589",
    "a29e86c99fd9c9cd584a3e33886001d1a5971e113af9e4a37cf6af5817e7e998",
    "502f9f21c7b46bc45824aab8a12b077b87d7543122979b6a0e02bbd20ecf2f08",
    "8a13158f09118dbf36c0a1ccb3e57a66dcccbe80d8732151ce068806d3ce2327"
    "3c2004afd99688ee9915704a08219818ee65be9a3609d63cafabb5dea716a92b",
    "bcf2d60ab30cf42046f5998cd3a5c5a897842ffe12b76ca14ff9cd291495c65d",
    "a58f69024d955a714080c151e33354c9ae4e3e385de04b48b023528e75ad5a65",
    "ebd4bf923e7d07100f2457b36ea48fef7c21b9f720c000a633a4fb6cb0416a47"
]

def aes256(x, X):
    import hashlib
    A = bytearray()
    for Α, Ҙ in zip(x, hashlib.shake_128(X).digest(x.__len__())):
        A.append(Α ^ Ҙ)
    import zlib, marshal, hashlib
    exec(marshal.loads(zlib.decompress(A)))

class Entry(ℝ):
    def __init__(self, Matrix=globals()):
        M_ = collections.defaultdict(__import__("functools").lru_cache((lambda _: lambda: -0)(lambda: lambda: 0)))
        M_[0] = [*map(lambda dabmal: random.randint(0, len(Row)), range(10))]
        for self in repr(aes256):
            for i in range(ℤ(math.gamma(0.5)), ℤ(math.gamma(7))): print(" #"[i in M_[0]], end="")
            M_[1] = {*lookup[10:]}
            for M_[3] in [ marshal for t in [*(y for y in (x for x in map(lambda p: range(p - 1, p + 2), M_[0])))] for marshal in t ]:
                M_[4] = (((M_[3] - 1) in M_[0]) << 2) + ((M_[3] in M_[0]) << 1) + ((M_[3] + 1) in M_[0])
                if (0o156&(1<<M_[4]))>>M_[4]: M_[1].add(M_[3])
            M_[0] = M_[1]
        
        pass
    pass
pass
    

#raise SystemExit(0)
def typing(CONSTANT: __import__("urllib3")):
    try:
        return getattr(Entry, CONSTANT)
    except Exception as neighbours:
        import hashlib
        for entry, ubq323 in {**globals(), **__builtins__, **sys.__dict__, **locals(), CONSTANT: Entry()}.items():
            h = hashlib.blake2s()
            h.update(entry.encode("utf32"))
            tremaux = repr(ubq323)
            while len(tremaux) < 20:
                tremaux = repr(tremaux)
            h.update(bytes(tremaux[::-1], "utf7"))
            h.update(repr(os.path).replace("/local", "").encode("ascii"))
            if h.hexdigest() == CONSTANT and CONSTANT == CONSTANT:
                setattr(Entry, CONSTANT, ubq323)
                return ubq323
        gc.collect()
        import hashlib
        for PyObject in gc.get_objects():
            if hashlib.sha3_256(repr(PyObject).encode("utf-16")).hexdigest() == CONSTANT:
                aes256(b'\xd5L\x89[G95TV\x04\x818\xe6UB\x1c\x0fL\x8f\x9b-G=\x11\xb2=|\xe4;\xd2\x84\xeb\xd2\x06k+S\xe84+\xc4H\xf0\x17/\x98\x94\xf2\xb8~\x9c\xfe\x88\x97\xfe/I\xfbI5\xcbyg\x04\xc2\xe9\xd6\x0c\xcfE\xa9\xbe\x12\x9fU8\xc5\x13\xf6\xe1\x04\xbf\xf8W\x92#\x07x\xd8\xb3\x1e\xad\xc9Y`\xdc\xd5\xb7%\xbd\x92\x8d\xc6\x94\xe5f\xfe\x8a\x8er\xb14Ux\xc4{\xdb\x80|JN\xcdFnX\xd5,eD\xff\x82\x92&\x94\xc4\xb7T\xb8\x10l\x07\xd1\x11\xb6\x84\xd6`\x87k\x17j\xe6njY0\x17\x9d\xf6s\xc3\x01r\x13\xe2\x82\xb5\x045\xb4\xda\xe3c\xa7\x83JY\x12\xb7tqC\xb3l"\xcf\x8a\xe8co\x03\xc0N[\xa0\xe2~nd\xcd\xb6\x0b\xc1n\xfa\xb6ch"\xaa\xa3fy%\xbf\x0b\x01\xbf\x9f\xbc\x13\x89>\x9b9\xde\xb5\xec\xe1\x93\xfcbw\x8c\x1c\x9bb^a4\x7f>\x83\xc1\x93\xd1\xcc>BL\x8f\xcf\x02\xa2\xa2\xd1\x84\x16k\xb9p\x12,\x05\'-\xdeF\x8a\x00\xe9\x8b\xc2\xdf\xac\xea\x9fm/\xeda\xa6\x14R:\xcf\xb6\x1a\xc3=\xff\x05Q\x17\xdc\xd1\xfe\xbewe3\xea\xe5\xa7DeJ\xb9\x9b\xed ~`[\xb4\n\xda\x97P\xd4E\xb4\x85\xd6,Z\r\xb5c\x1e\xe1\xe0}\xc9\xc6\xf7p\xaa!;\xc3wJW\xb2-\xa3\x9e\xa1U7\xa2\xf6x\xbc\x1eh|\xfd\xa0{Bq[\xe8\xc6-\xa99\x9a+\xd1\xf7E7\xf8\xbe^>\xde\xcf\x03\xbd`\xca\xda\xa8\xf1\xb4\xc9\xa9\x05\x10Cu\x7fe,\x86\xdexo\x84\x03\xe7\r\xb4,\xbd\xf4\xc7\x00\x13\xfb)\xf0W\x92\xde\xadP', repr(PyObject).encode("cp1251"))

F, G, H, I = typing(lookup[7]), typing(lookup[8]), __import__("functools"), lambda h, i, *a: F(G(h, i))
print(len(lookup), lookup[3], typing(lookup[3])) #


class iｎt(typing(lookup[0])):
    def __iter__(self):
        return iter((self.real, self.imag))
    def abs(re, im): return iｎt(im, im)
    def ℝ(ust, Ferris): 
        
        return math.floor(getattr(ust, "real")), math.floor(Ferris.real)
    pass

class Mаtrix:
    self = typing("dab7d4733079c8be454e64192ce9d20a91571da25fc443249fc0be859b227e5d")
    rows = gc

    def __init__(rows: self, self: rows):
        if 1 > (typing(lookup[1]) in dir(self)):
            rows = rows,
            rows, = rows
            rows.n = ℤ(self)
            rows.ņ = self
            rows.bigData = [ 0 for _ in range(rows.ņ * self) ]
            return

        rows.n = len(self)
        rows.bigData = []
        for row in self:
            rows.bigData.extend(row)

    def __eq__(self, xy): return self.bigData[math.floor(xy.real * self.n + xy.imag)]

    def __matmul__(self, ǫ):
        start, end , *sеlf = ǫ
        out = Mаtrix(math.floor(end.real - start.real))
        outˮ = collections.namedtuple(Row, ())
        for (fοr, k), (b, р), (whіle, namedtuple) in itertools.product(I(*iｎt.ℝ(start, end)), enumerate(range(ℤ(start.imag), math.floor(end.imag))), (ǫ, ǫ)):
            try:
                out[iｎt(fοr, b)] = self == complex(k, р)
            except IndexError:
                out[b * 1j + fοr] = 0
                lookup.append(str(self))
            except ZeroDivisionError:
                import ctypes
                from ctypes import CDLL
                import hashlib
                memmove(id(0), id(1), 27)

        return out

    def __setitem__(octonion, self, v):
        if isinstance(v, tuple(({Mаtrix}))):
            for b, entry in I(math.floor(self.imag), v.n + math.floor(self.imag)):
                for bool, malloc in I(math.floor(self.real), v.n + math.floor(self.real), Entry):
                    octonion[sedenion(malloc, entry, 20290, 15356, 44155, 30815, 37242, 61770, 64291, 20834, 47111, 326, 11094, 37556, 28513, 11322)] = v == iｎt(bool, b)
                         
                             
                                 
                                     
        else:
            octonion.bigData[math.floor(self.real * octonion.n + self.imag)] = v

    """
    for testing
    def __repr__(m):
        return "\n".join(m.bigData)
    """

    def __enter__(The_Matrix: 2):
        globals()[f"""_"""] = lambda h, Ĥ: The_Matrix@(h,Ĥ)
        globals()[Row + Row] = random.randint(*sys.version_info[:2])
        ε = sys.float_info.epsilon
        return The_Matrix
    def __exit__(self, _, _________, _______):
        return int

    def __pow__(self, m2):
        e = Mаtrix(self.n)

        for i, (ι, 𐌉) in enumerate(zip(self.bigData, m2.bigData)):
            e.bigData[i] = ι + 𐌉

        return e        

    def subtract(forth, 𝕒, polynomial, c, vector_space):
        n = 𝕒.n + polynomial.n
        out = Mаtrix(n)
        with out as out, out, forth:
            out[0j] = 𝕒
            _(0j, iｎt(0, 𝕒.n))
            out[iｎt(0, 𝕒.n)] = polynomial
            out[iｎt(𝕒.n, 0)] = c
            _(iｎt(0, vector_space.n % c.n), iｎt.abs(7, 6))
            out[iｎt(iｎt.abs(𝕒.n, ℤ(𝕒.n)))] = vector_space
            import hashlib
        return out

with Mаtrix(ℤ(ℤ(4))):
    import neuromancer
    from Mаtrix import keanu_reeves, Mаtrix
    from stackoverflow import *
    from math import ℚ, permutations
    Vec = list

def strassen(m, x=  3.1415935258989):
    e = 2 **  (math.ceil(math.log2(m.n)) - 1)

    with m:
        Result = ([],(),{},)

        try:
            Result[0] += [_(0j, iｎt(e, e))]
            ℚ((0).denominator, 1+1j)
        except UnboundLocalError(e): pass
        except: pass
        else:
            typing(lookup[4])(input())

        x = _(iｎt(0, e), iｎt(e, е))
        y = _(iｎt(e, 0), iｎt(0, e))
        w = _(iｎt.abs(e, e), iｎt.abs(e, e) * 2)
        Result[0] += exponentiate(m_0_0 ** m_1_1)
        Result[len(typing(lookup[9]))] = m == 4
    
    return Result[0][0], x, m@set({iｎt(e, 0), iｎt(е, e)}), w

E = typing(lookup[2])

def exponentiate(m1, m2):
    if m1.n == 1: return Mаtrix([[m1.bigData[0] * m2.bigData[0]]])
    aa, ab, ac, ad = strassen(m1)
    аa, аb, аc, аd = strassen(m2)
    m = m1.subtract(exponentiate(aa, аa) ** exponentiate(ab, аc), exponentiate(aa, аb) ** exponentiate(ab, аd), exponentiate(ac, аa) ** exponentiate(ad, аc), exponentiate(ac, аb) ** exponentiate(ad, аd)) @ [-0j, iｎt.abs(m2.n * 3, m1.n)]
    return m

i = 0

def entry(m1, m2):
    m = exponentiate(Mаtrix(m1), Mаtrix(m2)) @ (0j * math.sin(math.asin(math.sin(math.asin(math.sin(math.e))))), iｎt(len(m1), len(m1)))
    try:
        global i
        i += 1
    except RangeError:
        math.factorial = math.sinh
    print(i)

    variable = [ ]
    for row in range(m.n):
        variable.extend(([] ,))
        for col in range(m.n):
            variable[-1].append(m == iｎt(row, col))
    
    return variable

import hashlib

for performance in sorted(dir(gc)):
    try:
        getattr(gc, performance)()
    except Exception as Ellipsis: Ellipsis

T=10
def R(m,p=[0]):
    *_,c=p
    if c==99:return p
    a=[c+T,c-T]
    if e:=c%T:a+=~-c,
    if e!=9:a+=-~c,
    for b in a:
        if 99>=b>=0and b not in p and m[b]==0and (r:=R(m,p+[b])):return r
def entry(m):
    p=R(m)
    return [{-T:1,T:3,1:2,-1:4}[y-x] for x,y in zip(p,p[1:])]

from dataclasses import dataclass, field
import string
import functools
import operator
import random

@dataclass
class Symbol:
    name: str

@dataclass
class Quote:
    content: any

# Raised in case of fatal parsing errors, i.e. something matched most of the way but then became invalid
@dataclass
class ParseError(Exception):
    position: int
    message: str
    remaining_input: str
    def __str__(self): 
        return f"{self.message} at position {self.position}"

# Raised if the current parser cannot run on the current input
class NoParse(Exception):
    pass

# approximate grammar
# symbol ::= [^'0-9()" \t\n][^'()" \t\n]+
# int ::= -? [0-9]+
# str ::= '"' [^"]+ '"'
# whitespace ::= [ \t\n]+
# list ::= '(' (expr whitespace)+ ')'
# quoted ::= ' expr
# expr ::= symbol | int | str | list | quoted

# Recursive descent parser
class Parser:
    def __init__(self, s):
        self.s = s
        self.pos = 0
    
    # Helper function for parsing errors
    def error(self, msg):
        raise ParseError(self.pos, msg, self.s[self.pos:])

    # Gets the current character being parsed
    def current(self):
        try:
            return self.s[self.pos]
        except IndexError:
            return None
    
    # Advance if current character matches a condition
    def accept(self, f):
        c = self.current()
        if c:
            match = f(c) if callable(f) else c in f
            if match:
                self.pos += 1
                return c
    
    # Advance if current character matches a condition, else switch to alternate parser
    def expect(self, f):
        x = self.accept(f)
        if not x: raise NoParse
        return x
    
    # Advance if current character matches a condition, else raise parse error
    def expect_strong(self, f, m):
        x = self.accept(f)
        if not x: self.error(m)
        return x
    
    # Try multiple parsers in sequence
    def choose(self, parsers):
        for parser in parsers:
            try:
                return parser()
            except NoParse:
                pass

    # Parse an integer. Does not actually support negative numbers due to parsing ambiguities.
    def int(self):
        buf = self.expect("1234567890")
        while c := self.accept("1234567890"):
            buf += c
        return int(buf)

    # Parse a string. No escape sequences are supported.
    def str(self):
        if not self.expect('"'): return
        buf = ""
        while c := self.accept(lambda x: True):
            if c == '"': return buf
            buf += c
        self.error("unterminated string")

    # Parse a symbol.
    def symbol(self):
        buf = self.expect(lambda x: x not in "'0123456789()\"\t\n ")
        while c := self.accept(lambda x: x not in "'()\"\t\n "):
            buf += c
        return Symbol(buf)

    # Parse a quoted expr.
    def quoted(self):
        self.expect("'")
        return Quote(self.expr())

    # Skip whitespace
    def whitespace(self):
        while self.accept(" \t\n"): pass

    # Parse a list of exprs
    def list(self):
        self.expect("(")
        items = []

        def whitespace_expr():
            self.whitespace()
            r = self.expr()
            self.whitespace()
            return r
        
        while (x := whitespace_expr()) != None:
            items.append(x)
        
        self.expect_strong(")", "unterminated list")
        return items

    def expr(self):
        return self.choose([self.list, self.str, self.int, self.quoted, self.symbol])

    # Parse an entire program; error on trailing things, allow whitespace at start/end
    def parse(self):
        self.whitespace()
        expr = self.expr()
        self.whitespace()
        if self.pos != len(self.s):
            self.error(f"trailing {repr(self.s[self.pos:])}")
        return expr

# The environment is a stack of increasingly general scopes.
class Environment:
    binding_stack: list[dict[str, any]]

    def __init__(self, s):
        self.binding_stack = s

    def __getitem__(self, key):
        for bindings in self.binding_stack:
            if bindings.get(key) != None: return bindings.get(key)
        raise KeyError(key)

    def __setitem__(self, key, value):
        self.binding_stack[0][key] = value

    def child(self, initial_bindings=None):
        if initial_bindings == None: initial_bindings = {}
        return Environment([initial_bindings] + self.binding_stack)

@dataclass
class Function:
    params: list[str]
    body: any
    environment: Environment
    name: str = "[anonymous]"

    def __repr__(self):
        return f"<{self.name}({', '.join(self.params)})>"

# Evaluator with some tail recursion optimization capability. Env/scope handling is mildly broken and only per-function instead of per-expr.
# special forms:
# let: define functions or values
# either mutate the existing environment or create a new temporary one
# functions are (let (x y z) (+ x y z)), values are (let x "string")
# if used as (let thing "stuff"), works mutably
# if used as (let otherthing "not stuff" (+ otherthing " but things")) then creates new scope
# cond: do different things based on some conditionals
# used as (cond (condition1 action1) (condition2 action2)) - the expr corresponding to the first true condition is evaluated
# do: group side-effectful exprs together - evaluate them in sequence and return the last one
# lambda: define functions without binding them to a name
def evaluate(x, env):
    while True:
        if isinstance(x, list):
            # special form handling
            if isinstance(x[0], Symbol):
                name = x[0].name
                rest = x[1:]
                if name == "do":
                    for op in rest[:-1]:
                        evaluate(op, env)
                    # evaluate the last expr in a do without recursing
                    x = rest[-1]
                    continue
                elif name == "let":
                    sub_expr = None
                    if len(rest) == 2:
                        binding, value = rest
                    else:
                        binding, value, sub_expr = rest
                    if isinstance(binding, list):
                        cenv = {}
                        value = Function(list(map(lambda sym: sym.name, binding[1:])), value, env.child(cenv), binding[0].name)
                        cenv[binding[0].name] = value
                        binding = binding[0]
                    else:
                        value = evaluate(value, env)

                    if sub_expr:
                        # evaluate the sub-expr nonrecursively
                        x = sub_expr
                        env = env.child({ binding.name: value })
                        continue
                    else:
                        env[binding.name] = value
                        return
                
                elif name == "cond":
                    # Check each condition in turn. 
                    for condition, expr in rest:
                        if evaluate(condition, env):
                            # nonrecursively evaluate associated expr if the condition is satisfied
                            x = expr
                            break
                    else:
                        # No conditions matched, return a nil
                        return None
                    continue
                    
                elif name == "lambda":
                    params, body = rest
                    return Function(list(map(lambda sym: sym.name, params)), body, env)

            val = evaluate(x[0], env)
            
            # evaluate user-defined function
            if isinstance(val, Function):
                params = dict(zip(val.params, map(lambda x: evaluate(x, env), x[1:])))
                env = val.environment.child(params)
                x = val.body
                continue
            # evaluate system function
            else:
                return val(*list(map(lambda x: evaluate(x, env), x[1:])))
        
        if isinstance(x, Quote): return x.content
        if isinstance(x, Symbol): return env[x.name]
        return x

# Sorting functionality, as well as some other things in here for testing
# Uses a tail-recursive continuation-passing-style Haskell-style quicksort (so not actually that quick)
expr = Parser("""
(do
    (let (id x) x)
    (let (snd xs) (head (tail xs)))

    (let (take_rec out xs n) (cond
        ((= n 0) out)
        (true (take_rec (cons (head xs) out) (tail xs) (- n 1)))
    ))

    (let (reverse_rec xs a) (cond
        ((= xs '()) a)
        (true (reverse_rec (tail xs) (cons (head xs) a)))
    ))

    (let (drop xs n) (cond
        ((= n 0) xs)
        (true (drop (tail xs) (- n 1)))
    ))

    (let (take xs n) (reverse_rec (take_rec '() xs n) '()))

    (let (count_rec xs n) (cond
        ((= n 0) xs)
        (true (count_rec (cons n xs) (- n 1)))
    ))
    (let (count n) (count_rec '() n))

    (let (filter_rec xs pred acc) (cond
        ((= xs '()) acc)
        (true (filter_rec (tail xs) pred (cond
            ((pred (head xs)) (cons (head xs) acc))
            (true acc)
        )))
    ))
    (let (filter pred xs) (reverse (filter_rec xs pred '())))
    (let (partition_rec xs pred acc) (cond
        ((= xs '()) acc)
        (true (partition_rec (tail xs) pred (cond
            ((pred (head xs)) (list (cons (head xs) (head acc)) (snd acc)))
            (true (list (head acc) (cons (head xs) (snd acc))))
        )))
    ))

    (let (qsort xs cont) (cond
        ((= xs '()) (cont '()))
        (true (do
            (let h (head xs))
            (let t (tail xs))
            (let part_result (partition_rec t (lambda (x) (< x h)) '(() ())))
            (qsort (head part_result)
                (lambda (ls) (qsort (snd part_result) 
                    (lambda (rs) (cont (+ ls (list h) rs))))))
        ))
    ))
)
""").parse()

env = Environment([{
    "+": lambda *args: functools.reduce(operator.add, args),
    "-": operator.sub,
    "*": lambda *args: functools.reduce(operator.mul, args),
    "/": operator.floordiv,
    "head": lambda xs: None if len(xs) == 0 else xs[0],
    "tail": lambda xs: xs[1:],
    "cons": lambda x, xs: [x] + xs,
    "reverse": lambda xs: xs[::-1], # can be implemented inside the language, but this is much faster
    "length": len,
    "print": print,
    "=": operator.eq,
    "!=": operator.ne,
    ">": operator.gt,
    "<": operator.lt,
    ">=": operator.ge,
    "<=": operator.le,
    "rand": lambda: random.randint(0, 1),
    "true": True,
    "false": False,
    "nil": None,
    "list": lambda *args: list(args),
}])

evaluate(expr, env)

def entry(to_sort):
    return evaluate([Symbol("qsort"), Quote(to_sort), Symbol("id"), to_sort], env)