diff --git a/.gitlab/ci/pipelines/before_merging.yml b/.gitlab/ci/pipelines/before_merging.yml index b24cbf891888d2621df9a0698c027fdd7008e69c..e2d94a5ed7c62efb95085636298140bae741753c 100644 --- a/.gitlab/ci/pipelines/before_merging.yml +++ b/.gitlab/ci/pipelines/before_merging.yml @@ -2882,7 +2882,8 @@ test_evm_compatibility: - . ./scripts/ci/sccache-start.sh script: - make -f etherlink.mk EVM_EVALUATION_FEATURES=disable-file-logs evm-evaluation-assessor - - git clone --depth 1 --branch v13 https://github.com/ethereum/tests ethereum_tests + - git clone --depth 1 --branch v14.1@etherlink https://github.com/functori/tests + ethereum_tests - ./evm-evaluation-assessor --eth-tests ./ethereum_tests/ --resources ./etherlink/kernel_evm/evm_evaluation/resources/ -c after_script: diff --git a/.gitlab/ci/pipelines/merge_train.yml b/.gitlab/ci/pipelines/merge_train.yml index e671e0763b0051c1e041beda8c8dea2253136376..b5229b53d6eb11770b63a53a4939ea1cb115f12d 100644 --- a/.gitlab/ci/pipelines/merge_train.yml +++ b/.gitlab/ci/pipelines/merge_train.yml @@ -2881,7 +2881,8 @@ test_evm_compatibility: - . ./scripts/ci/sccache-start.sh script: - make -f etherlink.mk EVM_EVALUATION_FEATURES=disable-file-logs evm-evaluation-assessor - - git clone --depth 1 --branch v13 https://github.com/ethereum/tests ethereum_tests + - git clone --depth 1 --branch v14.1@etherlink https://github.com/functori/tests + ethereum_tests - ./evm-evaluation-assessor --eth-tests ./ethereum_tests/ --resources ./etherlink/kernel_evm/evm_evaluation/resources/ -c after_script: diff --git a/.gitlab/ci/pipelines/schedule_extended_test.yml b/.gitlab/ci/pipelines/schedule_extended_test.yml index b0e4d1bb3e68ecbe42a36502374728036f227af0..733bbd182dac6b692a48c49e8fb7c24a1f3607d0 100644 --- a/.gitlab/ci/pipelines/schedule_extended_test.yml +++ b/.gitlab/ci/pipelines/schedule_extended_test.yml @@ -2524,7 +2524,8 @@ test_evm_compatibility: - . ./scripts/ci/sccache-start.sh script: - make -f etherlink.mk EVM_EVALUATION_FEATURES=disable-file-logs evm-evaluation-assessor - - git clone --depth 1 --branch v13 https://github.com/ethereum/tests ethereum_tests + - git clone --depth 1 --branch v14.1@etherlink https://github.com/functori/tests + ethereum_tests - ./evm-evaluation-assessor --eth-tests ./ethereum_tests/ --resources ./etherlink/kernel_evm/evm_evaluation/resources/ -c after_script: diff --git a/ci/bin/code_verification.ml b/ci/bin/code_verification.ml index f4b5e69071eddb5868c8a79ee4b3cfb1b34209ac..1d5780a9d1df24ed23eef8a23c264590d7c3a1ef 100644 --- a/ci/bin/code_verification.ml +++ b/ci/bin/code_verification.ml @@ -3,6 +3,7 @@ (* SPDX-License-Identifier: MIT *) (* Copyright (c) 2024 Nomadic Labs. *) (* Copyright (c) 2024-2025 TriliTech *) +(* Copyright (c) 2025 Functori *) (* *) (*****************************************************************************) @@ -1746,8 +1747,8 @@ let jobs pipeline_type = [ "make -f etherlink.mk EVM_EVALUATION_FEATURES=disable-file-logs \ evm-evaluation-assessor"; - "git clone --depth 1 --branch v13 \ - https://github.com/ethereum/tests ethereum_tests"; + "git clone --depth 1 --branch v14.1@etherlink \ + https://github.com/functori/tests ethereum_tests"; "./evm-evaluation-assessor --eth-tests ./ethereum_tests/ \ --resources ./etherlink/kernel_evm/evm_evaluation/resources/ -c"; ] diff --git a/etherlink/CHANGES_KERNEL.md b/etherlink/CHANGES_KERNEL.md index aeb7c1305db65fb442c6357cff9d981f5e7d9463..e35ef2abad988e40364682ed1856b587d5786cfb 100644 --- a/etherlink/CHANGES_KERNEL.md +++ b/etherlink/CHANGES_KERNEL.md @@ -14,6 +14,14 @@ - The EVM is now refunding accounts as expected during inter (layer) transactions. (!16973) +### Features + +- The EVM's configuration has been bumped to Cancun. (!16141)\ + The following EIPs are now supported by Etherlink: + * [EIP-1153](https://eips.ethereum.org/EIPS/eip-1153) + * [EIP-5656](https://eips.ethereum.org/EIPS/eip-5656) + * [EIP-6780](https://eips.ethereum.org/EIPS/eip-6780) + ### Internal - Rework block production to simplify data flow and remove unnecessary diff --git a/etherlink/kernel_bifrost/evm_execution/src/handler.rs b/etherlink/kernel_bifrost/evm_execution/src/handler.rs index 56c6db525de826ab94f3bd4b18aa2f3ccb1a843a..eb73ba11c9a516ce9bd7e6053352455b155c37d3 100644 --- a/etherlink/kernel_bifrost/evm_execution/src/handler.rs +++ b/etherlink/kernel_bifrost/evm_execution/src/handler.rs @@ -2816,6 +2816,27 @@ impl<'a, Host: Runtime> Handler for EvmHandler<'a, Host> { self.record_dynamic_cost(cost, memory_cost) } } + + fn transient_storage(&self, _address: H160, _index: H256) -> H256 { + panic!("Not available on bifrost") + } + + fn blob_hash(&self, _index: H256) -> H256 { + panic!("Not available on bifrost") + } + + fn block_blob_base_fee(&self) -> U256 { + panic!("Not available on bifrost") + } + + fn set_transient_storage( + &mut self, + _address: H160, + _index: H256, + _value: H256, + ) -> Result<(), ExitError> { + panic!("Not available on bifrost") + } } #[cfg(test)] diff --git a/etherlink/kernel_calypso/evm_execution/src/handler.rs b/etherlink/kernel_calypso/evm_execution/src/handler.rs index bd921edbe1aff0d5915a88fca79691fef8d0de0a..81fa4be8e4d1a2c0194caa58a43f4f3c0f4e36eb 100644 --- a/etherlink/kernel_calypso/evm_execution/src/handler.rs +++ b/etherlink/kernel_calypso/evm_execution/src/handler.rs @@ -2861,6 +2861,27 @@ impl<'a, Host: Runtime> Handler for EvmHandler<'a, Host> { self.record_dynamic_cost(cost, memory_cost) } } + + fn transient_storage(&self, _address: H160, _index: H256) -> H256 { + panic!("Not available on calypso") + } + + fn blob_hash(&self, _index: H256) -> H256 { + panic!("Not available on calypso") + } + + fn block_blob_base_fee(&self) -> U256 { + panic!("Not available on calypso") + } + + fn set_transient_storage( + &mut self, + _address: H160, + _index: H256, + _value: H256, + ) -> Result<(), ExitError> { + panic!("Not available on calypso") + } } #[cfg(test)] diff --git a/etherlink/kernel_evm/ethereum/src/block.rs b/etherlink/kernel_evm/ethereum/src/block.rs index a315867b2551197f443e1f76f8b76606f75ed0ed..fa5f117e032fb8957bd2d99925729d5442b44ba9 100644 --- a/etherlink/kernel_evm/ethereum/src/block.rs +++ b/etherlink/kernel_evm/ethereum/src/block.rs @@ -23,6 +23,7 @@ pub struct BlockFees { minimum_base_fee_per_gas: U256, base_fee_per_gas: U256, da_fee_per_byte: U256, + blob_base_fee: U256, } impl BlockFees { @@ -36,6 +37,11 @@ impl BlockFees { minimum_base_fee_per_gas, base_fee_per_gas, da_fee_per_byte, + // Etherlink doesn't support blob as defined by + // EIP-7516. + // As such, the following value will always return + // zero. + blob_base_fee: U256::zero(), } } @@ -56,6 +62,11 @@ impl BlockFees { pub const fn da_fee_per_byte(&self) -> U256 { self.da_fee_per_byte } + + #[inline(always)] + pub const fn blob_base_fee(&self) -> U256 { + self.blob_base_fee + } } /// All data for an Ethereum block. @@ -109,6 +120,11 @@ impl BlockConstants { pub const fn base_fee_per_gas(&self) -> U256 { self.block_fees.base_fee_per_gas } + + #[inline(always)] + pub const fn blob_base_fee(&self) -> U256 { + self.block_fees.blob_base_fee + } } #[derive(Debug, PartialEq, Eq, Clone)] diff --git a/etherlink/kernel_evm/evm_evaluation/Cargo.toml b/etherlink/kernel_evm/evm_evaluation/Cargo.toml index 841471ee6386097f0d42b94c33b3006206cc87f9..d670e7e14846c60b2516a5624026bc57908dad58 100644 --- a/etherlink/kernel_evm/evm_evaluation/Cargo.toml +++ b/etherlink/kernel_evm/evm_evaluation/Cargo.toml @@ -19,7 +19,7 @@ tezos-smart-rollup-mock.workspace = true tezos-smart-rollup-host.workspace = true tezos-smart-rollup-core.workspace = true -hex.workspace = true +hex = { version = "0.4.3", features = ["serde"] } hex-literal.workspace = true bytes = "1.5" diff --git a/etherlink/kernel_evm/evm_evaluation/resources/skip_data.yml b/etherlink/kernel_evm/evm_evaluation/resources/skip_data.yml index 42c9594145e4e07ef685b4d06447314560032a2a..0aa059228b57f0a586fcccdd362beb76ae375575 100644 --- a/etherlink/kernel_evm/evm_evaluation/resources/skip_data.yml +++ b/etherlink/kernel_evm/evm_evaluation/resources/skip_data.yml @@ -5,4 +5,12 @@ datas: # when we exceed the max init code limit. # Other tests behave in the same way and we're passing them, we are also passing # this test but it expects an exception when it shouldn't. - - 601080600b6000396000f360606040523615610074576000357c010000000000000000000000000000000000000000000000000000000090048063a3b9f3e514610079578063b50345b61461008d578063d4f639ea146100a1578063d9bb316f146100b5578063e22a5d5b146100c9578063f983c0fa146100dd57610074565b610002565b346100025761008b60048050506100f1565b005b346100025761009f6004805050611097565b005b34610002576100b3600480505061203d565b005b34610002576100c76004805050612fe3565b005b34610002576100db6004805050613f89565b005b34610002576100ef6004805050614f2f565b005b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b505660606040523615610074576000357c010000000000000000000000000000000000000000000000000000000090048063a3b9f3e514610079578063b50345b61461008d578063d4f639ea146100a1578063d9bb316f146100b5578063e22a5d5b146100c9578063f983c0fa146100dd57610074565b610002565b346100025761008b60048050506100f1565b005b346100025761009f6004805050611097565b005b34610002576100b3600480505061203d565b005b34610002576100c76004805050612fe3565b005b34610002576100db6004805050613f89565b005b34610002576100ef6004805050614f2f565b005b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b505660606040523615610074576000357c010000000000000000000000000000000000000000000000000000000090048063a3b9f3e514610079578063b50345b61461008d578063d4f639ea146100a1578063d9bb316f146100b5578063e22a5d5b146100c9578063f983c0fa146100dd57610074565b610002565b346100025761008b60048050506100f1565b005b346100025761009f6004805050611097565b005b34610002576100b3600480505061203d565b005b34610002576100c76004805050612fe3565b005b34610002576100db6004805050613f89565b005b34610002576100ef6004805050614f2f565b005b60007310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000 + creationTxInitCodeSizeLimit: + - 601080600b6000396000f360606040523615610074576000357c010000000000000000000000000000000000000000000000000000000090048063a3b9f3e514610079578063b50345b61461008d578063d4f639ea146100a1578063d9bb316f146100b5578063e22a5d5b146100c9578063f983c0fa146100dd57610074565b610002565b346100025761008b60048050506100f1565b005b346100025761009f6004805050611097565b005b34610002576100b3600480505061203d565b005b34610002576100c76004805050612fe3565b005b34610002576100db6004805050613f89565b005b34610002576100ef6004805050614f2f565b005b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b505660606040523615610074576000357c010000000000000000000000000000000000000000000000000000000090048063a3b9f3e514610079578063b50345b61461008d578063d4f639ea146100a1578063d9bb316f146100b5578063e22a5d5b146100c9578063f983c0fa146100dd57610074565b610002565b346100025761008b60048050506100f1565b005b346100025761009f6004805050611097565b005b34610002576100b3600480505061203d565b005b34610002576100c76004805050612fe3565b005b34610002576100db6004805050613f89565b005b34610002576100ef6004805050614f2f565b005b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b50565b6000731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000008905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000000990508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000000109050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000101905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010290508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001039050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000104905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010590508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001069050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000107905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010890508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001099050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000110905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020190508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002029050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000203905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020490508050731000000000000000000000000000000000000205905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000206905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020790508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002089050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000209905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000021090508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003019050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000302905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030390508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003049050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000305905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030690508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003079050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000308905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000030990508050731000000000000000000000000000000000000310905080507310000000000000000000000000000000000003109050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000001905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000290508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000039050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000004905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000590508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000069050805073100000000000000000000000000000000000000790508050731000000000000000000000000000000000000007905080507310000000000000000000000000000000000000089050805073100000000000000000000000000000000000000890508050731000000000000000000000000000000000000009905080507310000000000000000000000000000000000000099050805073100000000000000000000000000000000000001090508050731000000000000000000000000000000000000010905080507310000000000000000000000000000000000001019050805073100000000000000000000000000000000000010190508050731000000000000000000000000000000000000102905080507310000000000000000000000000000000000001029050805073100000000000000000000000000000000000010390508050731000000000000000000000000000000000000103905080507310000000000000000000000000000000000001049050805073100000000000000000000000000000000000010490508050731000000000000000000000000000000000000105905080507310000000000000000000000000000000000001059050805073100000000000000000000000000000000000010690508050731000000000000000000000000000000000000106905080507310000000000000000000000000000000000001079050805073100000000000000000000000000000000000010790508050731000000000000000000000000000000000000108905080507310000000000000000000000000000000000001089050805073100000000000000000000000000000000000010990508050731000000000000000000000000000000000000109905080507310000000000000000000000000000000000001109050805073100000000000000000000000000000000000011090508050731000000000000000000000000000000000000201905080507310000000000000000000000000000000000002019050805073100000000000000000000000000000000000020290508050731000000000000000000000000000000000000202905080507310000000000000000000000000000000000002039050805073100000000000000000000000000000000000020390508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002049050805073100000000000000000000000000000000000020590508050731000000000000000000000000000000000000204905080507310000000000000000000000000000000000002069050805073100000000000000000000000000000000000020690508050731000000000000000000000000000000000000207905080507310000000000000000000000000000000000002079050805073100000000000000000000000000000000000020890508050731000000000000000000000000000000000000208905080507310000000000000000000000000000000000002099050805073100000000000000000000000000000000000020990508050731000000000000000000000000000000000000210905080507310000000000000000000000000000000000002109050805073100000000000000000000000000000000000030190508050731000000000000000000000000000000000000301905080507310000000000000000000000000000000000003029050805073100000000000000000000000000000000000030290508050731000000000000000000000000000000000000303905080507310000000000000000000000000000000000003039050805073100000000000000000000000000000000000030490508050731000000000000000000000000000000000000304905080507310000000000000000000000000000000000003059050805073100000000000000000000000000000000000030590508050731000000000000000000000000000000000000306905080507310000000000000000000000000000000000003069050805073100000000000000000000000000000000000030790508050731000000000000000000000000000000000000307905080507310000000000000000000000000000000000003089050805073100000000000000000000000000000000000030890508050731000000000000000000000000000000000000309905080507310000000000000000000000000000000000003099050805073100000000000000000000000000000000000031090508050731000000000000000000000000000000000000310905080505b505660606040523615610074576000357c010000000000000000000000000000000000000000000000000000000090048063a3b9f3e514610079578063b50345b61461008d578063d4f639ea146100a1578063d9bb316f146100b5578063e22a5d5b146100c9578063f983c0fa146100dd57610074565b610002565b346100025761008b60048050506100f1565b005b346100025761009f6004805050611097565b005b34610002576100b3600480505061203d565b005b34610002576100c76004805050612fe3565b005b34610002576100db6004805050613f89565b005b34610002576100ef6004805050614f2f565b005b60007310000000000000000000000000000000000000019050805073100000000000000000000000000000000000000190508050731000000000000000000000000000000000000002905080507310000000000000000000000000000000000000029050805073100000000000000000000000000000000000000390508050731000000000000000000000000000000000000003905080507310000000000000000000000000000000000000049050805073100000000000000000000000000000000000000490508050731000000000000000000000000000000000000005905080507310000000000000000000000000000000000000059050805073100000000000000000000000000000000000000690508050731000000000000000000000000000000000000006905080507310000000000000000000000000000000000000079050805073100000000000000000000000000000000000 + # The following tests are relying on specific BLOBBASEFEE values which we don't support + # on Etherlink. + opc4ADiffPlaces: + - 693c61390000000000000000000000000000000000000000000000000000000000000000 + - 693c613900000000000000000000000000000000000000000000000000000000000000fd + - 693c613900000000000000000000000000000000000000000000000000000000000000fe + - 693c613900000000000000000000000000000000000000000000000000000000000000ff diff --git a/etherlink/kernel_evm/evm_evaluation/src/main.rs b/etherlink/kernel_evm/evm_evaluation/src/main.rs index 7c04a468867de94369d56f0a84768c5c9a61e56c..8dbe7a7127738a9b90aaad7f537c0befb32aac0e 100644 --- a/etherlink/kernel_evm/evm_evaluation/src/main.rs +++ b/etherlink/kernel_evm/evm_evaluation/src/main.rs @@ -330,6 +330,21 @@ fn generate_diff( pub fn check_skip(test_file_path: &Path) -> bool { let file_name = test_file_path.file_name().unwrap().to_str().unwrap(); + let test_path = test_file_path.to_str().unwrap(); + + let skip_blob_tests = [ + "stEIP4844-blobtransactions", + "eip7516_blobgasfee", + "eip4844_blobs", + ]; + + // Reason: Etherlink doesn't support blob related features. + if skip_blob_tests + .iter() + .any(|folder| test_path.contains(folder)) + { + return true; + } matches!( file_name, @@ -337,8 +352,18 @@ pub fn check_skip(test_file_path: &Path) -> bool { | "CALLBlake2f_MaxRounds.json" // ✔ | "loopMul.json" // ✔ + // TODO: The two following tests should be investigated. + // Context: bugs were discovered thanks to the more finer-grained + // generated filler files, these bugs existed prior to Cancun. + // They are temporarily skipped and will be fixed seperatly. + // See: https://gitlab.com/tezos/tezos/-/issues/7817. + | "randomStatetestDEFAULT-Tue_07_58_41-15153-575192.json" + | "randomStatetestDEFAULT-Tue_07_58_41-15153-575192_london.json" + // Reason: chainId is tested for ethereum mainnet (1) not for etherlink (1337) | "chainId.json" + | "chainid_1.json" + | "chainid_0.json" // Reason: we temporarily reduce stack limit to 256. | "Call1024PreCalls.json" @@ -380,6 +405,13 @@ pub fn check_skip(test_file_path: &Path) -> bool { | "transactionCosts.json" | "variedContext.json" + // Reason: relying on precompile contract kzg_point_evaluation from + // EIP-4844 which we don't support. + | "value_transfer_gas_calculation_0.json" + | "value_transfer_gas_calculation_1.json" + | "value_transfer_gas_calculation_2.json" + | "value_transfer_gas_calculation_3.json" + // Reason: those test the refund mechanism // see https://gitlab.com/tezos/tezos/-/merge_requests/11835 | "refund_getEtherBack.json" @@ -391,6 +423,14 @@ pub fn check_skip(test_file_path: &Path) -> bool { | "refund50percentCap.json" | "refund600.json" + // Reason: these tests are assuming EIP-7610 is implemented in Cancun. + // The EIP is slated for inclusion in the upcoming Pectra upgrade. + | "RevertInCreateInInit_Paris.json" + | "dynamicAccountOverwriteEmpty_Paris.json" + | "RevertInCreateInInitCreate2Paris.json" + | "create2collisionStorageParis.json" + | "InitCollisionParis.json" + // SKIPPED BECAUSE TESTS ARE EXPECTED TO BE RUNNED VIA AN EXTERNAL CLIENT // Reason: Invalid transaction. The gas limit is set to less than 21000. @@ -453,9 +493,7 @@ pub fn check_skip_parsing(test_file_path: &Path) -> bool { // byte array containing between (0; 32] bytes | "ZeroValue_SUICIDE_ToOneStorageKey.json" | "ValueOverflow.json" - - // Reason: invalid length 0, expected a (both 0x-prefixed or not) hex string or - // byte array containing between (0; 32] bytes + | "ValueOverflowParis.json" | "eqNonConst.json" | "mulmodNonConst.json" | "addmodNonConst.json" @@ -571,7 +609,9 @@ pub fn main() { write_out!(output_file, "WARNING: the specified path [{}] can not be found, data(s) \ that should be skipped will not be and the outcome of the \ evaluation could be erroneous.", skip_data_path.display()); - SkipData { datas: vec![] } + SkipData { + datas: HashMap::new(), + } } }; diff --git a/etherlink/kernel_evm/evm_evaluation/src/models/deserializer.rs b/etherlink/kernel_evm/evm_evaluation/src/models/deserializer.rs index 31ef7319fd0fda05d553d30e9f3e8f8ded0dab8b..95e2be3017588e2ee4d3902b7fee3a5d6223dc21 100644 --- a/etherlink/kernel_evm/evm_evaluation/src/models/deserializer.rs +++ b/etherlink/kernel_evm/evm_evaluation/src/models/deserializer.rs @@ -109,27 +109,6 @@ where Ok(Some(H160::from_str(&string).map_err(D::Error::custom)?)) } -pub fn deserialize_vec_str_as_u8_vectors<'de, D>( - deserializer: D, -) -> Result>, D::Error> -where - D: de::Deserializer<'de>, -{ - let strings: Vec = Vec::deserialize(deserializer)?; - - let mut vecs: Vec> = vec![]; - - for string in strings.iter() { - vecs.push( - hex::decode(string.strip_prefix("0x").unwrap_or(string)) - .map_err(D::Error::custom) - .unwrap(), - ) - } - - Ok(vecs) -} - pub fn deserialize_str_as_bytes<'de, D>(deserializer: D) -> Result where D: de::Deserializer<'de>, diff --git a/etherlink/kernel_evm/evm_evaluation/src/models/mod.rs b/etherlink/kernel_evm/evm_evaluation/src/models/mod.rs index 4c218f7bab663e2ea36788163ee9f3e5255610a2..e19df831d032efcb185bd48d67aa51a887ccf85d 100644 --- a/etherlink/kernel_evm/evm_evaluation/src/models/mod.rs +++ b/etherlink/kernel_evm/evm_evaluation/src/models/mod.rs @@ -244,10 +244,13 @@ pub struct Env { pub tx: TxEnv, } +#[derive(Clone, Debug, PartialEq, Eq, Deserialize)] +#[serde(transparent)] +pub struct HexBytes(#[serde(with = "hex::serde")] pub Vec); + #[derive(Clone, Debug, PartialEq, Eq, Deserialize)] pub struct SkipData { - #[serde(deserialize_with = "deserialize_vec_str_as_u8_vectors")] - pub datas: Vec>, + pub datas: HashMap>, } #[cfg(test)] diff --git a/etherlink/kernel_evm/evm_evaluation/src/runner.rs b/etherlink/kernel_evm/evm_evaluation/src/runner.rs index 4b3a9e95535629b500c48462498b61f08ba9b7eb..364beb9a1978ce6acc1854ad841f915b5fd46c2d 100644 --- a/etherlink/kernel_evm/evm_evaluation/src/runner.rs +++ b/etherlink/kernel_evm/evm_evaluation/src/runner.rs @@ -253,10 +253,12 @@ fn execute_transaction( ) } -fn data_to_skip(data: &[u8], skip_data: &SkipData) -> bool { - for skip_data in skip_data.datas.iter() { - if data == skip_data { - return true; +fn data_to_skip(name: &str, data: &[u8], skip_data: &SkipData) -> bool { + for (skip_name, skip_datas) in skip_data.datas.iter() { + for skip_data in skip_datas { + if data == skip_data.0 && name == skip_name { + return true; + } } } false @@ -339,6 +341,7 @@ pub fn run_test( for (spec_name, tests) in &unit.post { let config = match spec_name { SpecName::Shanghai => Config::shanghai(), + SpecName::Cancun => Config::cancun(), // TODO: enable future configs when parallelization is enabled. // Other tests are ignored _ => continue, @@ -380,7 +383,7 @@ pub fn run_test( .unwrap() .clone(); - if data_to_skip(&data, skip_data) { + if data_to_skip(&name, &data, skip_data) { continue; } diff --git a/etherlink/kernel_evm/evm_execution/src/fa_bridge/mod.rs b/etherlink/kernel_evm/evm_execution/src/fa_bridge/mod.rs index 2c31dc8963180a8cba6459aa27399a19eaa49e92..254e4811ab97c43b57230c0e511d053af88768a2 100644 --- a/etherlink/kernel_evm/evm_execution/src/fa_bridge/mod.rs +++ b/etherlink/kernel_evm/evm_execution/src/fa_bridge/mod.rs @@ -51,6 +51,7 @@ use crate::{ precompiles::{PrecompileBTreeMap, PrecompileOutcome, SYSTEM_ACCOUNT_ADDRESS}, trace::TracerInput, transaction::TransactionContext, + transaction_layer_data::CallContext, withdrawal_counter::WithdrawalCounter, EthereumError, }; @@ -152,7 +153,13 @@ pub fn execute_fa_deposit<'a, Host: Runtime>( tracer_input, ); - handler.begin_initial_transaction(false, Some(gas_limit))?; + handler.begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(gas_limit), + )?; // It's ok if internal proxy call fails, we will update the ticket table anyways. let ticket_owner = if let Some(proxy) = deposit.proxy { @@ -259,7 +266,13 @@ pub fn execute_fa_withdrawal( }); } - handler.begin_inter_transaction(false, gas_limit)?; + handler.begin_inter_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + gas_limit, + )?; // Execute the withdrawal in the transaction layer and clean it based // on the result. diff --git a/etherlink/kernel_evm/evm_execution/src/fa_bridge/test_utils.rs b/etherlink/kernel_evm/evm_execution/src/fa_bridge/test_utils.rs index 38d874928511b71b9c7b4e806400859dd11caf22..da9bfb85f6b3e230e380e465f1be420b7470d530 100644 --- a/etherlink/kernel_evm/evm_execution/src/fa_bridge/test_utils.rs +++ b/etherlink/kernel_evm/evm_execution/src/fa_bridge/test_utils.rs @@ -31,6 +31,7 @@ use crate::{ self, precompile_set, FA_BRIDGE_PRECOMPILE_ADDRESS, SYSTEM_ACCOUNT_ADDRESS, }, run_transaction, + transaction_layer_data::CallContext, utilities::keccak256_hash, withdrawal_counter::WITHDRAWAL_COUNTER_PATH, }; @@ -61,6 +62,14 @@ const MOCK_WRAPPER_BYTECODE: &[u8] = const REENTRANCY_TESTER_BYTECODE: &[u8] = include_bytes!("../../tests/contracts/artifacts/ReentrancyTester.bytecode"); +pub const CONFIG: Config = Config { + // The current implementation doesn't support Cancun call + // stack limit of 256. We need to set a lower limit until we + // have switched to a head-based recursive calls. + call_stack_limit: 256, + ..Config::cancun() +}; + /// Create a smart contract in the storage with the mocked token code pub fn deploy_mock_wrapper( host: &mut MockKernelHost, @@ -87,7 +96,7 @@ pub fn deploy_mock_wrapper( &block, evm_account_storage, &precompiles, - Config::shanghai(), + CONFIG, None, *caller, [code, calldata.abi_encode()].concat(), @@ -134,7 +143,7 @@ pub fn deploy_reentrancy_tester( &block, evm_account_storage, &precompiles, - Config::shanghai(), + CONFIG, None, *caller, [code, calldata.abi_encode()].concat(), @@ -168,7 +177,7 @@ pub fn run_fa_deposit( &block, evm_account_storage, &precompiles, - Config::shanghai(), + CONFIG, *caller, deposit, 100_000_000_000, @@ -392,7 +401,7 @@ pub fn fa_bridge_precompile_call_withdraw( ) -> ExecutionOutcome { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); - let config = Config::shanghai(); + let config = CONFIG; let mut handler = EvmHandler::new( host, @@ -408,7 +417,13 @@ pub fn fa_bridge_precompile_call_withdraw( ); handler - .begin_initial_transaction(false, Some(30_000_000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(30_000_000), + ) .unwrap(); let res = execute_fa_withdrawal(&mut handler, caller, withdrawal); diff --git a/etherlink/kernel_evm/evm_execution/src/handler.rs b/etherlink/kernel_evm/evm_execution/src/handler.rs index 11c944fb54a46515320779ab844d61d223fe89fe..e52ca3690d7e69954163dcad0a00d2110b00b4b8 100644 --- a/etherlink/kernel_evm/evm_execution/src/handler.rs +++ b/etherlink/kernel_evm/evm_execution/src/handler.rs @@ -24,7 +24,7 @@ use crate::trace::{ StructLoggerInput, TracerInput, }; use crate::transaction::TransactionContext; -use crate::transaction_layer_data::TransactionLayerData; +use crate::transaction_layer_data::{CallContext, TransactionLayerData}; use crate::utilities::create_address_legacy; use crate::EthereumError; use crate::PrecompileSet; @@ -41,7 +41,7 @@ use evm::{ use primitive_types::{H160, H256, U256}; use sha3::{Digest, Keccak256}; use std::cmp::min; -use std::collections::HashMap; +use std::collections::{BTreeSet, HashMap}; use std::fmt::Debug; use tezos_data_encoding::enc::{BinResult, BinWriter}; use tezos_ethereum::block::BlockConstants; @@ -361,6 +361,10 @@ impl CacheStorageValue { /// address and an index (StorageKey) to a value (CacheStorageValue). pub type LayerCache = HashMap; +/// A transient layer associates at each address and index (StorageKey) +/// its value (H256). +pub type TransientLayer = HashMap; + /// The storage cache is associating at each layer (usize) its /// own cache (LayerCache). For each slot that is modified or /// read during a call it will be added to the cache in its own @@ -372,6 +376,13 @@ pub type LayerCache = HashMap; // 300_000 × 32B = 9_600_000B = 9.6MB pub type StorageCache = HashMap; +/// The transient storage is a temporary data storage area within the +/// EVM. It is associating at each layer (usize) its own storage map. +/// For each slot that is modified it will be added to the associated +/// layer and map. If the value did not exist, by default we return the +/// default value as specified by EIP-1153. +pub type TransientStorage = HashMap; + /// The implementation of the SputnikVM [Handler] trait pub struct EvmHandler<'a, Host: Runtime> { /// The host @@ -409,6 +420,12 @@ pub struct EvmHandler<'a, Host: Runtime> { /// access storage slots before any transaction happens. /// See: `fn original_storage`. original_storage_cache: LayerCache, + /// Transient storage as specified by EIP-1153. + pub transient_storage: TransientStorage, + /// All the freshly created contracts. + /// It will help identify created contracts within the same transaction + /// accross all the execution layers to help comply with EIP-6780. + pub created_contracts: BTreeSet, /// Reentrancy guard prevents circular calls to impure precompiles reentrancy_guard: ReentrancyGuard, } @@ -443,6 +460,8 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { tracer, storage_cache: HashMap::with_capacity(10), original_storage_cache: HashMap::with_capacity(10), + transient_storage: HashMap::with_capacity(10), + created_contracts: BTreeSet::new(), reentrancy_guard: ReentrancyGuard::new(vec![ WITHDRAWAL_ADDRESS, FA_BRIDGE_PRECOMPILE_ADDRESS, @@ -693,10 +712,16 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { fn is_static(&self) -> bool { self.transaction_data .last() - .map(|data| data.is_static) + .map(|data| data.call_context.is_static) .unwrap_or(false) } + /// Returns true if [address] was created during the on-going transaction accross + /// all the layers. + fn was_created(&self, address: &H160) -> bool { + self.created_contracts.contains(address) + } + /// Record the base fee part of the transaction cost. We need the SputnikVM /// error code in case this goes wrong, so that's what we return. fn record_base_gas_cost( @@ -1368,7 +1393,13 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { is_static: bool, ) -> Result { self.increment_nonce(caller)?; - self.begin_initial_transaction(is_static, gas_limit)?; + self.begin_initial_transaction( + CallContext { + is_static, + is_creation: false, + }, + gas_limit, + )?; if self.mark_address_as_hot(caller).is_err() { return Err(EthereumError::InconsistentState(Cow::from( @@ -1416,7 +1447,13 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { let address = self.create_address(default_create_scheme)?; self.increment_nonce(caller)?; - self.begin_initial_transaction(false, gas_limit)?; + self.begin_initial_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + gas_limit, + )?; if self.mark_address_as_hot(caller).is_err() { return Err(EthereumError::InconsistentState(Cow::from( @@ -1610,7 +1647,7 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { /// this. pub(crate) fn begin_initial_transaction( &mut self, - is_static: bool, + call_context: CallContext, gas_limit: Option, ) -> Result<(), EthereumError> { let number_of_tx_layer = self.evm_account_storage.stack_depth(); @@ -1632,7 +1669,8 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { } self.transaction_data.push(TransactionLayerData::new( - self.is_static() || is_static, + self.is_static() || call_context.is_static, + call_context.is_creation, gas_limit, self.config, AccessRecord::default(), @@ -1697,6 +1735,10 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { .commit_transaction(self.host) .map_err(EthereumError::from)?; + if let ExecutionResult::ContractDeployed(new_address, _) = result { + self.created_contracts.insert(new_address); + } + Ok(ExecutionOutcome { gas_used, logs: last_layer.logs, @@ -1753,6 +1795,7 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { let _ = self.transaction_data.pop(); self.storage_cache.clear(); + self.transient_storage.clear(); self.original_storage_cache.clear(); Ok(ExecutionOutcome { @@ -1880,7 +1923,7 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { /// Begin an intermediate transaction pub fn begin_inter_transaction( &mut self, - is_static: bool, + call_context: CallContext, gas_limit: Option, ) -> Result<(), EthereumError> { let number_of_tx_layer = self.evm_account_storage.stack_depth(); @@ -1903,7 +1946,8 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { let accessed_storage_keys = current_top.accessed_storage_keys.clone(); self.transaction_data.push(TransactionLayerData::new( - self.is_static() || is_static, + self.is_static() || call_context.is_static, + call_context.is_creation, gas_limit, self.config, accessed_storage_keys, @@ -1937,6 +1981,7 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { let gas_refunded = self.gas_refunded(); commit_storage_cache(self, number_of_tx_layer); + commit_transient_storage(self, number_of_tx_layer); self.evm_account_storage .commit_transaction(self.host) @@ -2008,6 +2053,7 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { } self.storage_cache.remove(&number_of_tx_layer); + self.transient_storage.remove(&number_of_tx_layer); self.evm_account_storage .rollback_transaction(self.host) @@ -2044,7 +2090,7 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { execution_result: Result, ) -> Capture { match execution_result { - Ok((ref exit_reason, _, _)) => match exit_reason { + Ok((ref exit_reason, new_address, _)) => match exit_reason { ExitReason::Succeed(_) => { log!( self.host, @@ -2053,6 +2099,10 @@ impl<'a, Host: Runtime> EvmHandler<'a, Host> { exit_reason ); + if let Some(new_address) = new_address { + self.created_contracts.insert(new_address); + } + if let Err(err) = self.commit_inter_transaction() { log!( self.host, @@ -2264,6 +2314,20 @@ fn commit_storage_cache( } } +fn commit_transient_storage( + handler: &mut EvmHandler<'_, Host>, + current_layer: usize, +) { + let commit_layer = current_layer - 1; + if let Some(t_storage) = handler.transient_storage.remove(¤t_layer) { + if let Some(prev_t_storage) = handler.transient_storage.get_mut(&commit_layer) { + prev_t_storage.extend(t_storage); + } else { + handler.transient_storage.insert(commit_layer, t_storage); + } + } +} + fn cached_storage_access( handler: &mut EvmHandler<'_, Host>, address: H160, @@ -2295,6 +2359,77 @@ fn cached_storage_access( } } +/// SELFDESTRUCT implementation prior to EIP-6780. +/// See https://eips.ethereum.org/EIPS/eip-6780. +fn mark_delete_legacy( + handler: &mut EvmHandler<'_, Host>, + address: H160, + target: H160, +) -> Result<(), ExitError> { + let new_deletion = match handler.transaction_data.last_mut() { + Some(top_layer) => Ok(top_layer.deleted_contracts.insert(address)), + None => Err(ExitError::Other(Cow::from( + "No transaction data for delete", + ))), + }?; + if new_deletion && address == target { + handler.reset_balance(address).map_err(|_| { + ExitError::Other(Cow::from("Could not reset balance when deleting contract")) + }) + } else if new_deletion { + let balance = handler.balance(address); + + handler + .execute_transfer(address, target, balance) + .map_err(|_| { + ExitError::Other(Cow::from( + "Could not execute transfer on contract delete", + )) + })?; + Ok(()) + } else { + log!(handler.host, Debug, "Contract already marked to delete"); + Ok(()) + } +} + +/// SELFDESTRUCT implementation after EIP-6780. +/// See https://eips.ethereum.org/EIPS/eip-6780. +fn mark_delete_eip6780( + handler: &mut EvmHandler<'_, Host>, + address: H160, + target: H160, +) -> Result<(), ExitError> { + if address != target { + let balance = handler.balance(address); + + handler + .execute_transfer(address, target, balance) + .map_err(|_| { + ExitError::Other(Cow::from( + "Could not execute transfer on contract delete", + )) + })?; + } + + match handler.transaction_data.last_mut() { + Some(top_layer) => { + if top_layer.call_context.is_creation { + top_layer.deleted_contracts.insert(address); + handler.reset_balance(address).map_err(|_| { + ExitError::Other(Cow::from( + "Could not reset balance when deleting contract", + )) + })?; + } + Ok(()) + } + None => Err(ExitError::Other(Cow::from( + "No transaction data for delete", + ))), + } +} + #[allow(unused_variables)] impl Handler for EvmHandler<'_, Host> { type CreateInterrupt = Infallible; @@ -2345,6 +2480,18 @@ impl Handler for EvmHandler<'_, Host> { cached_storage_access(self, address, index, layer) } + fn transient_storage(&self, address: H160, index: H256) -> H256 { + let layer = self.evm_account_storage.stack_depth(); + for layer in (0..=layer).rev() { + if let Some(t_storage) = self.transient_storage.get(&layer) { + if let Some(value) = t_storage.get(&StorageKey { address, index }) { + return *value; + } + } + } + H256::zero() + } + fn original_storage(&mut self, address: H160, index: H256) -> H256 { let key = StorageKey { address, index }; if let Some(value) = self.original_storage_cache.get(&key) { @@ -2417,6 +2564,18 @@ impl Handler for EvmHandler<'_, Host> { self.block.base_fee_per_gas() } + fn blob_hash(&self, _index: H256) -> H256 { + // Etherlink doesn't support blob as defined by + // EIP-4844 (Proto-Danksharding). + // As such, the following value will always return + // zero. + H256::zero() + } + + fn block_blob_base_fee(&self) -> U256 { + self.block.blob_base_fee() + } + fn block_randomness(&self) -> Option { self.block.prevrandao // Always None } @@ -2484,6 +2643,29 @@ impl Handler for EvmHandler<'_, Host> { Ok(()) } + fn set_transient_storage( + &mut self, + address: H160, + index: H256, + value: H256, + ) -> Result<(), ExitError> { + if self.is_static() { + return Err(ExitError::Other(Cow::from( + "TSTORE cannot be executed inside a static call", + ))); + } + + let layer = self.evm_account_storage.stack_depth(); + if let Some(t_storage) = self.transient_storage.get_mut(&layer) { + t_storage.insert(StorageKey { address, index }, value); + } else { + let mut t_storage = HashMap::new(); + t_storage.insert(StorageKey { address, index }, value); + self.transient_storage.insert(layer, t_storage); + } + Ok(()) + } + fn log( &mut self, address: H160, @@ -2498,31 +2680,13 @@ impl Handler for EvmHandler<'_, Host> { } fn mark_delete(&mut self, address: H160, target: H160) -> Result<(), ExitError> { - let new_deletion = match self.transaction_data.last_mut() { - Some(top_layer) => Ok(top_layer.deleted_contracts.insert(address)), - None => Err(ExitError::Other(Cow::from( - "No transaction data for delete", - ))), - }?; - if new_deletion && address == target { - self.reset_balance(address).map_err(|_| { - ExitError::Other(Cow::from( - "Could not reset balance when deleting contract", - )) - }) - } else if new_deletion { - let balance = self.balance(address); - - self.execute_transfer(address, target, balance) - .map_err(|_| { - ExitError::Other(Cow::from( - "Could not execute transfer on contract delete", - )) - })?; - Ok(()) + // To comply with EIP-6780, if the opcode is considered not deprecated or if + // the address where the SELFDESTRUCT is called was just created, we keep + // the legacy behavior, otherwise we use the "deprecated" behavior. + if !self.config.selfdestruct_deprecated || self.was_created(&address) { + mark_delete_legacy(self, address, target) } else { - log!(self.host, Debug, "Contract already marked to delete"); - Ok(()) + mark_delete_eip6780(self, address, target) } } @@ -2630,7 +2794,13 @@ impl Handler for EvmHandler<'_, Host> { )); } - match self.begin_inter_transaction(false, gas_limit) { + match self.begin_inter_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + gas_limit, + ) { Ok(()) => { let gas_before = self.gas_used(); let result = self.execute_create( @@ -2775,7 +2945,10 @@ impl Handler for EvmHandler<'_, Host> { } if let Err(err) = self.begin_inter_transaction( - call_scheme == CallScheme::StaticCall, + CallContext { + is_static: call_scheme == CallScheme::StaticCall, + is_creation: false, + }, gas_limit, ) { return Capture::Exit((ethereum_error_to_exit_reason(&err), vec![])); @@ -3004,13 +3177,21 @@ mod test { ) } + const CONFIG: Config = Config { + // The current implementation doesn't support Cancun call + // stack limit of 256. We need to set a lower limit until we + // have switched to a head-based recursive calls. + call_stack_limit: 256, + ..Config::cancun() + }; + #[test] fn legacy_create_to_correct_address() { let mut mock_runtime = MockKernelHost::default(); let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let gas_price = U256::from(21000); @@ -3053,7 +3234,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller: H160 = H160::from_str("9bbfed6889322e016e0a02ee459d306fc19545d8").unwrap(); @@ -3095,7 +3276,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let gas_price = U256::from(21000); @@ -3141,7 +3322,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(28349_u64); // We use an origin distinct from caller for testing purposes @@ -3180,7 +3361,15 @@ mod test { set_code(&mut handler, &address, code); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3206,7 +3395,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(28349_u64); let gas_price = U256::from(21000); @@ -3274,7 +3463,15 @@ mod test { set_code(&mut handler, &address, code); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3300,7 +3497,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(2340); let gas_price = U256::from(21000); @@ -3369,7 +3566,15 @@ mod test { set_code(&mut handler, &address, code); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input.to_vec(), transaction_context); @@ -3395,7 +3600,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(8213); let gas_price = U256::from(21000); @@ -3464,7 +3669,15 @@ mod test { set_code(&mut handler, &address, code); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input.to_vec(), transaction_context); @@ -3488,7 +3701,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(444); let gas_price = U256::from(21000); @@ -3529,7 +3742,15 @@ mod test { set_code(&mut handler, &address, code); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3560,7 +3781,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(117); let gas_price = U256::from(21000); @@ -3584,7 +3805,15 @@ mod test { let expected_address = handler.create_address(create_scheme).unwrap_or_default(); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + None, + ) + .unwrap(); let result = handler.execute_create(caller, value, init_code, expected_address); @@ -3617,7 +3846,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(117); let gas_price = U256::from(21000); @@ -3653,7 +3882,15 @@ mod test { ]; let contract_address = handler.create_address(create_scheme).unwrap_or_default(); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + None, + ) + .unwrap(); let result = handler.execute_create(caller, value, initial_code, contract_address); @@ -3683,7 +3920,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(118); let gas_price = U256::from(21000); @@ -3721,7 +3958,15 @@ mod test { set_code(&mut handler, &address, code); set_balance(&mut handler, &caller, U256::from(101_u32)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3746,7 +3991,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -3783,7 +4028,15 @@ mod test { set_code(&mut handler, &address, code); set_balance(&mut handler, &caller, U256::from(99_u32)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3808,7 +4061,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -3854,7 +4107,15 @@ mod test { set_code(&mut handler, &address, code); set_balance(&mut handler, &caller, U256::from(99_u32)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3879,7 +4140,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -3950,7 +4211,13 @@ mod test { set_balance(&mut handler, &caller, U256::from(99_u32)); handler - .begin_initial_transaction(false, Some(30000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(30000), + ) .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -3968,7 +4235,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4003,7 +4270,15 @@ mod test { set_code(&mut handler, &address, code); set_balance(&mut handler, &caller, U256::from(99_u32)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -4020,7 +4295,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4068,7 +4343,15 @@ mod test { set_code(&mut handler, &address, code); set_balance(&mut handler, &caller, U256::from(99_u32)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address, transfer, input, transaction_context); @@ -4089,7 +4372,7 @@ mod test { let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller_address: [u8; 20] = hex::decode("a94f5374fce5edbc8e2a8697c15331677e6ebf0b") @@ -4131,7 +4414,15 @@ mod test { set_code(&mut handler, &target_address, code); set_balance(&mut handler, &caller, U256::from(1000000000000000000u64)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(target_address, None, input, transaction_context); @@ -4157,7 +4448,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_str("a94f5374fce5edbc8e2a8697c15331677e6ebf0b").unwrap(); @@ -4182,7 +4473,13 @@ mod test { let contract_address = handler.create_address(scheme).unwrap_or_default(); handler - .begin_initial_transaction(false, Some(10000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + Some(10000), + ) .unwrap(); let result = @@ -4200,7 +4497,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4259,7 +4556,15 @@ mod test { set_balance(&mut handler, &caller, U256::from(1000_u32)); set_balance(&mut handler, &address_1, U256::from(1000_u32)); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call(address_1, transfer, input, transaction_context); @@ -4276,7 +4581,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4305,7 +4610,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_str("a94f5374fce5edbc8e2a8697c15331677e6ebf0b").unwrap(); let withdrawal_contract = @@ -4349,7 +4654,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4414,7 +4719,13 @@ mod test { set_balance(&mut handler, &address_1, U256::from(1000_u32)); handler - .begin_initial_transaction(false, Some(1000000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(1000000), + ) .unwrap(); let result = @@ -4432,7 +4743,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4510,7 +4821,13 @@ mod test { set_balance(&mut handler, &address_1, U256::from(1000_u32)); handler - .begin_initial_transaction(false, Some(1000000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(1000000), + ) .unwrap(); let result = @@ -4532,6 +4849,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); + // This test is specifically testing a Shanghai behaviour: let config = Config::shanghai(); let caller = H160::from_str("095e7baea6a6c7c4c2dfeb977efac326af552d87").unwrap(); @@ -4598,7 +4916,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let gas_price = U256::from(21000); @@ -4651,7 +4969,13 @@ mod test { let transfer: Option = None; handler - .begin_initial_transaction(false, Some(1000000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(1000000), + ) .unwrap(); let _ = handler.execute_call(contrac_addr, transfer, input, transaction_context); @@ -4672,7 +4996,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let mut handler = EvmHandler::new( @@ -4689,11 +5013,23 @@ mod test { ); handler - .begin_initial_transaction(false, Some(150000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(150000), + ) .unwrap(); handler - .begin_inter_transaction(false, Some(150000)) + .begin_inter_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + Some(150000), + ) .unwrap(); let ecmul = H160::from_low_u64_be(7u64); @@ -4731,7 +5067,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4813,7 +5149,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let gas_price = U256::from(21000); @@ -4834,7 +5170,13 @@ mod test { let initial_code = [1; 49153]; // MAX_INIT_CODE_SIZE + 1 handler - .begin_initial_transaction(false, Some(150000)) + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + Some(150000), + ) .unwrap(); let capture = handler.create( @@ -4865,7 +5207,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_str("a94f5374fce5edbc8e2a8697c15331677e6ebf0b").unwrap(); @@ -4882,7 +5224,13 @@ mod test { None, ); - let _ = handler.begin_initial_transaction(false, None); + let _ = handler.begin_initial_transaction( + CallContext { + is_static: false, + is_creation: true, + }, + None, + ); set_balance(&mut handler, &caller, U256::from(1000000000)); set_nonce(&mut handler, &caller, u64::MAX); @@ -4909,7 +5257,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(523_u64); let mut handler = EvmHandler::new( @@ -4987,6 +5335,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); + // This test is specifically testing a Shanghai behaviour: let config = Config::shanghai(); let caller = H160::from_low_u64_be(111_u64); @@ -5059,7 +5408,7 @@ mod test { let block = dummy_first_block(); let precompiles = precompiles::precompile_set::(false); let mut evm_account_storage = init_account_storage().unwrap(); - let config = Config::shanghai(); + let config = CONFIG; let caller = H160::from_low_u64_be(111_u64); let gas_price = U256::from(21000); diff --git a/etherlink/kernel_evm/evm_execution/src/lib.rs b/etherlink/kernel_evm/evm_execution/src/lib.rs index c72670a1d812d8c9c88b99779303e139cee4f156..bd8cdbf2023dd62f01f48bb4d1fefe842eb82f21 100755 --- a/etherlink/kernel_evm/evm_execution/src/lib.rs +++ b/etherlink/kernel_evm/evm_execution/src/lib.rs @@ -469,11 +469,11 @@ mod test { "60fe47b1000000000000000000000000000000000000000000000000000000000000002a"; const CONFIG: Config = Config { - // The current implementation doesn't support Shanghai call + // The current implementation doesn't support Cancun call // stack limit of 256. We need to set a lower limit until we // have switched to a head-based recursive calls. call_stack_limit: 256, - ..Config::shanghai() + ..Config::cancun() }; // The compiled initialization code for the Ethereum demo contract given @@ -609,7 +609,7 @@ mod test { let caller = H160::from_low_u64_be(985493); let call_data: Vec = vec![]; let transaction_value = U256::from(100_u32); - let config = Config::shanghai(); + let config = CONFIG; let gas_price = U256::from(1); set_balance( @@ -674,7 +674,7 @@ mod test { let caller = H160::from_low_u64_be(1234); let call_data: Vec = vec![]; let transaction_value = U256::from(100_u32); - let config = Config::shanghai(); + let config = CONFIG; let gas_price = U256::from(1); set_balance( @@ -2144,7 +2144,8 @@ mod test { &block, &mut evm_account_storage, &precompiles, - CONFIG, + // This test is specifically testing a Shanghai behaviour: + Config::shanghai(), Some(target), caller, vec![], diff --git a/etherlink/kernel_evm/evm_execution/src/precompiles/fa_bridge.rs b/etherlink/kernel_evm/evm_execution/src/precompiles/fa_bridge.rs index 91f613ff816699668a501ad13524e90340ee6148..04bd010a758d97e7df5e6f9c460e922f5ff8ebf3 100644 --- a/etherlink/kernel_evm/evm_execution/src/precompiles/fa_bridge.rs +++ b/etherlink/kernel_evm/evm_execution/src/precompiles/fa_bridge.rs @@ -158,7 +158,7 @@ mod tests { use std::{borrow::Cow, str::FromStr}; use alloy_sol_types::SolCall; - use evm::{Config, ExitError}; + use evm::ExitError; use primitive_types::{H160, U256}; use tezos_data_encoding::enc::BinWriter; use tezos_evm_runtime::runtime::MockKernelHost; @@ -170,12 +170,13 @@ mod tests { test_utils::{ convert_h160, convert_u256, deploy_reentrancy_tester, dummy_fa_withdrawal, dummy_first_block, dummy_ticket, kernel_wrapper, - set_balance, ticket_balance_add, ticket_id, + set_balance, ticket_balance_add, ticket_id, CONFIG, }, }, handler::{EvmHandler, ExecutionOutcome, ExecutionResult}, precompiles::{self, FA_BRIDGE_PRECOMPILE_ADDRESS}, transaction::TransactionContext, + transaction_layer_data::CallContext, utilities::{bigint_to_u256, keccak256_hash}, }; @@ -191,7 +192,7 @@ mod tests { disable_reentrancy_guard: bool, ) -> ExecutionOutcome { let block = dummy_first_block(); - let config = Config::shanghai(); + let config = CONFIG; let callee = FA_BRIDGE_PRECOMPILE_ADDRESS; let precompiles = precompiles::precompile_set::(true); @@ -320,7 +321,7 @@ mod tests { let caller = H160::from_low_u64_be(1); let callee = H160::from_low_u64_be(2); let block = dummy_first_block(); - let config = Config::shanghai(); + let config = CONFIG; let precompiles = precompiles::precompile_set::(true); @@ -337,7 +338,15 @@ mod tests { None, ); - handler.begin_initial_transaction(false, None).unwrap(); + handler + .begin_initial_transaction( + CallContext { + is_static: false, + is_creation: false, + }, + None, + ) + .unwrap(); let result = handler.execute_call( FA_BRIDGE_PRECOMPILE_ADDRESS, diff --git a/etherlink/kernel_evm/evm_execution/src/precompiles/mod.rs b/etherlink/kernel_evm/evm_execution/src/precompiles/mod.rs index f11eeee487fe9648e2cc221d6fcd56e2dad24bd6..83c73fd744c99f8788f3058e9870149410d6669c 100644 --- a/etherlink/kernel_evm/evm_execution/src/precompiles/mod.rs +++ b/etherlink/kernel_evm/evm_execution/src/precompiles/mod.rs @@ -29,6 +29,7 @@ use crate::EthereumError; use alloc::collections::btree_map::BTreeMap; use blake2::blake2f_precompile; use ecdsa::ecrecover_precompile; +use evm::executor::stack::PrecompileFailure; use evm::{Context, ExitReason, Handler, Transfer}; use fa_bridge::fa_bridge_precompile; use hash::{ripemd160_precompile, sha256_precompile}; @@ -162,6 +163,21 @@ pub const WITHDRAWAL_ADDRESS: H160 = H160([ 0xff, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, ]); +// This precompile is part of EIP-4844 which we don't support +// on Etherlink, as they are related to blobs. +// See: https://eips.ethereum.org/EIPS/eip-4844#point-evaluation-precompile +fn kzg_point_evaluation( + _handler: &mut EvmHandler, + _input: &[u8], + _context: &Context, + _is_static: bool, + _transfer: Option, +) -> Result { + Err(EthereumError::PrecompileFailed(PrecompileFailure::Fatal { + exit_status: evm::ExitFatal::NotSupported, + })) +} + pub fn evm_precompile_set() -> PrecompileBTreeMap { BTreeMap::from([ ( @@ -200,6 +216,10 @@ pub fn evm_precompile_set() -> PrecompileBTreeMap { H160::from_low_u64_be(9u64), blake2f_precompile as PrecompileFn, ), + ( + H160::from_low_u64_be(10u64), + kzg_point_evaluation as PrecompileFn, + ), ]) } @@ -282,11 +302,11 @@ mod test_helpers { use crate::account_storage::account_path; use crate::account_storage::init_account_storage as init_evm_account_storage; use crate::account_storage::EthereumAccountStorage; + use crate::fa_bridge::test_utils::CONFIG; use crate::handler::EvmHandler; use crate::handler::ExecutionOutcome; use crate::EthereumError; use crate::NATIVE_TOKEN_TICKETER_PATH; - use evm::Config; use evm::Transfer; use host::runtime::Runtime; use primitive_types::{H160, U256}; @@ -342,7 +362,7 @@ mod test_helpers { ); let mut evm_account_storage = init_evm_account_storage().unwrap(); let precompiles = precompile_set::(false); - let config = Config::shanghai(); + let config = CONFIG; let gas_price = U256::from(21000); set_ticketer(&mut mock_runtime, DUMMY_TICKETER); diff --git a/etherlink/kernel_evm/evm_execution/src/transaction_layer_data.rs b/etherlink/kernel_evm/evm_execution/src/transaction_layer_data.rs index 956892ab30045caeef21446a458b81a985522af4..4a85dfdf36602f8a3bcd26af013f0d89fffb6b19 100644 --- a/etherlink/kernel_evm/evm_execution/src/transaction_layer_data.rs +++ b/etherlink/kernel_evm/evm_execution/src/transaction_layer_data.rs @@ -1,5 +1,6 @@ // SPDX-FileCopyrightText: 2022-2023 TriliTech // SPDX-FileCopyrightText: 2023-2024 Nomadic Labs +// SPDX-FileCopyrightText: 2025 Functori // // SPDX-License-Identifier: MIT @@ -11,15 +12,23 @@ use evm::Config; use primitive_types::H160; use std::collections::BTreeSet; +pub struct CallContext { + /// Whether the current transaction is static or not, ie, if the + /// transaction is allowed to update durable storage. + pub is_static: bool, + /// Whether the current transaction is a contract creation or not. + pub is_creation: bool, +} + /// Data related to the current transaction layer pub struct TransactionLayerData<'config> { /// Gasometer for the current transaction layer. If this value is /// `None`, then the current transaction has no gas limit and no /// gas accounting. pub gasometer: Option>, - /// Whether the current transaction is static or not, ie, if the - /// transaction is allowed to update durable storage. - pub is_static: bool, + /// Call context. + /// See `CallContext` for more documentation. + pub call_context: CallContext, /// The log records gathered in this layer of transactions and any /// committed sub layers. pub logs: Vec, @@ -42,13 +51,17 @@ impl<'config> TransactionLayerData<'config> { /// will be no gasometer. pub fn new( is_static: bool, + is_creation: bool, gas_limit: Option, config: &'config Config, accessed_storage_keys: AccessRecord, ) -> Self { TransactionLayerData { gasometer: gas_limit.map(|gl| Gasometer::new(gl, config)), - is_static, + call_context: CallContext { + is_static, + is_creation, + }, logs: vec![], deleted_contracts: BTreeSet::new(), withdrawals: vec![], diff --git a/etherlink/kernel_evm/kernel/src/lib.rs b/etherlink/kernel_evm/kernel/src/lib.rs index ef13486007cdf4dd8bc7838411a3e55b0d1a8501..9c66c77ef9d6cc99fbc6b0b93dba4c9ca31bdb2c 100644 --- a/etherlink/kernel_evm/kernel/src/lib.rs +++ b/etherlink/kernel_evm/kernel/src/lib.rs @@ -74,7 +74,7 @@ pub const CHAIN_ID: u32 = 1337; /// The configuration for the EVM execution. const CONFIG: Config = Config { - // The current implementation doesn't support Shanghai call stack limit of 256. + // The current implementation doesn't support Cancun call stack limit of 256. // We need to set a lower limit until we have switched to a head-based // recursive calls. // @@ -82,7 +82,7 @@ const CONFIG: Config = Config { // to be reactivated. As well as tests `call_too_deep_not_revert` and // `multiple_call_all_the_way_to_1024` in the evm execution crate. call_stack_limit: 256, - ..Config::shanghai() + ..Config::cancun() }; const KERNEL_VERSION: &str = env!("GIT_HASH"); diff --git a/etherlink/sputnikvm/core/src/eval/macros.rs b/etherlink/sputnikvm/core/src/eval/macros.rs index 3fd7a9f6ed05d4335f0daa9f0124d5dd3dd3eb30..34c537d58d853eb47b27d4cd8b1db109fc253c11 100644 --- a/etherlink/sputnikvm/core/src/eval/macros.rs +++ b/etherlink/sputnikvm/core/src/eval/macros.rs @@ -130,3 +130,13 @@ macro_rules! as_usize_or_fail { $v.as_usize() }}; } + +macro_rules! as_usize_or_revert { + ($value:expr) => {{ + if $value > U256::from(usize::MAX) { + return Control::Exit(crate::ExitReason::Revert(ExitRevert::Reverted)); + } else { + $value.as_usize() + } + }}; +} diff --git a/etherlink/sputnikvm/core/src/eval/misc.rs b/etherlink/sputnikvm/core/src/eval/misc.rs index 8271d5f6c6b66a8d4818c1fdbb1a5e9c6ad2f6e9..38b4afb10bff497fd27de654fecda36e73b2ed98 100644 --- a/etherlink/sputnikvm/core/src/eval/misc.rs +++ b/etherlink/sputnikvm/core/src/eval/misc.rs @@ -110,6 +110,28 @@ pub fn mstore8(state: &mut Machine) -> Control { } } +#[inline] +pub fn mcopy(state: &mut Machine) -> Control { + pop_u256!(state, dst, src, len); + + try_or_fail!(state.memory.resize_offset(U256::max(dst, src), len)); + + if len == U256::zero() { + return Control::Continue(1); + } + + let dst = as_usize_or_revert!(dst); + let src = as_usize_or_revert!(src); + let len = as_usize_or_revert!(len); + + let data = state.memory.get(src, len); + + match state.memory.set(dst, &data, None) { + Ok(()) => Control::Continue(1), + Err(e) => Control::Exit(e.into()), + } +} + #[inline] pub fn jump(state: &mut Machine) -> Control { pop_u256!(state, dest); diff --git a/etherlink/sputnikvm/core/src/eval/mod.rs b/etherlink/sputnikvm/core/src/eval/mod.rs index 519f5d92585aac1f4b3b02fbb315ae0950e56740..580fba4bf2dcbae22ac0ddbcd24d746d05685849 100644 --- a/etherlink/sputnikvm/core/src/eval/mod.rs +++ b/etherlink/sputnikvm/core/src/eval/mod.rs @@ -160,6 +160,10 @@ fn eval_jump(state: &mut Machine, _opcode: Opcode, _position: usize) -> Control self::misc::jump(state) } +fn eval_mcopy(state: &mut Machine, _opcode: Opcode, _position: usize) -> Control { + self::misc::mcopy(state) +} + fn eval_jumpi(state: &mut Machine, _opcode: Opcode, _position: usize) -> Control { self::misc::jumpi(state) } @@ -492,6 +496,7 @@ pub fn eval(state: &mut Machine, opcode: Opcode, position: usize) -> Control { table[Opcode::MLOAD.as_usize()] = eval_mload as _; table[Opcode::MSTORE.as_usize()] = eval_mstore as _; table[Opcode::MSTORE8.as_usize()] = eval_mstore8 as _; + table[Opcode::MCOPY.as_usize()] = eval_mcopy as _; table[Opcode::JUMP.as_usize()] = eval_jump as _; table[Opcode::JUMPI.as_usize()] = eval_jumpi as _; table[Opcode::PC.as_usize()] = eval_pc as _; diff --git a/etherlink/sputnikvm/core/src/opcode.rs b/etherlink/sputnikvm/core/src/opcode.rs index 15814b0acfb39991e447fd831b8e51ca3c158fd9..67f8dafd6ec39e34a39dd373a3b0d93c45ce031a 100644 --- a/etherlink/sputnikvm/core/src/opcode.rs +++ b/etherlink/sputnikvm/core/src/opcode.rs @@ -83,6 +83,8 @@ impl Opcode { pub const MSTORE: Opcode = Opcode(0x52); /// `MSTORE8` pub const MSTORE8: Opcode = Opcode(0x53); + /// `MCOPY` + pub const MCOPY: Opcode = Opcode(0x5e); /// `JUMP` pub const JUMP: Opcode = Opcode(0x56); /// `JUMPI` @@ -189,6 +191,10 @@ impl Opcode { pub const SELFBALANCE: Opcode = Opcode(0x47); /// `BASEFEE` pub const BASEFEE: Opcode = Opcode(0x48); + /// `BLOBHASH` + pub const BLOBHASH: Opcode = Opcode(0x49); + /// `BLOBBASEFEE` + pub const BLOBBASEFEE: Opcode = Opcode(0x4a); /// `ORIGIN` pub const ORIGIN: Opcode = Opcode(0x32); /// `CALLER` @@ -223,6 +229,10 @@ impl Opcode { pub const SLOAD: Opcode = Opcode(0x54); /// `SSTORE` pub const SSTORE: Opcode = Opcode(0x55); + /// `TLOAD` + pub const TLOAD: Opcode = Opcode(0x5c); + /// `TSTORE` + pub const TSTORE: Opcode = Opcode(0x5d); /// `GAS` pub const GAS: Opcode = Opcode(0x5a); /// `LOGn` diff --git a/etherlink/sputnikvm/gasometer/src/consts.rs b/etherlink/sputnikvm/gasometer/src/consts.rs index 285a4c1ac8ece7e23886662a778c76c36cefeb56..c1c3da2c40966582581c5be4c395d95060af6810 100644 --- a/etherlink/sputnikvm/gasometer/src/consts.rs +++ b/etherlink/sputnikvm/gasometer/src/consts.rs @@ -19,3 +19,7 @@ pub const G_SHA3WORD: u64 = 6; pub const G_COPY: u64 = 3; pub const G_BLOCKHASH: u64 = 20; pub const G_CODEDEPOSIT: u64 = 200; +pub const G_TLOAD: u64 = 100; +pub const G_TSTORE: u64 = 100; +pub const G_BLOBHASH: u64 = 3; +pub const G_BLOBBASEFEE: u64 = 2; diff --git a/etherlink/sputnikvm/gasometer/src/lib.rs b/etherlink/sputnikvm/gasometer/src/lib.rs index ce60a3907f4609783725d26c3758a1b1f188cb65..1cf9be9e77592118b6b477cf06f3064c11482d25 100644 --- a/etherlink/sputnikvm/gasometer/src/lib.rs +++ b/etherlink/sputnikvm/gasometer/src/lib.rs @@ -477,6 +477,10 @@ pub fn dynamic_opcode_cost( Opcode::BASEFEE if config.has_base_fee => GasCost::Base, Opcode::BASEFEE => GasCost::Invalid(opcode), + Opcode::BLOBHASH if config.has_blob_instructions => GasCost::BlobHash, + Opcode::BLOBHASH => GasCost::Invalid(opcode), + Opcode::BLOBBASEFEE if config.has_blob_instructions => GasCost::BlobBaseFee, + Opcode::BLOBBASEFEE => GasCost::Invalid(opcode), Opcode::EXTCODESIZE => { let target = stack.peek(0)?.into(); @@ -536,6 +540,10 @@ pub fn dynamic_opcode_cost( Opcode::CALLDATACOPY | Opcode::CODECOPY => GasCost::VeryLowCopy { len: U256::from_big_endian(&stack.peek(2)?[..]), }, + Opcode::MCOPY if config.has_mcopy => GasCost::VeryLowCopy { + len: U256::from_big_endian(&stack.peek(2)?[..]), + }, + Opcode::MCOPY => GasCost::Invalid(opcode), Opcode::EXP => GasCost::Exp { power: U256::from_big_endian(&stack.peek(1)?[..]), }, @@ -576,6 +584,10 @@ pub fn dynamic_opcode_cost( target_is_cold: handler.is_cold(address, Some(index))?, } } + Opcode::TLOAD if config.has_transient_storage => GasCost::TLoad, + Opcode::TLOAD => GasCost::Invalid(opcode), + Opcode::TSTORE if config.has_transient_storage => GasCost::TStore, + Opcode::TSTORE => GasCost::Invalid(opcode), Opcode::LOG0 if !is_static => GasCost::Log { n: 0, len: U256::from_big_endian(&stack.peek(1)?[..]), @@ -642,10 +654,12 @@ pub fn dynamic_opcode_cost( len: U256::from_big_endian(&stack.peek(1)?[..]), }), - Opcode::CODECOPY | Opcode::CALLDATACOPY | Opcode::RETURNDATACOPY => Some(MemoryCost { - offset: U256::from_big_endian(&stack.peek(0)?[..]), - len: U256::from_big_endian(&stack.peek(2)?[..]), - }), + Opcode::CODECOPY | Opcode::CALLDATACOPY | Opcode::RETURNDATACOPY | Opcode::MCOPY => { + Some(MemoryCost { + offset: U256::from_big_endian(&stack.peek(0)?[..]), + len: U256::from_big_endian(&stack.peek(2)?[..]), + }) + } Opcode::EXTCODECOPY => Some(MemoryCost { offset: U256::from_big_endian(&stack.peek(1)?[..]), @@ -835,6 +849,10 @@ impl<'config> Inner<'config> { self.config.gas_ext_code_hash, self.config, ), + GasCost::TLoad => consts::G_TLOAD, + GasCost::TStore => consts::G_TSTORE, + GasCost::BlobHash => consts::G_BLOBHASH, + GasCost::BlobBaseFee => consts::G_BLOBBASEFEE, }) } @@ -991,6 +1009,14 @@ pub enum GasCost { /// True if target has not been previously accessed in this transaction target_is_cold: bool, }, + /// Gas cost for `TLOAD`. + TLoad, + /// Gas cost for `TSTORE`. + TStore, + /// Gas cost for `BLOBHASH`. + BlobHash, + /// Gas cost for `BLOBBASEFEE`. + BlobBaseFee, } /// Storage opcode will access. Used for tracking accessed storage (EIP-2929). diff --git a/etherlink/sputnikvm/runtime/src/eval/mod.rs b/etherlink/sputnikvm/runtime/src/eval/mod.rs index b2965335f97e380795e836b40b619c53c32fd58e..4421a4027b6da35e7f638264f5de1b153d6f447e 100644 --- a/etherlink/sputnikvm/runtime/src/eval/mod.rs +++ b/etherlink/sputnikvm/runtime/src/eval/mod.rs @@ -44,6 +44,8 @@ pub fn eval(state: &mut Runtime, opcode: Opcode, handler: &mut H) -> Opcode::GASLIMIT => system::gaslimit(state, handler), Opcode::SLOAD => system::sload(state, handler), Opcode::SSTORE => system::sstore(state, handler), + Opcode::TLOAD => system::tload(state, handler), + Opcode::TSTORE => system::tstore(state, handler), Opcode::GAS => system::gas(state, handler), Opcode::LOG0 => system::log(state, 0, handler), Opcode::LOG1 => system::log(state, 1, handler), @@ -59,6 +61,8 @@ pub fn eval(state: &mut Runtime, opcode: Opcode, handler: &mut H) -> Opcode::STATICCALL => system::call(state, CallScheme::StaticCall, handler), Opcode::CHAINID => system::chainid(state, handler), Opcode::BASEFEE => system::base_fee(state, handler), + Opcode::BLOBHASH => system::blob_hash(state, handler), + Opcode::BLOBBASEFEE => system::blob_base_fee(state, handler), _ => handle_other(state, opcode, handler), } } diff --git a/etherlink/sputnikvm/runtime/src/eval/system.rs b/etherlink/sputnikvm/runtime/src/eval/system.rs index 5b535375103539aa5da6367ebc8a1593b462413e..7e8f2ff4e1085cae2dbbeb02c73525acfd04d659 100644 --- a/etherlink/sputnikvm/runtime/src/eval/system.rs +++ b/etherlink/sputnikvm/runtime/src/eval/system.rs @@ -90,6 +90,22 @@ pub fn base_fee(runtime: &mut Runtime, handler: &H) -> Control { Control::Continue } +pub fn blob_hash(runtime: &mut Runtime, handler: &H) -> Control { + pop!(runtime, index); + let ret = handler.blob_hash(index); + push!(runtime, ret); + + Control::Continue +} + +pub fn blob_base_fee(runtime: &mut Runtime, handler: &H) -> Control { + let mut ret = H256::default(); + handler.block_blob_base_fee().to_big_endian(&mut ret[..]); + push!(runtime, ret); + + Control::Continue +} + pub fn extcodesize(runtime: &mut Runtime, handler: &H) -> Control { pop!(runtime, address); push_u256!(runtime, handler.code_size(address.into())); @@ -228,6 +244,35 @@ pub fn sstore(runtime: &mut Runtime, handler: &mut H) -> Control } } +pub fn tload(runtime: &mut Runtime, handler: &H) -> Control { + pop!(runtime, index); + let value = handler.transient_storage(runtime.context.address, index); + push!(runtime, value); + + event!(TLoad { + address: runtime.context.address, + index, + value + }); + + Control::Continue +} + +pub fn tstore(runtime: &mut Runtime, handler: &mut H) -> Control { + pop!(runtime, index, value); + + event!(TStore { + address: runtime.context.address, + index, + value + }); + + match handler.set_transient_storage(runtime.context.address, index, value) { + Ok(()) => Control::Continue, + Err(e) => Control::Exit(e.into()), + } +} + pub fn gas(runtime: &mut Runtime, handler: &H) -> Control { push_u256!(runtime, handler.gas_left()); diff --git a/etherlink/sputnikvm/runtime/src/handler.rs b/etherlink/sputnikvm/runtime/src/handler.rs index e87b88d53c6618ee94f8e5321f7e9e8f29526026..78b4bd50c831e0f3f03e50487599cc7b90d172b0 100644 --- a/etherlink/sputnikvm/runtime/src/handler.rs +++ b/etherlink/sputnikvm/runtime/src/handler.rs @@ -37,6 +37,8 @@ pub trait Handler { fn code(&self, address: H160) -> Vec; /// Get storage value of address at index. fn storage(&mut self, address: H160, index: H256) -> H256; + /// Get transient storage value of address at index. + fn transient_storage(&self, address: H160, index: H256) -> H256; /// Get original storage value of address at index. fn original_storage(&mut self, address: H160, index: H256) -> H256; @@ -62,6 +64,10 @@ pub trait Handler { fn block_gas_limit(&self) -> U256; /// Environmental block base fee. fn block_base_fee_per_gas(&self) -> U256; + /// Returns the value of the blob versioned hash at index i. + fn blob_hash(&self, index: H256) -> H256; + /// Returns the value of the blob base-fee of the current block it is executing in. + fn block_blob_base_fee(&self) -> U256; /// Get environmental chain ID. fn chain_id(&self) -> U256; @@ -79,6 +85,13 @@ pub trait Handler { /// Set storage value of address at index. fn set_storage(&mut self, address: H160, index: H256, value: H256) -> Result<(), ExitError>; + /// Set transient storage value of address at index. + fn set_transient_storage( + &mut self, + address: H160, + index: H256, + value: H256, + ) -> Result<(), ExitError>; /// Create a log owned by address with given topics and data. fn log(&mut self, address: H160, topics: Vec, data: Vec) -> Result<(), ExitError>; /// Mark an address to be deleted, with funds transferred to target. diff --git a/etherlink/sputnikvm/runtime/src/lib.rs b/etherlink/sputnikvm/runtime/src/lib.rs index 8809e58f35943c3f4327f3e3bf2cf00e180e1d7e..396ce0aa6470fbb8f8cec7ad87e0fc5e76959925 100644 --- a/etherlink/sputnikvm/runtime/src/lib.rs +++ b/etherlink/sputnikvm/runtime/src/lib.rs @@ -288,6 +288,15 @@ pub struct Config { pub has_push0: bool, /// Whether the gasometer is running in estimate mode. pub estimate: bool, + /// Whether the opcode SELFEDESTRUCT is considered deprecated. + /// See [EIP-6780](https://eips.ethereum.org/EIPS/eip-6780) + pub selfdestruct_deprecated: bool, + /// Has transient storage. + pub has_transient_storage: bool, + /// Has mcopy. + pub has_mcopy: bool, + /// Has blob instructions. + pub has_blob_instructions: bool, } impl Config { @@ -342,6 +351,10 @@ impl Config { has_base_fee: false, has_push0: false, estimate: false, + selfdestruct_deprecated: false, + has_transient_storage: false, + has_mcopy: false, + has_blob_instructions: false, } } @@ -396,6 +409,10 @@ impl Config { has_base_fee: false, has_push0: false, estimate: false, + selfdestruct_deprecated: false, + has_transient_storage: false, + has_mcopy: false, + has_blob_instructions: false, } } @@ -419,6 +436,11 @@ impl Config { Self::config_with_derived_values(DerivedConfigInputs::shanghai()) } + /// Cancun hard fork configuration. + pub const fn cancun() -> Config { + Self::config_with_derived_values(DerivedConfigInputs::cancun()) + } + const fn config_with_derived_values(inputs: DerivedConfigInputs) -> Config { let DerivedConfigInputs { gas_storage_read_warm, @@ -430,6 +452,10 @@ impl Config { disallow_executable_format, warm_coinbase_address, max_initcode_size, + selfdestruct_deprecated, + has_transient_storage, + has_mcopy, + has_blob_instructions, } = inputs; // See https://eips.ethereum.org/EIPS/eip-2929 @@ -493,6 +519,10 @@ impl Config { has_base_fee, has_push0, estimate: false, + selfdestruct_deprecated, + has_transient_storage, + has_mcopy, + has_blob_instructions, } } } @@ -509,6 +539,10 @@ struct DerivedConfigInputs { disallow_executable_format: bool, warm_coinbase_address: bool, max_initcode_size: Option, + selfdestruct_deprecated: bool, + has_transient_storage: bool, + has_mcopy: bool, + has_blob_instructions: bool, } impl DerivedConfigInputs { @@ -523,6 +557,10 @@ impl DerivedConfigInputs { disallow_executable_format: false, warm_coinbase_address: false, max_initcode_size: None, + selfdestruct_deprecated: false, + has_transient_storage: false, + has_mcopy: false, + has_blob_instructions: false, } } @@ -537,6 +575,10 @@ impl DerivedConfigInputs { disallow_executable_format: true, warm_coinbase_address: false, max_initcode_size: None, + selfdestruct_deprecated: false, + has_transient_storage: false, + has_mcopy: false, + has_blob_instructions: false, } } @@ -551,6 +593,10 @@ impl DerivedConfigInputs { disallow_executable_format: true, warm_coinbase_address: false, max_initcode_size: None, + selfdestruct_deprecated: false, + has_transient_storage: false, + has_mcopy: false, + has_blob_instructions: false, } } @@ -566,6 +612,21 @@ impl DerivedConfigInputs { warm_coinbase_address: true, // 2 * 24576 as per EIP-3860 max_initcode_size: Some(0xC000), + selfdestruct_deprecated: false, + has_transient_storage: false, + has_mcopy: false, + has_blob_instructions: false, + } + } + + const fn cancun() -> Self { + let base = Self::shanghai(); + Self { + selfdestruct_deprecated: true, + has_transient_storage: true, + has_mcopy: true, + has_blob_instructions: true, + ..base } } } diff --git a/etherlink/sputnikvm/runtime/src/tracing.rs b/etherlink/sputnikvm/runtime/src/tracing.rs index f9fed1961f83e3b5be0ba480039ae3c867507bf8..c502bfb66147d945843f3a1a86f066a53697e5c6 100644 --- a/etherlink/sputnikvm/runtime/src/tracing.rs +++ b/etherlink/sputnikvm/runtime/src/tracing.rs @@ -32,6 +32,16 @@ pub enum Event<'a> { index: H256, value: H256, }, + TLoad { + address: H160, + index: H256, + value: H256, + }, + TStore { + address: H160, + index: H256, + value: H256, + }, } // Expose `listener::with` to the crate only. diff --git a/etherlink/sputnikvm/src/backend/memory.rs b/etherlink/sputnikvm/src/backend/memory.rs index 37e7718b10cd36e5ce976824033f38f296e45ddb..353750e64e250735d0b8fafa8b5804611d6c0ce6 100644 --- a/etherlink/sputnikvm/src/backend/memory.rs +++ b/etherlink/sputnikvm/src/backend/memory.rs @@ -31,6 +31,8 @@ pub struct MemoryVicinity { pub block_gas_limit: U256, /// Environmental base fee per gas. pub block_base_fee_per_gas: U256, + /// Environmental blob base fee. + pub block_blob_base_fee: U256, /// Environmental randomness. /// /// In Ethereum, this is the randomness beacon provided by the beacon @@ -61,15 +63,24 @@ pub struct MemoryAccount { pub struct MemoryBackend<'vicinity> { vicinity: &'vicinity MemoryVicinity, state: BTreeMap, + blob_hashes: BTreeMap, + transient_state: BTreeMap<(H160, H256), H256>, logs: Vec, } impl<'vicinity> MemoryBackend<'vicinity> { /// Create a new memory backend. - pub fn new(vicinity: &'vicinity MemoryVicinity, state: BTreeMap) -> Self { + pub fn new( + vicinity: &'vicinity MemoryVicinity, + state: BTreeMap, + blob_hashes: BTreeMap, + transient_state: BTreeMap<(H160, H256), H256>, + ) -> Self { Self { vicinity, state, + blob_hashes, + transient_state, logs: Vec::new(), } } @@ -121,10 +132,19 @@ impl<'vicinity> Backend for MemoryBackend<'vicinity> { fn block_gas_limit(&self) -> U256 { self.vicinity.block_gas_limit } + + fn blob_hash(&self, index: H256) -> H256 { + self.blob_hashes.get(&index).copied().unwrap_or_default() + } + fn block_base_fee_per_gas(&self) -> U256 { self.vicinity.block_base_fee_per_gas } + fn block_blob_base_fee(&self) -> U256 { + self.vicinity.block_blob_base_fee + } + fn chain_id(&self) -> U256 { self.vicinity.chain_id } @@ -157,6 +177,13 @@ impl<'vicinity> Backend for MemoryBackend<'vicinity> { .unwrap_or_default() } + fn transient_storage(&self, address: H160, index: H256) -> H256 { + self.transient_state + .get(&(address, index)) + .cloned() + .unwrap_or_default() + } + fn original_storage(&self, address: H160, index: H256) -> Option { Some(self.storage(address, index)) } diff --git a/etherlink/sputnikvm/src/backend/mod.rs b/etherlink/sputnikvm/src/backend/mod.rs index 7cda7fd1d8716a7f24294411a70ba72e9231947a..c9bb01200fc2f9b95ecea28282cacf92b813d0df 100644 --- a/etherlink/sputnikvm/src/backend/mod.rs +++ b/etherlink/sputnikvm/src/backend/mod.rs @@ -70,8 +70,12 @@ pub trait Backend { fn block_randomness(&self) -> Option; /// Environmental block gas limit. fn block_gas_limit(&self) -> U256; + /// Environmental blob hash at index. + fn blob_hash(&self, index: H256) -> H256; /// Environmental block base fee. fn block_base_fee_per_gas(&self) -> U256; + /// Returns the value of the blob base-fee of the current block it is executing in. + fn block_blob_base_fee(&self) -> U256; /// Environmental chain ID. fn chain_id(&self) -> U256; @@ -83,6 +87,8 @@ pub trait Backend { fn code(&self, address: H160) -> Vec; /// Get storage value of address at index. fn storage(&self, address: H160, index: H256) -> H256; + /// Get transient storage value of address at index. + fn transient_storage(&self, address: H160, index: H256) -> H256; /// Get original storage value of address at index, if available. fn original_storage(&self, address: H160, index: H256) -> Option; } diff --git a/etherlink/sputnikvm/src/executor/stack/executor.rs b/etherlink/sputnikvm/src/executor/stack/executor.rs index 480ea3bd43fb3ea67120aa559c3e44d0eaff63dc..3364e470e40dc9553fe33efa2a97723343f3dd98 100644 --- a/etherlink/sputnikvm/src/executor/stack/executor.rs +++ b/etherlink/sputnikvm/src/executor/stack/executor.rs @@ -206,6 +206,7 @@ pub trait StackState<'config>: Backend { fn inc_nonce(&mut self, address: H160) -> Result<(), ExitError>; fn set_storage(&mut self, address: H160, key: H256, value: H256); + fn set_transient_storage(&mut self, address: H160, key: H256, value: H256); fn reset_storage(&mut self, address: H160); fn log(&mut self, address: H160, topics: Vec, data: Vec); fn set_deleted(&mut self, address: H160); @@ -1049,6 +1050,10 @@ impl<'config, 'precompiles, S: StackState<'config>, P: PrecompileSet> Handler self.state.storage(address, index) } + fn transient_storage(&self, address: H160, index: H256) -> H256 { + self.state.transient_storage(address, index) + } + fn original_storage(&mut self, address: H160, index: H256) -> H256 { self.state .original_storage(address, index) @@ -1120,9 +1125,15 @@ impl<'config, 'precompiles, S: StackState<'config>, P: PrecompileSet> Handler fn block_gas_limit(&self) -> U256 { self.state.block_gas_limit() } + fn blob_hash(&self, index: H256) -> H256 { + self.state.blob_hash(index) + } fn block_base_fee_per_gas(&self) -> U256 { self.state.block_base_fee_per_gas() } + fn block_blob_base_fee(&self) -> U256 { + self.state.block_blob_base_fee() + } fn chain_id(&self) -> U256 { self.state.chain_id() } @@ -1136,6 +1147,16 @@ impl<'config, 'precompiles, S: StackState<'config>, P: PrecompileSet> Handler Ok(()) } + fn set_transient_storage( + &mut self, + address: H160, + index: H256, + value: H256, + ) -> Result<(), ExitError> { + self.state.set_transient_storage(address, index, value); + Ok(()) + } + fn log(&mut self, address: H160, topics: Vec, data: Vec) -> Result<(), ExitError> { self.state.log(address, topics, data); Ok(()) diff --git a/etherlink/sputnikvm/src/executor/stack/memory.rs b/etherlink/sputnikvm/src/executor/stack/memory.rs index 957b2b3d56d4ad288a0c091c6c983c2567e1ae52..26f193a67f6e4613baa00ce966928b2f730863d4 100644 --- a/etherlink/sputnikvm/src/executor/stack/memory.rs +++ b/etherlink/sputnikvm/src/executor/stack/memory.rs @@ -23,6 +23,7 @@ pub struct MemoryStackSubstate<'config> { logs: Vec, accounts: BTreeMap, storages: BTreeMap<(H160, H256), H256>, + transient_storages: BTreeMap<(H160, H256), H256>, deletes: BTreeSet, } @@ -34,6 +35,7 @@ impl<'config> MemoryStackSubstate<'config> { logs: Vec::new(), accounts: BTreeMap::new(), storages: BTreeMap::new(), + transient_storages: BTreeMap::new(), deletes: BTreeSet::new(), } } @@ -119,6 +121,7 @@ impl<'config> MemoryStackSubstate<'config> { logs: Vec::new(), accounts: BTreeMap::new(), storages: BTreeMap::new(), + transient_storages: BTreeMap::new(), deletes: BTreeSet::new(), }; mem::swap(&mut entering, self); @@ -232,6 +235,18 @@ impl<'config> MemoryStackSubstate<'config> { None } + pub fn known_transient_storage(&self, address: H160, key: H256) -> Option { + if let Some(value) = self.transient_storages.get(&(address, key)) { + return Some(*value); + } + + if let Some(parent) = self.parent.as_ref() { + return parent.known_transient_storage(address, key); + } + + None + } + pub fn known_original_storage(&self, address: H160) -> Option { if let Some(account) = self.accounts.get(&address) { if account.reset { @@ -314,6 +329,10 @@ impl<'config> MemoryStackSubstate<'config> { self.storages.insert((address, key), value); } + pub fn set_transient_storage(&mut self, address: H160, key: H256, value: H256) { + self.transient_storages.insert((address, key), value); + } + pub fn reset_storage(&mut self, address: H160, backend: &B) { let mut removing = Vec::new(); @@ -436,6 +455,14 @@ impl<'backend, 'config, B: Backend> Backend for MemoryStackState<'backend, 'conf self.backend.block_base_fee_per_gas() } + fn blob_hash(&self, index: H256) -> H256 { + self.backend.blob_hash(index) + } + + fn block_blob_base_fee(&self) -> U256 { + self.backend.block_blob_base_fee() + } + fn chain_id(&self) -> U256 { self.backend.chain_id() } @@ -462,6 +489,12 @@ impl<'backend, 'config, B: Backend> Backend for MemoryStackState<'backend, 'conf .unwrap_or_else(|| self.backend.storage(address, key)) } + fn transient_storage(&self, address: H160, key: H256) -> H256 { + self.substate + .known_transient_storage(address, key) + .unwrap_or_else(|| self.backend.transient_storage(address, key)) + } + fn original_storage(&self, address: H160, key: H256) -> Option { if let Some(value) = self.substate.known_original_storage(address) { return Some(value); @@ -526,6 +559,10 @@ impl<'backend, 'config, B: Backend> StackState<'config> for MemoryStackState<'ba self.substate.set_storage(address, key, value) } + fn set_transient_storage(&mut self, address: H160, key: H256, value: H256) { + self.substate.set_transient_storage(address, key, value) + } + fn reset_storage(&mut self, address: H160) { self.substate.reset_storage(address, self.backend); }