Addition of Big Integers

Given two integers $A$ and $B$, compute the sum, $A + B$.

Input

Two integers $A$ and $B$ separated by a space character are given in a line.

Output

Print the sum in a line.

Constraints

* $-1 \times 10^{100000} \leq A, B \leq 10^{100000}$



Sample Input 1


5 8


Sample Output 1


13


Sample Input 2


100 25


Sample Output 2


125


Sample Input 3


-1 1


Sample Output 3


0


Sample Input 4


12 -3


Sample Output 4


9






Example

Input

5 8


Output

13
/*input
50 -100
*/

// Don't change the base
const BASE: i32 = 1000;

// true sign for positive
// false sign for negative
#[derive(Clone, Debug)]
struct BigInteger {
    sign: bool,
    number: Vec<i32>,
}

impl BigInteger {
    fn new(number_string: String) -> BigInteger {
        let mut number_string = number_string;
        // check if it's a negative value or not by it's sign
        let sign = if number_string.chars().nth(0).unwrap() == '-' {
            false
        } else {
            true
        };
        // removing the sign if it exist
        if !sign || number_string.chars().nth(0).unwrap() == '+' {
            number_string.remove(0);
        }
        BigInteger {
            sign,
            number: BigUInteger::new(number_string).number,
        }
    }
}

// Substraction
impl std::ops::Sub for BigInteger {
    type Output = BigInteger;

    fn sub(self, other: BigInteger) -> BigInteger {
        //TODO: Only works for integer & integer
        // Implemented from: https://www.geeksforgeeks.org/difference-of-two-large-numbers/
        let mut other = BigInteger { ..other };
        let mut self_ = BigInteger { ..self };
        if BigUInteger::from_BigInteger(self_.clone()) < BigUInteger::from_BigInteger(other.clone())
        {
            std::mem::swap(&mut self_, &mut other);
        }
        // (1+) - (2+)
        if self_.sign && other.sign {
            BigInteger {
                sign: true,
                number: (BigUInteger::from_BigInteger(self_.clone())
                    - BigUInteger::from_BigInteger(other.clone()))
                .number,
            }
        // (1-) - (2-) == -((1+) - (2+))
        } else if !self_.sign && !other.sign {
            BigInteger {
                sign: false,
                number: (BigUInteger::from_BigInteger(self_.clone())
                    - BigUInteger::from_BigInteger(other.clone()))
                .number,
            }
        // (1-) - (2+) == -((1+) + (2+))
        } else if !self_.sign && other.sign {
            BigInteger {
                sign: false,
                number: (BigUInteger::from_BigInteger(self_.clone())
                    + BigUInteger::from_BigInteger(other.clone()))
                .number,
            }
        // (1+) - (2-) == (1+) + (2+)
        } else {
            BigInteger {
                sign: true,
                number: (BigUInteger::from_BigInteger(self_.clone())
                    + BigUInteger::from_BigInteger(other.clone()))
                .number,
            }
        }
    }
}

// Addition
impl std::ops::Add for BigInteger {
    type Output = BigInteger;

    fn add(self, other: BigInteger) -> BigInteger {
        // TODO: only works for self & other positive, self & other negative
        // implementation from https://www.geeksforgeeks.org/sum-two-large-numbers/
        let mut other = BigInteger { ..other };
        let mut self_ = BigInteger { ..self };
        // (1+) + (2+)
        if self_.sign == other.sign {
            BigInteger {
                sign: self_.sign,
                number: (BigUInteger::from_BigInteger(self_.clone())
                    + BigUInteger::from_BigInteger(other.clone()))
                .number,
            }
        } else {
            if BigUInteger::from_BigInteger(self_.clone())
                < BigUInteger::from_BigInteger(other.clone())
            {
                std::mem::swap(&mut self_, &mut other);
            }
            // (1+) +  (2-) == (1+) - (2+)
            if self_.sign && !other.sign {
                BigInteger {
                    sign: true,
                    number: (BigUInteger::from_BigInteger(self_.clone())
                        - BigUInteger::from_BigInteger(other.clone()))
                    .number,
                }
            // else !self_.sign && other.sign
            // (1-) + (2+) == -((1+) - (2+))
            } else {
                BigInteger {
                    sign: false,
                    number: (BigUInteger::from_BigInteger(self_.clone())
                        - BigUInteger::from_BigInteger(other.clone()))
                    .number,
                }
            }
        }
    }
}

impl std::cmp::Eq for BigInteger {}

impl std::cmp::PartialEq for BigInteger {
    fn eq(&self, other: &BigInteger) -> bool {
        self.sign == other.sign
            && BigUInteger::from_BigInteger(self.clone())
                == BigUInteger::from_BigInteger(other.clone())
    }
}

impl std::cmp::Ord for BigInteger {
    fn cmp(&self, other: &BigInteger) -> std::cmp::Ordering {
        if self.sign != other.sign {
            if !self.sign {
                std::cmp::Ordering::Less
            } else {
                std::cmp::Ordering::Greater
            }
        } else {
            if self.sign {
                BigUInteger::from_BigInteger(self.clone())
                    .cmp(&BigUInteger::from_BigInteger(other.clone()))
            } else {
                BigUInteger::from_BigInteger(other.clone())
                    .cmp(&BigUInteger::from_BigInteger(self.clone()))
            }
        }
    }
}

impl std::cmp::PartialOrd for BigInteger {
    fn partial_cmp(&self, other: &BigInteger) -> std::option::Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl std::fmt::Display for BigInteger {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        if self.sign {
            write!(
                f,
                "{}",
                BigUInteger::from_BigInteger(self.clone()).to_string()
            )
        } else {
            write!(
                f,
                "-{}",
                BigUInteger::from_BigInteger(self.clone()).to_string()
            )
        }
    }
}

//#################################################################################

/// Big Unsigned Integer

#[derive(Clone, Debug)]
struct BigUInteger {
    number: Vec<i32>,
}

impl BigUInteger {
    fn new(number_string: String) -> BigUInteger {
        let mut number_string = number_string;
        if number_string.chars().nth(0).unwrap() == '-'
            || number_string.chars().nth(0).unwrap() == '+'
        {
            number_string.remove(0);
        }
        let mut number_vector: Vec<i32> = Vec::new();
        let base_dig = (BASE as f64).log10() as usize;
        // backward version compatibility
        // .step_by(base_dig)
        for i in (base_dig..number_string.len() + 1)
            .rev()
            .filter(|x| x % base_dig == 0)
        {
            //println!("segment: {:?}", &number_string[i - base_dig..i]);
            let temp = &number_string[i - base_dig..i]
                .parse::<i32>()
                .unwrap()
                .clone();
            number_vector.push(*temp);
        }
        if number_string.len() % base_dig != 0 {
            let temp = &number_string[0..number_string.len() % base_dig]
                .parse::<i32>()
                .unwrap()
                .clone();
            number_vector.push(*temp);
        }
        BigUInteger {
            number: number_vector.iter().rev().map(|&x| x).collect::<Vec<i32>>(),
        }
    }

    // dropping the sign
    #[allow(non_snake_case)]
    fn from_BigInteger(big_integer: BigInteger) -> BigUInteger {
        BigUInteger {
            number: big_integer.number,
        }
    }

    fn to_string(&self) -> String {
        let mut output_string: String = self
            .number
            .iter()
            .map(|&x| format!("{:03}", x))
            .collect::<Vec<String>>()
            .join("");
        while &output_string[0..1] == "0" && output_string.len() > 1 {
            output_string.remove(0);
        }
        output_string
    }
}

impl std::ops::Sub for BigUInteger {
    type Output = BigUInteger;

    fn sub(self, other: BigUInteger) -> BigUInteger {
        //TODO: Only works for integer & integer
        // Implemented from: https://www.geeksforgeeks.org/difference-of-two-large-numbers/
        let mut other = BigUInteger { ..other };
        let mut self_ = BigUInteger { ..self };
        if self_.number.len() > other.number.len() {
            std::mem::swap(&mut self_, &mut other);
        }
        let mut number_output: Vec<i32> = Vec::new();
        let digit_difference = other.number.len() - self_.number.len();
        let mut carry: i32 = 0;
        for i in (0..other.number.len()).rev() {
            let mut sub =
                self_.number[i + digit_difference] - other.number[i + digit_difference] - carry;
            if sub < 0 {
                sub = sub + BASE;
                carry = 1;
            } else {
                carry = 0;
            }
            number_output.push(sub);
        }
        for i in (0..self_.number.len() - other.number.len()).rev() {
            if self_.number[i] == 0 && carry != 0 {
                number_output.push(BASE - 1);
                continue;
            }
            let sub = self_.number[i] - carry;
            if i > 0 || sub > 0 {
                number_output.push(sub);
            }
            carry = 0;
        }
        BigUInteger {
            number: number_output.iter().rev().map(|&x| x).collect::<Vec<i32>>(),
        }
    }
}

impl std::ops::Add for BigUInteger {
    type Output = BigUInteger;

    fn add(self, other: BigUInteger) -> BigUInteger {
        // TODO: only works for self & other positive, self & other negative
        // implementation from https://www.geeksforgeeks.org/sum-two-large-numbers/
        let mut other = BigUInteger { ..other };
        let mut self_ = BigUInteger { ..self };
        if self_.number.len() > other.number.len() {
            std::mem::swap(&mut self_, &mut other);
        }
        let mut number_output: Vec<i32> = Vec::new();
        let digit_difference = other.number.len() - self_.number.len();
        let mut carry: i32 = 0;
        for i in (0..self_.number.len()).rev() {
            let sum = self_.number[i] + other.number[i + digit_difference] + carry;
            number_output.push(sum % BASE);
            carry = sum / BASE;
        }
        for i in (0..other.number.len() - self_.number.len()).rev() {
            let sum = other.number[i] + carry;
            number_output.push(sum % BASE);
            carry = sum / BASE;
        }
        if carry != 0 {
            number_output.push(carry);
        }
        BigUInteger {
            number: number_output.iter().rev().map(|&x| x).collect::<Vec<i32>>(),
        }
    }
}

impl std::cmp::Eq for BigUInteger {}

impl std::cmp::PartialEq for BigUInteger {
    fn eq(&self, other: &BigUInteger) -> bool {
        self.number == other.number
    }
}

impl std::cmp::Ord for BigUInteger {
    fn cmp(&self, other: &BigUInteger) -> std::cmp::Ordering {
        if self.number.len() < other.number.len() {
            std::cmp::Ordering::Less
        } else if self.number.len() > other.number.len() {
            std::cmp::Ordering::Greater
        } else {
            for (self_i, other_i) in self.number.iter().zip(&other.number) {
                if self_i < &other_i {
                    return std::cmp::Ordering::Less;
                } else if self_i > &other_i {
                    return std::cmp::Ordering::Greater;
                }
            }
            std::cmp::Ordering::Equal
        }
    }
}

impl std::cmp::PartialOrd for BigUInteger {
    fn partial_cmp(&self, other: &BigUInteger) -> std::option::Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl std::fmt::Display for BigUInteger {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.to_string())
    }
}

//##################################################################################

fn main() {
    let mut input: String = String::new();
    std::io::stdin().read_line(&mut input).ok();
    input.pop();
    let num_l: Vec<String> = input
        .split_whitespace()
        .map(|x| x.to_string())
        .collect::<Vec<String>>();
    println!(
        "{}",
        BigInteger::new(num_l[0].clone()) + BigInteger::new(num_l[1].clone())
    );
    /*println!("BigUInteger");
    println!("Left: {0} {0:?}", BigUInteger::new(num_l[0].clone()));
    println!("Right: {0} {0:?}", BigUInteger::new(num_l[1].clone()));
    println!(
        "Left BigUInteger from Left BigInteger: {0} {0:?}",
        BigUInteger::from_BigInteger(BigInteger::new(num_l[0].clone()))
    );
    println!(
        "Right BigUInteger from Left Right: {0} {0:?}",
        BigUInteger::from_BigInteger(BigInteger::new(num_l[1].clone()))
    );
    println!(
        "Left + Right: {0} {0:?}",
        BigUInteger::new(num_l[0].clone()) + BigUInteger::new(num_l[1].clone())
    );
    println!(
        "Left - Right: {0} {0:?}",
        BigUInteger::new(num_l[0].clone()) - BigUInteger::new(num_l[1].clone())
    );
    println!(
        "Left < Right: {:?}",
        BigUInteger::new(num_l[0].clone()) < BigUInteger::new(num_l[1].clone())
    );
    println!(
        "Left > Right: {:?}",
        BigUInteger::new(num_l[0].clone()) > BigUInteger::new(num_l[1].clone())
    );
    println!(
        "Left == Right: {:?}",
        BigUInteger::new(num_l[0].clone()) == BigUInteger::new(num_l[1].clone())
    );
    println!("BigInteger");
    println!("Left: {0} {0:?}", BigInteger::new(num_l[0].clone()));
    println!("Right: {0} {0:?}", BigInteger::new(num_l[1].clone()));
    println!(
        "Left + Right: {0} {0:?}",
        BigInteger::new(num_l[0].clone()) + BigInteger::new(num_l[1].clone())
    );
    println!(
        "Left - Right: {0} {0:?}",
        BigInteger::new(num_l[0].clone()) - BigInteger::new(num_l[1].clone())
    );
    println!(
        "Left < Right: {:?}",
        BigInteger::new(num_l[0].clone()) < BigInteger::new(num_l[1].clone())
    );
    println!(
        "Left > Right: {:?}",
        BigInteger::new(num_l[0].clone()) > BigInteger::new(num_l[1].clone())
    );
    println!(
        "Left == Right: {:?}",
        BigInteger::new(num_l[0].clone()) == BigInteger::new(num_l[1].clone())
    );*/
}

