You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by tm...@apache.org on 2020/02/25 17:09:41 UTC
[impala] branch master updated (90ab610 -> f228121)
This is an automated email from the ASF dual-hosted git repository.
tmarshall pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git.
from 90ab610 Convert dataload hdfs copy commands to LOAD DATA statements
new 571131f IMPALA-9075: Add support for reading zstd text files
new 777d0d2 IMPALA-8852: Skip short-circuit config check for dedicated coordinator
new 1e61677 IMPALA-8712: Make ExecQueryFInstances async
new f228121 IMPALA-9226: Bump ORC version to 1.6.2-p7
The 4 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
be/src/common/global-flags.cc | 1 +
be/src/exec/hdfs-text-scanner.cc | 1 +
be/src/exec/hdfs-text-scanner.h | 1 +
be/src/runtime/coordinator-backend-state.cc | 322 +-
be/src/runtime/coordinator-backend-state.h | 160 +-
be/src/runtime/coordinator.cc | 93 +-
be/src/runtime/coordinator.h | 19 +-
be/src/runtime/exec-env.cc | 7 -
be/src/runtime/exec-env.h | 5 -
be/src/runtime/query-state.cc | 2 +
be/src/util/backend-gflag-util.cc | 2 +
be/src/util/compress.h | 2 +-
be/src/util/counting-barrier.h | 4 +-
be/src/util/decompress-test.cc | 37 +-
be/src/util/decompress.cc | 50 +-
be/src/util/decompress.h | 20 +-
bin/impala-config.sh | 4 +-
bin/rat_exclude_files.txt | 2 +
common/thrift/BackendGflags.thrift | 22 +-
.../org/apache/impala/service/BackendConfig.java | 4 +
.../org/apache/impala/service/JniFrontend.java | 8 +-
.../org/apache/impala/service/JniFrontendTest.java | 73 +-
testdata/data/text_large_zstd.txt | 10000000 ++++++++++++++++
testdata/data/text_large_zstd.zst | Bin 0 -> 3070087 bytes
..._interop.py => test_hive_text_codec_interop.py} | 66 +-
tests/custom_cluster/test_rpc_exception.py | 63 +-
tests/failure/test_failpoints.py | 5 +
tests/query_test/test_compressed_formats.py | 71 +-
28 files changed, 10000725 insertions(+), 319 deletions(-)
create mode 100644 testdata/data/text_large_zstd.txt
create mode 100644 testdata/data/text_large_zstd.zst
copy tests/custom_cluster/{test_hive_parquet_codec_interop.py => test_hive_text_codec_interop.py} (56%)
[impala] 03/04: IMPALA-8712: Make ExecQueryFInstances async
Posted by tm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
tmarshall pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git
commit 1e616774d4d3a00e002d1e383ccd89c46f6d9010
Author: Thomas Tauber-Marshall <tm...@cloudera.com>
AuthorDate: Wed Dec 4 11:47:05 2019 -0800
IMPALA-8712: Make ExecQueryFInstances async
This patch refactors the ExecQueryFInstances rpc to be asychronous.
Previously, Impala would issue all the Exec()s, wait for all of them
to complete, and then check if any of them resulted in an error. We
now stop issuing Exec()s and cancel any that are still in flight as
soon as an error occurs.
It also performs some cleanup around the thread safety of
Coordinator::BackendState, including adding comments and DCHECKS.
=== Exec RPC Thread Pool ===
This patch also removes the 'exec_rpc_thread_pool_' from ExecEnv. This
thread pool was used to partially simulate async Exec() prior to the
switch to KRPC, which provides built-in async rpc capabilities.
Removing this thread pool has potential performance implications, as
it means that the Exec() parameters are serialized in serialize rather
than in parallel (with the level of parallelism determined by the size
of the thread pool, which was configurable by an Advanced flag and
defaulted to 12).
To ensure we don't regress query startup times, I did some performance
testing. All tests were done on a 10 node cluster. The baseline used
for the tests did not include IMPALA-9181, a perf optimization for
query startup done to facilitate this work.
I ran TPCH 100 at concurrency levels of 1, 4, and 8 and extracted the
query startup times from the profiles. For each concurrency level, the
average regression in query startup time was < 2ms. Because query e2e
running time was much longer than this, there was no noticable change
in total query time.
I also ran a 'worst case scenario' with a table with 10,000 pertitions
to create a very large Exec() payload to serialize (~1.21MB vs.
~10KB-30KB for TPCH 100). Again, change in query startup time was
neglible.
============================
Testing:
- Added a e2e test that verifies that a query where an Exec() fails
doesn't wait for all Exec()s to complete before cancelling and
returning the error to the client.
Change-Id: I33ec96e5885af094c294cd3a76c242995263ba32
Reviewed-on: http://gerrit.cloudera.org:8080/15154
Reviewed-by: Thomas Tauber-Marshall <tm...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
be/src/common/global-flags.cc | 1 +
be/src/runtime/coordinator-backend-state.cc | 322 ++++++++++++++++------------
be/src/runtime/coordinator-backend-state.h | 160 +++++++++-----
be/src/runtime/coordinator.cc | 93 +++++---
be/src/runtime/coordinator.h | 19 +-
be/src/runtime/exec-env.cc | 7 -
be/src/runtime/exec-env.h | 5 -
be/src/runtime/query-state.cc | 2 +
be/src/util/counting-barrier.h | 4 +-
tests/custom_cluster/test_rpc_exception.py | 63 ++++--
tests/failure/test_failpoints.py | 5 +
11 files changed, 426 insertions(+), 255 deletions(-)
diff --git a/be/src/common/global-flags.cc b/be/src/common/global-flags.cc
index 539ece2..dea6e27 100644
--- a/be/src/common/global-flags.cc
+++ b/be/src/common/global-flags.cc
@@ -346,6 +346,7 @@ REMOVED_FLAG(adls_read_chunk_size);
REMOVED_FLAG(authorization_policy_file);
REMOVED_FLAG(be_service_threads);
REMOVED_FLAG(cgroup_hierarchy_path);
+REMOVED_FLAG(coordinator_rpc_threads);
REMOVED_FLAG(disable_admission_control);
REMOVED_FLAG(disable_mem_pools);
REMOVED_FLAG(enable_accept_queue_server);
diff --git a/be/src/runtime/coordinator-backend-state.cc b/be/src/runtime/coordinator-backend-state.cc
index b5e8452..3d53700 100644
--- a/be/src/runtime/coordinator-backend-state.cc
+++ b/be/src/runtime/coordinator-backend-state.cc
@@ -66,21 +66,20 @@ const char* Coordinator::BackendState::InstanceStats::LAST_REPORT_TIME_DESC =
"Last report received time";
Coordinator::BackendState::BackendState(const QuerySchedule& schedule,
- const TQueryCtx& query_ctx, int state_idx,
- TRuntimeFilterMode::type filter_mode, const BackendExecParams& exec_params)
+ const TQueryCtx& query_ctx, int state_idx, TRuntimeFilterMode::type filter_mode,
+ const BackendExecParams& exec_params)
: schedule_(schedule),
state_idx_(state_idx),
filter_mode_(filter_mode),
backend_exec_params_(&exec_params),
+ host_(backend_exec_params_->be_desc.address),
+ krpc_host_(backend_exec_params_->be_desc.krpc_address),
query_ctx_(query_ctx),
- query_id_(schedule.query_id()) {}
+ query_id_(schedule.query_id()),
+ num_remaining_instances_(backend_exec_params_->instance_params.size()) {}
void Coordinator::BackendState::Init(const vector<FragmentStats*>& fragment_stats,
RuntimeProfile* host_profile_parent, ObjectPool* obj_pool) {
- host_ = backend_exec_params_->be_desc.address;
- krpc_host_ = backend_exec_params_->be_desc.krpc_address;
- num_remaining_instances_ = backend_exec_params_->instance_params.size();
-
host_profile_ = RuntimeProfile::Create(obj_pool, TNetworkAddressToString(host_));
host_profile_parent->AddChild(host_profile_);
RuntimeProfile::Counter* admission_slots =
@@ -163,124 +162,156 @@ void Coordinator::BackendState::SetRpcParams(const DebugOptions& debug_options,
}
}
-void Coordinator::BackendState::SetExecError(const Status& status) {
+void Coordinator::BackendState::SetExecError(
+ const Status& status, TypedCountingBarrier<Status>* exec_status_barrier) {
const string ERR_TEMPLATE = "ExecQueryFInstances rpc query_id=$0 failed: $1";
const string& err_msg =
Substitute(ERR_TEMPLATE, PrintId(query_id_), status.msg().GetFullMessageDetails());
LOG(ERROR) << err_msg;
status_ = Status::Expected(err_msg);
+ exec_done_ = true;
+ exec_status_barrier->NotifyRemaining(status);
}
-void Coordinator::BackendState::Exec(const DebugOptions& debug_options,
- const FilterRoutingTable& filter_routing_table,
- const kudu::Slice& serialized_query_ctx, CountingBarrier* exec_complete_barrier) {
- const auto trigger = MakeScopeExitTrigger([&]() {
- // Ensure that 'last_report_time_ms_' is set prior to the barrier being notified.
- {
- // Since last_report_time_ms_ is protected by lock_ it must be acquired before
- // updating last_report_time_ms_. The lock_ is guaranteed to not be held by this
- // method when this lambda runs since it has not already been acquired by the
- // method. The lambda executes in an object destructor and C++ destroys objects in
- // the reverse order they were created.
- lock_guard<mutex> lock(lock_);
- last_report_time_ms_ = GenerateReportTimestamp();
- }
- exec_complete_barrier->Notify();
- });
+void Coordinator::BackendState::WaitOnExecRpc() {
+ unique_lock<mutex> l(lock_);
+ WaitOnExecLocked(&l);
+}
- // Do not issue an ExecQueryFInstances RPC if there are no fragment instances
- // scheduled to run on this backend.
- if (IsEmptyBackend()) {
- DCHECK(backend_exec_params_->is_coord_backend);
- return;
+void Coordinator::BackendState::WaitOnExecLocked(unique_lock<mutex>* l) {
+ DCHECK(l->owns_lock());
+ while (!exec_done_) {
+ exec_done_cv_.Wait(*l);
}
+}
- std::unique_ptr<ControlServiceProxy> proxy;
- Status get_proxy_status = ControlService::GetProxy(krpc_host_, host_.hostname, &proxy);
- if (!get_proxy_status.ok()) {
- SetExecError(get_proxy_status);
- return;
- }
+void Coordinator::BackendState::ExecCompleteCb(
+ TypedCountingBarrier<Status>* exec_status_barrier, int64_t start_ms) {
+ {
+ lock_guard<mutex> l(lock_);
+ exec_rpc_status_ = exec_rpc_controller_.status();
+ rpc_latency_ = MonotonicMillis() - start_ms;
- ExecQueryFInstancesRequestPB request;
- TExecPlanFragmentInfo fragment_info;
- SetRpcParams(debug_options, filter_routing_table, &request, &fragment_info);
-
- RpcController rpc_controller;
- rpc_controller.set_timeout(
- MonoDelta::FromMilliseconds(FLAGS_backend_client_rpc_timeout_ms));
-
- // Serialize the sidecar and add it to the rpc controller. The serialized buffer is
- // owned by 'serializer' and is freed when it is destructed.
- ThriftSerializer serializer(true);
- uint8_t* serialized_buf = nullptr;
- uint32_t serialized_len = 0;
- Status serialize_status =
- serializer.SerializeToBuffer(&fragment_info, &serialized_len, &serialized_buf);
- if (UNLIKELY(!serialize_status.ok())) {
- SetExecError(serialize_status);
- return;
- } else if (serialized_len > FLAGS_rpc_max_message_size) {
- SetExecError(
- Status::Expected("Serialized Exec() request exceeds --rpc_max_message_size."));
- return;
- }
+ if (!exec_rpc_status_.ok()) {
+ SetExecError(
+ FromKuduStatus(exec_rpc_status_, "Exec() rpc failed"), exec_status_barrier);
+ goto done;
+ }
- // TODO: eliminate the extra copy here by using a Slice
- unique_ptr<kudu::faststring> sidecar_buf = make_unique<kudu::faststring>();
- sidecar_buf->assign_copy(serialized_buf, serialized_len);
- unique_ptr<RpcSidecar> rpc_sidecar = RpcSidecar::FromFaststring(move(sidecar_buf));
+ Status exec_status = Status(exec_response_.status());
+ if (!exec_status.ok()) {
+ SetExecError(exec_status, exec_status_barrier);
+ goto done;
+ }
- int sidecar_idx;
- kudu::Status sidecar_status =
- rpc_controller.AddOutboundSidecar(move(rpc_sidecar), &sidecar_idx);
- if (!sidecar_status.ok()) {
- SetExecError(FromKuduStatus(sidecar_status, "Failed to add sidecar"));
- return;
- }
- request.set_plan_fragment_info_sidecar_idx(sidecar_idx);
-
- // Add the serialized TQueryCtx as a sidecar.
- unique_ptr<RpcSidecar> query_ctx_sidecar = RpcSidecar::FromSlice(serialized_query_ctx);
- int query_ctx_sidecar_idx;
- kudu::Status query_ctx_sidecar_status =
- rpc_controller.AddOutboundSidecar(move(query_ctx_sidecar), &query_ctx_sidecar_idx);
- if (!query_ctx_sidecar_status.ok()) {
- SetExecError(
- FromKuduStatus(query_ctx_sidecar_status, "Failed to add TQueryCtx sidecar"));
- return;
+ for (const auto& entry : instance_stats_map_) entry.second->stopwatch_.Start();
+ VLOG_FILE << "rpc succeeded: ExecQueryFInstances query_id=" << PrintId(query_id_);
+ exec_done_ = true;
+ last_report_time_ms_ = GenerateReportTimestamp();
+ exec_status_barrier->Notify(Status::OK());
}
- request.set_query_ctx_sidecar_idx(query_ctx_sidecar_idx);
+done:
+ // Notify after releasing 'lock_' so that we don't wake up a thread just to have it
+ // immediately block again.
+ exec_done_cv_.NotifyAll();
+}
- VLOG_FILE << "making rpc: ExecQueryFInstances"
- << " host=" << TNetworkAddressToString(impalad_address()) << " query_id="
- << PrintId(query_id_);
+void Coordinator::BackendState::ExecAsync(const DebugOptions& debug_options,
+ const FilterRoutingTable& filter_routing_table,
+ const kudu::Slice& serialized_query_ctx,
+ TypedCountingBarrier<Status>* exec_status_barrier) {
+ {
+ lock_guard<mutex> l(lock_);
+ DCHECK(!exec_done_);
+ DCHECK(status_.ok());
+ // Do not issue an ExecQueryFInstances RPC if there are no fragment instances
+ // scheduled to run on this backend.
+ if (IsEmptyBackend()) {
+ DCHECK(backend_exec_params_->is_coord_backend);
+ exec_done_ = true;
+ exec_status_barrier->Notify(Status::OK());
+ goto done;
+ }
- // guard against concurrent UpdateBackendExecStatus() that may arrive after RPC returns
- lock_guard<mutex> l(lock_);
- int64_t start = MonotonicMillis();
+ std::unique_ptr<ControlServiceProxy> proxy;
+ Status get_proxy_status =
+ ControlService::GetProxy(krpc_host_, host_.hostname, &proxy);
+ if (!get_proxy_status.ok()) {
+ SetExecError(get_proxy_status, exec_status_barrier);
+ goto done;
+ }
- ExecQueryFInstancesResponsePB response;
- exec_rpc_status_ =
- FromKuduStatus(proxy->ExecQueryFInstances(request, &response, &rpc_controller),
- "Exec() rpc failed");
+ ExecQueryFInstancesRequestPB request;
+ TExecPlanFragmentInfo fragment_info;
+ SetRpcParams(debug_options, filter_routing_table, &request, &fragment_info);
+
+ exec_rpc_controller_.set_timeout(
+ MonoDelta::FromMilliseconds(FLAGS_backend_client_rpc_timeout_ms));
+
+ // Serialize the sidecar and add it to the rpc controller. The serialized buffer is
+ // owned by 'serializer' and is freed when it is destructed.
+ ThriftSerializer serializer(true);
+ uint8_t* serialized_buf = nullptr;
+ uint32_t serialized_len = 0;
+ Status serialize_status =
+ DebugAction(schedule_.query_options(), "EXEC_SERIALIZE_FRAGMENT_INFO");
+ if (LIKELY(serialize_status.ok())) {
+ serialize_status =
+ serializer.SerializeToBuffer(&fragment_info, &serialized_len, &serialized_buf);
+ }
+ if (UNLIKELY(!serialize_status.ok())) {
+ SetExecError(serialize_status, exec_status_barrier);
+ goto done;
+ } else if (serialized_len > FLAGS_rpc_max_message_size) {
+ SetExecError(
+ Status::Expected("Serialized Exec() request exceeds --rpc_max_message_size."),
+ exec_status_barrier);
+ goto done;
+ }
- rpc_sent_ = true;
- rpc_latency_ = MonotonicMillis() - start;
+ // TODO: eliminate the extra copy here by using a Slice
+ unique_ptr<kudu::faststring> sidecar_buf = make_unique<kudu::faststring>();
+ sidecar_buf->assign_copy(serialized_buf, serialized_len);
+ unique_ptr<RpcSidecar> rpc_sidecar = RpcSidecar::FromFaststring(move(sidecar_buf));
+
+ int sidecar_idx;
+ kudu::Status sidecar_status =
+ exec_rpc_controller_.AddOutboundSidecar(move(rpc_sidecar), &sidecar_idx);
+ if (!sidecar_status.ok()) {
+ SetExecError(
+ FromKuduStatus(sidecar_status, "Failed to add sidecar"), exec_status_barrier);
+ goto done;
+ }
+ request.set_plan_fragment_info_sidecar_idx(sidecar_idx);
+
+ // Add the serialized TQueryCtx as a sidecar.
+ unique_ptr<RpcSidecar> query_ctx_sidecar =
+ RpcSidecar::FromSlice(serialized_query_ctx);
+ int query_ctx_sidecar_idx;
+ kudu::Status query_ctx_sidecar_status = exec_rpc_controller_.AddOutboundSidecar(
+ move(query_ctx_sidecar), &query_ctx_sidecar_idx);
+ if (!query_ctx_sidecar_status.ok()) {
+ SetExecError(
+ FromKuduStatus(query_ctx_sidecar_status, "Failed to add TQueryCtx sidecar"),
+ exec_status_barrier);
+ goto done;
+ }
+ request.set_query_ctx_sidecar_idx(query_ctx_sidecar_idx);
- if (!exec_rpc_status_.ok()) {
- SetExecError(exec_rpc_status_);
- return;
- }
+ VLOG_FILE << "making rpc: ExecQueryFInstances"
+ << " host=" << TNetworkAddressToString(impalad_address())
+ << " query_id=" << PrintId(query_id_);
- Status exec_status = Status(response.status());
- if (!exec_status.ok()) {
- SetExecError(exec_status);
+ proxy->ExecQueryFInstancesAsync(request, &exec_response_, &exec_rpc_controller_,
+ std::bind(&Coordinator::BackendState::ExecCompleteCb, this, exec_status_barrier,
+ MonotonicMillis()));
+ exec_rpc_sent_ = true;
return;
}
-
- for (const auto& entry: instance_stats_map_) entry.second->stopwatch_.Start();
- VLOG_FILE << "rpc succeeded: ExecQueryFInstances query_id=" << PrintId(query_id_);
+done:
+ // Notify after releasing 'lock_' so that we don't wake up a thread just to have it
+ // immediately block again.
+ exec_done_cv_.NotifyAll();
}
Status Coordinator::BackendState::GetStatus(bool* is_fragment_failure,
@@ -296,6 +327,7 @@ Status Coordinator::BackendState::GetStatus(bool* is_fragment_failure,
Coordinator::ResourceUtilization Coordinator::BackendState::ComputeResourceUtilization() {
lock_guard<mutex> l(lock_);
+ DCHECK(exec_done_) << "May only be called after WaitOnExecRpc() completes.";
return ComputeResourceUtilizationLocked();
}
@@ -339,6 +371,7 @@ Coordinator::BackendState::ComputeResourceUtilizationLocked() {
void Coordinator::BackendState::MergeErrorLog(ErrorLogMap* merged) {
lock_guard<mutex> l(lock_);
+ DCHECK(exec_done_) << "May only be called after WaitOnExecRpc() completes.";
if (error_log_.size() > 0) MergeErrorMaps(error_log_, merged);
}
@@ -389,7 +422,12 @@ bool Coordinator::BackendState::ApplyExecStatusReport(
unique_lock<mutex> lock(lock_);
last_report_time_ms_ = GenerateReportTimestamp();
- // If this backend completed previously, don't apply the update.
+ // If this backend completed previously, don't apply the update. This ensures that
+ // the profile doesn't change during or after Coordinator::ComputeQuerySummary(), but
+ // can mean that we lose profile information for failed queries, since the Coordinator
+ // will call Cancel() on all BackendStates and we may stop accepting reports before some
+ // backends send their final report.
+ // TODO: revisit ComputeQuerySummary()
if (IsDoneLocked(lock)) return false;
// Use empty profile in case profile serialization/deserialization failed.
@@ -457,20 +495,6 @@ bool Coordinator::BackendState::ApplyExecStatusReport(
instance_stats->done_ = true;
--num_remaining_instances_;
}
-
- // TODO: clean up the ReportQuerySummary() mess
- if (status_.ok()) {
- // We can't update this backend's profile if ReportQuerySummary() is running,
- // because it depends on all profiles not changing during its execution (when it
- // calls SortChildren()). ReportQuerySummary() only gets called after
- // WaitForBackendCompletion() returns or at the end of CancelFragmentInstances().
- // WaitForBackendCompletion() only returns after all backends have completed (in
- // which case we wouldn't be in this function), or when there's an error, in which
- // case CancelFragmentInstances() is called. CancelFragmentInstances sets all
- // exec_state's statuses to cancelled.
- // TODO: We're losing this profile information. Call ReportQuerySummary only after
- // all backends have completed.
- }
}
// status_ has incorporated the status from all fragment instances. If the overall
@@ -491,6 +515,7 @@ bool Coordinator::BackendState::ApplyExecStatusReport(
void Coordinator::BackendState::UpdateHostProfile(
const TRuntimeProfileTree& thrift_profile) {
+ // We do not take 'lock_' here because RuntimeProfile::Update() is thread-safe.
DCHECK(!IsEmptyBackend());
host_profile_->Update(thrift_profile);
}
@@ -498,6 +523,7 @@ void Coordinator::BackendState::UpdateHostProfile(
void Coordinator::BackendState::UpdateExecStats(
const vector<FragmentStats*>& fragment_stats) {
lock_guard<mutex> l(lock_);
+ DCHECK(exec_done_) << "May only be called after WaitOnExecRpc() completes.";
for (const auto& entry: instance_stats_map_) {
const InstanceStats& instance_stats = *entry.second;
int fragment_idx = instance_stats.exec_params_.fragment().idx;
@@ -516,29 +542,46 @@ void Coordinator::BackendState::UpdateExecStats(
bool Coordinator::BackendState::Cancel() {
unique_lock<mutex> l(lock_);
- // Nothing to cancel if the exec rpc was not sent
- if (!rpc_sent_) return false;
+ // Nothing to cancel if the exec rpc was not sent.
+ if (!exec_rpc_sent_) {
+ if (status_.ok()) status_ = Status::CANCELLED;
+ VLogForBackend("Not sending Cancel() rpc because nothing was started.");
+ exec_done_ = true;
+ // Notify after releasing 'lock_' so that we don't wake up a thread just to have it
+ // immediately block again.
+ l.unlock();
+ exec_done_cv_.NotifyAll();
+ return false;
+ }
- // don't cancel if it already finished (for any reason)
- if (IsDoneLocked(l)) return false;
+ // If the exec rpc was sent but the callback hasn't been executed, try to cancel the rpc
+ // and then wait for it to be done.
+ if (!exec_done_) {
+ VLogForBackend("Attempting to cancel Exec() rpc");
+ exec_rpc_controller_.Cancel();
+ WaitOnExecLocked(&l);
+ }
- /// If the status is not OK, we still try to cancel - !OK status might mean
- /// communication failure between backend and coordinator, but fragment
- /// instances might still be running.
+ // Don't cancel if we're done. Note that its possible the backend is still running, eg.
+ // if the rpc layer reported that the Exec() rpc failed but it actually reached the
+ // backend. In that case, the backend will cancel itself the first time it tries to send
+ // a status report and the coordinator responds with an error.
+ if (IsDoneLocked(l)) {
+ VLogForBackend(Substitute(
+ "Not cancelling because the backend is already done: $0", status_.GetDetail()));
+ return false;
+ }
- // set an error status to make sure we only cancel this once
+ // Set an error status to make sure we only cancel this once.
if (status_.ok()) status_ = Status::CANCELLED;
- VLOG_QUERY << "Sending CancelQueryFInstances rpc for query_id=" << PrintId(query_id_)
- << " backend=" << TNetworkAddressToString(krpc_host_);
+ VLogForBackend("Sending CancelQueryFInstances rpc");
std::unique_ptr<ControlServiceProxy> proxy;
Status get_proxy_status = ControlService::GetProxy(krpc_host_, host_.hostname, &proxy);
if (!get_proxy_status.ok()) {
status_.MergeStatus(get_proxy_status);
- VLOG_QUERY << "Cancel query_id= " << PrintId(query_id_) << " could not get proxy to "
- << TNetworkAddressToString(krpc_host_)
- << " failure: " << get_proxy_status.msg().msg();
+ VLogForBackend(Substitute("Could not get proxy: $0", get_proxy_status.msg().msg()));
return true;
}
@@ -556,17 +599,15 @@ bool Coordinator::BackendState::Cancel() {
if (!rpc_status.ok()) {
status_.MergeStatus(rpc_status);
- VLOG_QUERY << "Cancel query_id= " << PrintId(query_id_) << " could not do rpc to "
- << TNetworkAddressToString(krpc_host_)
- << " failure: " << rpc_status.msg().msg();
+ VLogForBackend(
+ Substitute("CancelQueryFInstances rpc failed: $0", rpc_status.msg().msg()));
return true;
}
Status cancel_status = Status(response.status());
if (!cancel_status.ok()) {
status_.MergeStatus(cancel_status);
- VLOG_QUERY << "Cancel query_id= " << PrintId(query_id_)
- << " got failure after rpc to " << TNetworkAddressToString(krpc_host_)
- << " failure: " << cancel_status.msg().msg();
+ VLogForBackend(
+ Substitute("CancelQueryFInstances failed: $0", cancel_status.msg().msg()));
return true;
}
return true;
@@ -811,6 +852,7 @@ void Coordinator::FragmentStats::AddExecStats() {
void Coordinator::BackendState::ToJson(Value* value, Document* document) {
unique_lock<mutex> l(lock_);
+ DCHECK(exec_done_) << "May only be called after WaitOnExecRpc() completes.";
ResourceUtilization resource_utilization = ComputeResourceUtilizationLocked();
value->AddMember("num_instances", fragments_.size(), document->GetAllocator());
value->AddMember("done", IsDoneLocked(l), document->GetAllocator());
@@ -843,6 +885,7 @@ void Coordinator::BackendState::InstanceStatsToJson(Value* value, Document* docu
Value instance_stats(kArrayType);
{
lock_guard<mutex> l(lock_);
+ DCHECK(exec_done_) << "May only be called after WaitOnExecRpc() completes.";
for (const auto& elem : instance_stats_map_) {
Value val(kObjectType);
elem.second->ToJson(&val, document);
@@ -857,4 +900,9 @@ void Coordinator::BackendState::InstanceStatsToJson(Value* value, Document* docu
value->AddMember("host", val, document->GetAllocator());
}
+void Coordinator::BackendState::VLogForBackend(const string& msg) {
+ VLOG_QUERY << "query_id=" << PrintId(query_id_)
+ << " target backend=" << TNetworkAddressToString(krpc_host_) << ": " << msg;
+}
+
} // namespace impala
diff --git a/be/src/runtime/coordinator-backend-state.h b/be/src/runtime/coordinator-backend-state.h
index 1edad2f..bc51b87 100644
--- a/be/src/runtime/coordinator-backend-state.h
+++ b/be/src/runtime/coordinator-backend-state.h
@@ -47,7 +47,6 @@ namespace impala {
class ProgressUpdater;
class ObjectPool;
class DebugOptions;
-class CountingBarrier;
class ReportExecStatusRequestPB;
class TUniqueId;
class TQueryCtx;
@@ -57,13 +56,31 @@ struct FInstanceExecParams;
/// This class manages all aspects of the execution of all fragment instances of a
/// single query on a particular backend. For the coordinator backend its possible to have
/// no fragment instances scheduled on it. In that case, no RPCs are issued and the
-/// Backend state transitions to 'done' state right after Exec() is called on it.
-/// Thread-safe unless pointed out otherwise.
+/// Backend state transitions to 'done' state right after ExecAsync() is called on it.
+///
+/// Object Lifecycle/Thread Safety:
+/// - Init() must be called first followed by ExecAsync() and then WaitOnExecRpc().
+/// - Cancel() may be called at any time after Init(). After Cancel() is called, it is no
+/// longer valid to call ExecAsync().
+/// - After WaitOnExecRpc() has completed, all other functions are valid to call and
+// thread-safe.
+/// - 'lock_' is used to protect all members that may be read and modified concurrently,
+/// subject to the restrictions above on when methods may be called.
class Coordinator::BackendState {
public:
BackendState(const QuerySchedule& schedule, const TQueryCtx& query_ctx, int state_idx,
TRuntimeFilterMode::type filter_mode, const BackendExecParams& exec_params);
+ /// The following are initialized in the constructor and always valid to call.
+ int state_idx() const { return state_idx_; }
+ const BackendExecParams* exec_params() const { return backend_exec_params_; }
+ const TNetworkAddress& impalad_address() const { return host_; }
+ const TNetworkAddress& krpc_impalad_address() const { return krpc_host_; }
+ /// Returns true if there are no fragment instances scheduled on this backend.
+ bool IsEmptyBackend() const { return backend_exec_params_->instance_params.empty(); }
+ /// Return true if execution at this backend is done.
+ bool IsDone();
+
/// Creates InstanceStats for all instance in backend_exec_params in obj_pool
/// and installs the instance profiles as children of the corresponding FragmentStats'
/// root profile. Also creates a child profile below 'host_profile_parent' that contains
@@ -72,16 +89,34 @@ class Coordinator::BackendState {
void Init(const std::vector<FragmentStats*>& fragment_stats,
RuntimeProfile* host_profile_parent, ObjectPool* obj_pool);
- /// Starts query execution at this backend by issuing an ExecQueryFInstances rpc and
- /// notifies on rpc_complete_barrier when the rpc completes. Success/failure is
- /// communicated through GetStatus(). Uses filter_routing_table to remove filters
- /// that weren't selected during its construction.
+ /// Starts query execution at this backend by issuing an ExecQueryFInstances rpc
+ /// asynchronously and returns immediately. 'exec_status_barrier' is notified when the
+ /// rpc completes or when an error occurs. Success/failure is communicated through
+ /// GetStatus() after WaitOnExecRpc() returns.
+ /// Uses 'filter_routing_table' to remove filters that weren't selected during its
+ /// construction.
/// No RPC is issued if there are no fragment instances scheduled on this backend.
- /// The debug_options are applied to the appropriate TPlanFragmentInstanceCtxs, based
+ /// The 'debug_options' are applied to the appropriate TPlanFragmentInstanceCtxs, based
/// on their node_id/instance_idx.
- void Exec(const DebugOptions& debug_options,
+ void ExecAsync(const DebugOptions& debug_options,
const FilterRoutingTable& filter_routing_table,
- const kudu::Slice& serialized_query_ctx, CountingBarrier* rpc_complete_barrier);
+ const kudu::Slice& serialized_query_ctx,
+ TypedCountingBarrier<Status>* exec_status_barrier);
+
+ /// Waits until the ExecQueryFInstances() rpc has completed. May be called multiple
+ /// times and from different threads.
+ void WaitOnExecRpc();
+
+ /// Cancel execution at this backend if anything is running. Returns true if
+ /// cancellation was attempted, false otherwise.
+ ///
+ /// May be called at any time after Init(). If the ExecQueryFInstances() rpc is
+ /// inflight, will attempt to cancel the rpc. If ExecQueryFInstances() has already
+ /// completed or cancelling it is unsuccessful, sends the Cancel() rpc.
+ bool Cancel();
+
+ /////////////////////////////////////////
+ /// BEGIN: Functions that should only be called after WaitOnExecRpc() has returned.
/// Update overall execution status, including the instances' exec status/profiles
/// and the error log, if this backend is not already done. Updates the fragment
@@ -111,10 +146,6 @@ class Coordinator::BackendState {
void PublishFilterCompleteCb(const kudu::rpc::RpcController* rpc_controller,
FilterState* state, MemTracker* mem_tracker);
- /// Cancel execution at this backend if anything is running. Returns true
- /// if cancellation was attempted, false otherwise.
- bool Cancel();
-
/// Return the overall execution status. For an error status, the error could come
/// from the fragment instance level or it can be a general error from the backend
/// (with no specific fragment responsible). For a caller to distinguish between
@@ -129,10 +160,6 @@ class Coordinator::BackendState {
Status GetStatus(bool* is_fragment_failure = nullptr,
TUniqueId* failed_instance_id = nullptr) WARN_UNUSED_RESULT;
- /// Return true if execution at this backend is done. Thread-safe. Caller must not hold
- /// lock_.
- bool IsDone();
-
/// Return peak memory consumption and aggregated resource usage across all fragment
/// instances for this backend.
ResourceUtilization ComputeResourceUtilization();
@@ -148,26 +175,15 @@ class Coordinator::BackendState {
/// 'fragment_idxs'
bool HasFragmentIdx(const std::unordered_set<int>& fragment_idxs) const;
- const TNetworkAddress& impalad_address() const { return host_; }
- const TNetworkAddress& krpc_impalad_address() const { return krpc_host_; }
- int state_idx() const { return state_idx_; }
-
- /// Valid after Init().
- const BackendExecParams* exec_params() const { return backend_exec_params_; }
-
- /// Only valid after Exec().
int64_t rpc_latency() const { return rpc_latency_; }
- Status exec_rpc_status() const { return exec_rpc_status_; }
+ kudu::Status exec_rpc_status() const { return exec_rpc_status_; }
int64_t last_report_time_ms() {
std::lock_guard<std::mutex> l(lock_);
+ DCHECK(exec_done_) << "May only be called after WaitOnExecRpc() completes.";
return last_report_time_ms_;
}
- /// Print host/port info for the first backend that's still in progress as a
- /// debugging aid for backend deadlocks.
- static void LogFirstInProgress(std::vector<BackendState*> backend_states);
-
/// Serializes backend state to JSON by adding members to 'value', including total
/// number of instances, peak memory consumption, host and status amongst others.
void ToJson(rapidjson::Value* value, rapidjson::Document* doc);
@@ -176,12 +192,16 @@ class Coordinator::BackendState {
/// adding members to 'value', including the remote host name.
void InstanceStatsToJson(rapidjson::Value* value, rapidjson::Document* doc);
+ /// END: Functions that should only be called after WaitOnExecRpc() has returned.
+ /////////////////////////////////////////
+
+ /// Print host/port info for the first backend that's still in progress as a
+ /// debugging aid for backend deadlocks.
+ static void LogFirstInProgress(std::vector<BackendState*> backend_states);
+
/// Returns a timestamp using monotonic time for tracking arrival of status reports.
static int64_t GenerateReportTimestamp() { return MonotonicMillis(); }
- /// Returns True if there are no fragment instances scheduled on this backend.
- bool IsEmptyBackend() { return backend_exec_params_->instance_params.empty(); }
-
private:
/// Execution stats for a single fragment instance.
/// Not thread-safe.
@@ -293,11 +313,33 @@ class Coordinator::BackendState {
/// Krpc address of execution backend.
TNetworkAddress krpc_host_;
- /// protects fields below
- /// lock ordering: Coordinator::lock_ must only be obtained *prior* to lock_
+ /// The query context of the Coordinator that owns this BackendState.
+ const TQueryCtx& query_ctx_;
+
+ /// The query id of the Coordinator that owns this BackendState.
+ const TUniqueId& query_id_;
+
+ /// Used to issue the ExecQueryFInstances() rpc.
+ kudu::rpc::RpcController exec_rpc_controller_;
+
+ /// Response from ExecQueryFInstances().
+ ExecQueryFInstancesResponsePB exec_response_;
+
+ /// The status returned by KRPC for the ExecQueryFInstances() rpc. If this is an error,
+ /// we were unable to successfully communicate with the backend, eg. because of a
+ /// network error, or the rpc was cancelled by Cancel().
+ kudu::Status exec_rpc_status_;
+
+ /// Time, in ms, that it took to execute the ExecQueryFInstances() rpc.
+ int64_t rpc_latency_ = 0;
+
+ /////////////////////////////////////////
+ /// BEGIN: Members that are protected by 'lock_'.
+
+ /// Lock ordering: Coordinator::lock_ must only be obtained *prior* to lock_
std::mutex lock_;
- // number of in-flight instances
+ // Number of in-flight instances
int num_remaining_instances_ = 0;
/// If the status indicates an error status, execution has either been aborted by the
@@ -305,11 +347,6 @@ class Coordinator::BackendState {
/// initiated; either way, execution must not be cancelled.
Status status_;
- /// The status returned by KRPC for the ExecQueryFInstances() rpc. If this is an error,
- /// we were unable to successfully communicate with the backend, eg. because of a
- /// network error.
- Status exec_rpc_status_;
-
/// Used to distinguish between errors reported by a specific fragment instance,
/// which would set failed_instance_id_, rather than an error independent of any
/// specific fragment.
@@ -322,22 +359,23 @@ class Coordinator::BackendState {
/// Errors reported by this fragment instance.
ErrorLogMap error_log_;
- /// Time, in ms, that it took to execute the ExecRemoteFragment() RPC.
- int64_t rpc_latency_ = 0;
+ /// If true, ExecQueryFInstances() rpc has been sent.
+ bool exec_rpc_sent_ = false;
+
+ /// If true, any work related to Exec() is done. The usual case is that the
+ /// ExecQueryFInstances() rpc callback has been executed, but it may also be set to true
+ /// if Cancel() is called before Exec() or if no Exec() rpc needs to be sent.
+ bool exec_done_ = false;
- /// If true, ExecPlanFragment() rpc has been sent - even if it was not determined to be
- /// successful.
- bool rpc_sent_ = false;
+ /// Notified when the ExecQueryFInstances() rpc is completed.
+ ConditionVariable exec_done_cv_;
- /// Initialized in Init(), then set in each call to ApplyExecStatusReport().
+ /// Initialized in ExecCompleteCb(), then set in each call to ApplyExecStatusReport().
/// Uses GenerateReportTimeout().
int64_t last_report_time_ms_ = 0;
- /// The query context of the Coordinator that owns this BackendState.
- const TQueryCtx& query_ctx_;
-
- /// The query id of the Coordinator that owns this BackendState.
- const TUniqueId& query_id_;
+ /// END: Members that are protected by 'lock_'.
+ /////////////////////////////////////////
/// Fill in 'request' and 'fragment_info' based on state. Uses 'filter_routing_table' to
/// remove filters that weren't selected during its construction.
@@ -346,14 +384,26 @@ class Coordinator::BackendState {
ExecQueryFInstancesRequestPB* request, TExecPlanFragmentInfo* fragment_info);
/// Expects that 'status' is an error. Sets 'status_' to a formatted version of its
- /// message.
- void SetExecError(const Status& status);
+ /// message and notifies 'exec_status_barrier' with it. Caller must hold 'lock_'.
+ void SetExecError(
+ const Status& status, TypedCountingBarrier<Status>* exec_status_barrier);
+
+ /// Same as WaitOnExecRpc(), except 'l' must own 'lock_'.
+ void WaitOnExecLocked(std::unique_lock<std::mutex>* l);
+
+ /// Called when the ExecQueryFInstances() rpc completes. Notifies 'exec_status_barrier'
+ /// with the status. 'start' is the MonotonicMillis() timestamp when the rpc was sent.
+ void ExecCompleteCb(
+ TypedCountingBarrier<Status>* exec_status_barrier, int64_t start_ms);
/// Version of IsDone() where caller must hold lock_ via lock;
bool IsDoneLocked(const std::unique_lock<std::mutex>& lock) const;
/// Same as ComputeResourceUtilization() but caller must hold lock.
ResourceUtilization ComputeResourceUtilizationLocked();
+
+ /// Logs 'msg' at the VLOG_QUERY level, along with 'query_id_' and 'krpc_host_'.
+ void VLogForBackend(const std::string& msg);
};
/// Per fragment execution statistics.
diff --git a/be/src/runtime/coordinator.cc b/be/src/runtime/coordinator.cc
index 06bc265..567094c 100644
--- a/be/src/runtime/coordinator.cc
+++ b/be/src/runtime/coordinator.cc
@@ -50,6 +50,7 @@
#include "util/hdfs-bulk-ops.h"
#include "util/hdfs-util.h"
#include "util/histogram-metric.h"
+#include "util/kudu-status-util.h"
#include "util/min-max-filter.h"
#include "util/pretty-printer.h"
#include "util/table-printer.h"
@@ -119,7 +120,7 @@ Coordinator::Coordinator(ClientRequestState* parent, const QuerySchedule& schedu
filter_mode_(schedule.query_options().runtime_filter_mode),
obj_pool_(new ObjectPool()),
query_events_(events),
- exec_rpcs_complete_barrier_(schedule_.per_backend_exec_params().size()),
+ exec_rpcs_status_barrier_(schedule_.per_backend_exec_params().size()),
backend_released_barrier_(schedule_.per_backend_exec_params().size()),
filter_routing_table_(new FilterRoutingTable) {}
@@ -443,6 +444,14 @@ void Coordinator::AddFilterSource(const FragmentExecParams& src_fragment_params,
f->set_num_producers(src_idxs.size());
}
+void Coordinator::WaitOnExecRpcs() {
+ if (exec_rpcs_complete_.Load()) return;
+ for (BackendState* backend_state : backend_states_) {
+ backend_state->WaitOnExecRpc();
+ }
+ exec_rpcs_complete_.Store(true);
+}
+
Status Coordinator::StartBackendExec() {
int num_backends = backend_states_.size();
backend_exec_complete_barrier_.reset(new CountingBarrier(num_backends));
@@ -454,7 +463,7 @@ Status Coordinator::StartBackendExec() {
query_events_->MarkEvent(Substitute("Ready to start on $0 backends", num_backends));
// Serialize the TQueryCtx once and pass it to each backend. The serialized buffer must
- // stay valid until exec_rpcs_complete_barrier_ has been signalled.
+ // stay valid until WaitOnExecRpcs() has returned.
ThriftSerializer serializer(true);
uint8_t* serialized_buf = nullptr;
uint32_t serialized_len = 0;
@@ -466,21 +475,41 @@ Status Coordinator::StartBackendExec() {
kudu::Slice query_ctx_slice(serialized_buf, serialized_len);
for (BackendState* backend_state: backend_states_) {
- ExecEnv::GetInstance()->exec_rpc_thread_pool()->Offer(
- [backend_state, this, &debug_options, &query_ctx_slice]() {
- DebugActionNoFail(schedule_.query_options(), "COORD_BEFORE_EXEC_RPC");
- // Safe for Exec() to read 'filter_routing_table_' because it is complete
- // at this point and won't be destroyed while this function is executing,
- // because it won't be torn down until 'exec_rpcs_complete_barrier_' is
- // signalled.
- DCHECK(filter_mode_ == TRuntimeFilterMode::OFF
- || filter_routing_table_->is_complete);
- backend_state->Exec(debug_options, *filter_routing_table_, query_ctx_slice,
- &exec_rpcs_complete_barrier_);
- });
+ if (exec_rpcs_status_barrier_.pending() <= 0) {
+ // One of the backends has already indicated an error with Exec().
+ break;
+ }
+ DebugActionNoFail(schedule_.query_options(), "COORD_BEFORE_EXEC_RPC");
+ // Safe for ExecAsync() to read 'filter_routing_table_' because it is complete
+ // at this point and won't be destroyed while this function is executing,
+ // because it won't be torn down until WaitOnExecRpcs() has returned.
+ DCHECK(filter_mode_ == TRuntimeFilterMode::OFF || filter_routing_table_->is_complete);
+ backend_state->ExecAsync(debug_options, *filter_routing_table_, query_ctx_slice,
+ &exec_rpcs_status_barrier_);
+ }
+ Status exec_rpc_status = exec_rpcs_status_barrier_.Wait();
+ if (!exec_rpc_status.ok()) {
+ // One of the backends failed to startup, so we cancel the other ones.
+ CancelBackends();
+ WaitOnExecRpcs();
+ for (BackendState* backend_state : backend_states_) {
+ // If Exec() rpc failed for a reason besides being aborted, blacklist the executor.
+ if (!backend_state->exec_rpc_status().ok()
+ && !backend_state->exec_rpc_status().IsAborted()) {
+ LOG(INFO) << "Blacklisting "
+ << TNetworkAddressToString(backend_state->impalad_address())
+ << " because an Exec() rpc to it failed.";
+ const TBackendDescriptor& be_desc = backend_state->exec_params()->be_desc;
+ ExecEnv::GetInstance()->cluster_membership_mgr()->BlacklistExecutor(be_desc,
+ FromKuduStatus(backend_state->exec_rpc_status(), "Exec() rpc failed"));
+ }
+ }
+ VLOG_QUERY << "query startup cancelled due to a failed Exec() rpc: "
+ << exec_rpc_status;
+ return UpdateExecState(exec_rpc_status, nullptr, FLAGS_hostname);
}
- exec_rpcs_complete_barrier_.Wait();
+ WaitOnExecRpcs();
VLOG_QUERY << "started execution on " << num_backends << " backends for query_id="
<< PrintId(query_id());
query_events_->MarkEvent(
@@ -490,6 +519,7 @@ Status Coordinator::StartBackendExec() {
}
Status Coordinator::FinishBackendStartup() {
+ DCHECK(exec_rpcs_complete_.Load());
const TMetricDef& def =
MakeTMetricDef("backend-startup-latencies", TMetricKind::HISTOGRAM, TUnit::TIME_MS);
// Capture up to 30 minutes of start-up times, in ms, with 4 s.f. accuracy.
@@ -499,18 +529,14 @@ Status Coordinator::FinishBackendStartup() {
string max_latency_host;
int max_latency = 0;
for (BackendState* backend_state: backend_states_) {
+ // All of the Exec() rpcs must have completed successfully.
+ DCHECK(backend_state->exec_rpc_status().ok());
// preserve the first non-OK, if there is one
Status backend_status = backend_state->GetStatus();
if (!backend_status.ok() && status.ok()) {
status = backend_status;
error_hostname = backend_state->impalad_address().hostname;
}
- if (!backend_state->exec_rpc_status().ok()) {
- // The Exec() rpc failed, so blacklist the executor.
- const TBackendDescriptor& be_desc = backend_state->exec_params()->be_desc;
- ExecEnv::GetInstance()->cluster_membership_mgr()->BlacklistExecutor(
- be_desc, backend_state->exec_rpc_status());
- }
if (backend_state->rpc_latency() > max_latency) {
// Find the backend that takes the most time to acknowledge to
// the ExecQueryFInstances() RPC.
@@ -672,7 +698,7 @@ void Coordinator::HandleExecStateTransition(
// Can't transition until the exec RPCs are no longer in progress. Otherwise, a
// cancel RPC could be missed, and resources freed before a backend has had a chance
// to take a resource reference.
- DCHECK_LE(exec_rpcs_complete_barrier_.pending(), 0) << "exec rpcs not completed";
+ DCHECK(exec_rpcs_complete_.Load()) << "exec rpcs not completed";
query_events_->MarkEvent(exec_state_to_event.at(new_state));
// This thread won the race to transitioning into a terminal state - terminate
@@ -748,6 +774,7 @@ void Coordinator::WaitForBackends() {
}
Status Coordinator::Wait() {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
lock_guard<SpinLock> l(wait_lock_);
SCOPED_TIMER(query_profile_->total_time_counter());
if (has_called_wait_.Load()) return Status::OK();
@@ -817,7 +844,7 @@ Status Coordinator::GetNext(QueryResultSet* results, int max_rows, bool* eos,
void Coordinator::Cancel() {
// Illegal to call Cancel() before Exec() returns, so there's no danger of the cancel
// RPC passing the exec RPC.
- DCHECK_LE(exec_rpcs_complete_barrier_.pending(), 0) << "Exec() must be called first";
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
discard_result(SetNonErrorTerminalState(ExecState::CANCELLED));
// CancelBackends() is called for all transitions into a terminal state except
// for RETURNED_RESULTS. We need to call it now because after Cancel() is called
@@ -879,7 +906,9 @@ Status Coordinator::UpdateBackendExecStatus(const ReportExecStatusRequestPB& req
if (!status.ok()) {
// We may start receiving status reports before all exec rpcs are complete.
// Can't apply state transition until no more exec rpcs will be sent.
- exec_rpcs_complete_barrier_.Wait();
+ // TODO(IMPALA-6788): we should stop issuing ExecQueryFInstance rpcs and cancel any
+ // inflight when this happens.
+ WaitOnExecRpcs();
// Transition the status if we're not already in a terminal state. This won't block
// because either this transitions to an ERROR state or the query is already in
@@ -970,11 +999,7 @@ void Coordinator::UpdateBlacklistWithAuxErrorInfo(
}
int64_t Coordinator::GetMaxBackendStateLagMs(TNetworkAddress* address) {
- if (exec_rpcs_complete_barrier_.pending() > 0) {
- // Exec() hadn't completed for all the backends, so we can't rely on
- // 'last_report_time_ms_' being set yet.
- return 0;
- }
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first.";
DCHECK_GT(backend_states_.size(), 0);
int64_t current_time = BackendState::GenerateReportTimestamp();
int64_t min_last_report_time_ms = current_time;
@@ -995,6 +1020,7 @@ int64_t Coordinator::GetMaxBackendStateLagMs(TNetworkAddress* address) {
// TODO: add histogram/percentile
void Coordinator::ComputeQuerySummary() {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
// In this case, the query did not even get to start all fragment instances.
// Some of the state that is used below might be uninitialized. In this case,
// the query has made so little progress, reporting a summary is not very useful.
@@ -1067,6 +1093,7 @@ void Coordinator::ComputeQuerySummary() {
}
string Coordinator::GetErrorLog() {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
ErrorLogMap merged;
{
lock_guard<SpinLock> l(backend_states_init_lock_);
@@ -1094,6 +1121,7 @@ void Coordinator::ReleaseExecResources() {
}
void Coordinator::ReleaseQueryAdmissionControlResources() {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
vector<BackendState*> unreleased_backends =
backend_resource_state_->CloseAndGetUnreleasedBackends();
if (!unreleased_backends.empty()) {
@@ -1128,6 +1156,7 @@ void Coordinator::ReleaseBackendAdmissionControlResources(
}
Coordinator::ResourceUtilization Coordinator::ComputeQueryResourceUtilization() {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
ResourceUtilization query_resource_utilization;
for (BackendState* backend_state: backend_states_) {
query_resource_utilization.Merge(backend_state->ComputeResourceUtilization());
@@ -1158,7 +1187,7 @@ void Coordinator::UpdateFilter(const UpdateFilterParamsPB& params, RpcContext* c
DCHECK(backend_exec_complete_barrier_.get() != nullptr)
<< "Filters received before fragments started!";
- exec_rpcs_complete_barrier_.Wait();
+ WaitOnExecRpcs();
DCHECK(filter_routing_table_->is_complete)
<< "Filter received before routing table complete";
@@ -1233,7 +1262,7 @@ void Coordinator::UpdateFilter(const UpdateFilterParamsPB& params, RpcContext* c
TUniqueIdToUniqueIdPB(query_id(), rpc_params.mutable_dst_query_id());
rpc_params.set_filter_id(params.filter_id());
- // Waited for exec_rpcs_complete_barrier_ so backend_states_ is valid.
+ // Called WaitForExecRpcs() so backend_states_ is valid.
for (BackendState* bs : backend_states_) {
if (!IsExecuting()) {
if (rpc_params.has_bloom_filter()) {
@@ -1361,6 +1390,7 @@ MemTracker* Coordinator::query_mem_tracker() const {
}
void Coordinator::BackendsToJson(Document* doc) {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
Value states(kArrayType);
{
lock_guard<SpinLock> l(backend_states_init_lock_);
@@ -1374,6 +1404,7 @@ void Coordinator::BackendsToJson(Document* doc) {
}
void Coordinator::FInstanceStatsToJson(Document* doc) {
+ DCHECK(exec_rpcs_complete_.Load()) << "Exec() must be called first";
Value states(kArrayType);
{
lock_guard<SpinLock> l(backend_states_init_lock_);
diff --git a/be/src/runtime/coordinator.h b/be/src/runtime/coordinator.h
index 79e0d7f..55fc832 100644
--- a/be/src/runtime/coordinator.h
+++ b/be/src/runtime/coordinator.h
@@ -120,7 +120,8 @@ class Coordinator { // NOLINT: The member variables could be re-ordered to save
/// Blocks until result rows are ready to be retrieved via GetNext(), or, if the
/// query doesn't return rows, until the query finishes or is cancelled. A call to
/// Wait() must precede all calls to GetNext(). Multiple calls to Wait() are
- /// idempotent and it is okay to issue multiple Wait() calls concurrently.
+ /// idempotent and it is okay to issue multiple Wait() calls concurrently. Only valid to
+ /// call after Exec() returns successfully.
Status Wait() WARN_UNUSED_RESULT;
/// Fills 'results' with up to 'max_rows' rows. May return fewer than 'max_rows'
@@ -150,8 +151,9 @@ class Coordinator { // NOLINT: The member variables could be re-ordered to save
/// Returns the time in ms since the latest report was received for the backend which
/// has gone the longest without a report being received, and sets 'address' to the host
- /// for that backend. May return 0, for example if the backends are not initialized yet
- /// or if all of them have already completed, in which case 'address' will not be set.
+ /// for that backend. Only valid to call if Exec() has returned successfully. May return
+ /// 0, for example if all of the backends have already completed, in which case
+ /// 'address' will not be set.
int64_t GetMaxBackendStateLagMs(TNetworkAddress* address);
/// Get cumulative profile aggregated over all fragments of the query.
@@ -365,8 +367,12 @@ class Coordinator { // NOLINT: The member variables could be re-ordered to save
/// sequentially, without synchronization.
std::vector<FragmentStats*> fragment_stats_;
- /// Barrier that is released when all calls to BackendState::Exec() have returned.
- CountingBarrier exec_rpcs_complete_barrier_;
+ /// Barrier that is released when all backend Exec() rpcs have completed successfully,
+ /// or when one fails, in which case the returned value is the error from that rpc.
+ TypedCountingBarrier<Status> exec_rpcs_status_barrier_;
+
+ /// True if all Exec() rpcs have completed.
+ AtomicBool exec_rpcs_complete_{false};
/// Barrier that is released when all backends have indicated execution completion,
/// or when all backends are cancelled due to an execution error or client requested
@@ -479,6 +485,9 @@ class Coordinator { // NOLINT: The member variables could be re-ordered to save
/// but any calls must be made only after Exec().
void WaitForBackends();
+ /// Returns when all Exec() rpcs have completed. Thread-safe.
+ void WaitOnExecRpcs();
+
/// Initializes fragment_stats_ and query_profile_. Must be called before
/// InitBackendStates().
void InitFragmentStats();
diff --git a/be/src/runtime/exec-env.cc b/be/src/runtime/exec-env.cc
index d68c469..608a319 100644
--- a/be/src/runtime/exec-env.cc
+++ b/be/src/runtime/exec-env.cc
@@ -133,10 +133,6 @@ DECLARE_string(webserver_interface);
DECLARE_int32(webserver_port);
DECLARE_int64(tcmalloc_max_total_thread_cache_bytes);
-// TODO-MT: rename or retire
-DEFINE_int32(coordinator_rpc_threads, 12, "(Advanced) Number of threads available to "
- "start fragments on remote Impala daemons.");
-
DECLARE_string(ssl_client_ca_certificate);
DEFINE_int32(backend_client_connection_num_retries, 3, "Retry backend connections.");
@@ -279,8 +275,6 @@ ExecEnv::ExecEnv(int backend_port, int krpc_port,
if (FLAGS_is_coordinator) {
hdfs_op_thread_pool_.reset(
CreateHdfsOpThreadPool("hdfs-worker-pool", FLAGS_num_hdfs_worker_threads, 1024));
- exec_rpc_thread_pool_.reset(new CallableThreadPool("exec-rpc-pool", "worker",
- FLAGS_coordinator_rpc_threads, numeric_limits<int32_t>::max()));
scheduler_.reset(new Scheduler(metrics_.get(), request_pool_service_.get()));
}
@@ -308,7 +302,6 @@ Status ExecEnv::InitForFeTests() {
Status ExecEnv::Init() {
// Initialize thread pools
if (FLAGS_is_coordinator) {
- RETURN_IF_ERROR(exec_rpc_thread_pool_->Init());
RETURN_IF_ERROR(hdfs_op_thread_pool_->Init());
}
RETURN_IF_ERROR(async_rpc_pool_->Init());
diff --git a/be/src/runtime/exec-env.h b/be/src/runtime/exec-env.h
index c622ff0..b590cdd 100644
--- a/be/src/runtime/exec-env.h
+++ b/be/src/runtime/exec-env.h
@@ -130,7 +130,6 @@ class ExecEnv {
ThreadResourceMgr* thread_mgr() { return thread_mgr_.get(); }
HdfsOpThreadPool* hdfs_op_thread_pool() { return hdfs_op_thread_pool_.get(); }
TmpFileMgr* tmp_file_mgr() { return tmp_file_mgr_.get(); }
- CallableThreadPool* exec_rpc_thread_pool() { return exec_rpc_thread_pool_.get(); }
ImpalaServer* impala_server() { return impala_server_; }
Frontend* frontend() { return frontend_.get(); }
RequestPoolService* request_pool_service() { return request_pool_service_.get(); }
@@ -199,10 +198,6 @@ class ExecEnv {
boost::scoped_ptr<RequestPoolService> request_pool_service_;
boost::scoped_ptr<Frontend> frontend_;
- // Thread pool for the ExecQueryFInstances RPC. Only used by the coordinator, so it's
- // only started if FLAGS_is_coordinator is 'true'.
- boost::scoped_ptr<CallableThreadPool> exec_rpc_thread_pool_;
-
boost::scoped_ptr<CallableThreadPool> async_rpc_pool_;
boost::scoped_ptr<QueryExecMgr> query_exec_mgr_;
boost::scoped_ptr<RpcMgr> rpc_mgr_;
diff --git a/be/src/runtime/query-state.cc b/be/src/runtime/query-state.cc
index a0c6a30..432d43f 100644
--- a/be/src/runtime/query-state.cc
+++ b/be/src/runtime/query-state.cc
@@ -145,6 +145,8 @@ Status QueryState::Init(const ExecQueryFInstancesRequestPB* exec_rpc_params,
// returns a resource refcount to its caller.
AcquireBackendResourceRefcount();
+ RETURN_IF_ERROR(DebugAction(query_options(), "QUERY_STATE_INIT"));
+
ExecEnv* exec_env = ExecEnv::GetInstance();
// Initialize resource tracking counters.
diff --git a/be/src/util/counting-barrier.h b/be/src/util/counting-barrier.h
index c1bc805..99b1561 100644
--- a/be/src/util/counting-barrier.h
+++ b/be/src/util/counting-barrier.h
@@ -37,7 +37,7 @@ class TypedCountingBarrier {
/// 'promise_value'.
int32_t Notify(const T& promise_value) {
int32_t result = count_.Add(-1);
- if (result == 0) promise_.Set(promise_value);
+ if (result == 0) discard_result(promise_.Set(promise_value));
return result;
}
@@ -48,7 +48,7 @@ class TypedCountingBarrier {
int32_t value = count_.Load();
if (value <= 0) return; // count_ can legitimately drop below 0
if (count_.CompareAndSwap(value, 0)) {
- promise_.Set(promise_value);
+ discard_result(promise_.Set(promise_value));
return;
}
}
diff --git a/tests/custom_cluster/test_rpc_exception.py b/tests/custom_cluster/test_rpc_exception.py
index 495305b..d4701c5 100644
--- a/tests/custom_cluster/test_rpc_exception.py
+++ b/tests/custom_cluster/test_rpc_exception.py
@@ -16,14 +16,37 @@
# under the License.
import pytest
+import time
from tests.beeswax.impala_beeswax import ImpalaBeeswaxException
from tests.common.custom_cluster_test_suite import CustomClusterTestSuite
from tests.common.skip import SkipIf, SkipIfBuildType
+# The BE krpc port of the impalad these tests simulate rpc errors at.
+KRPC_PORT = 27002
+
+
+def _get_rpc_debug_action(rpc, action, port=KRPC_PORT):
+ """Returns a debug action that causes rpcs with the name 'rpc' that are sent to the
+ impalad at 'port' to execute the debug aciton 'action'."""
+ return "IMPALA_SERVICE_POOL:127.0.0.1:{port}:{rpc}:{action}" \
+ .format(rpc=rpc, port=port, action=action)
+
+
+def _get_fail_action(rpc, error=None, port=KRPC_PORT, p=0.1):
+ """Returns a debug action that causes rpcs with the name 'rpc' that are sent to the
+ impalad at 'port' to FAIL with probability 'p' and return 'error' if specified."""
+ action = "FAIL@%s" % p
+ if error is not None:
+ action += "@" + error
+ return _get_rpc_debug_action(rpc, action, port=port)
+
@SkipIfBuildType.not_dev_build
class TestRPCException(CustomClusterTestSuite):
"""Tests Impala exception handling in TransmitData() RPC to make sure no
duplicated row batches are sent. """
+ # ControlService rpc names
+ EXEC_RPC = "ExecQueryFInstances"
+
# DataStreamService rpc names
TRANSMIT_DATA_RPC = "TransmitData"
END_DATA_STREAM_RPC = "EndDataStream"
@@ -31,9 +54,6 @@ class TestRPCException(CustomClusterTestSuite):
# Error to specify for ImpalaServicePool to reject rpcs with a 'server too busy' error.
REJECT_TOO_BUSY_MSG = "REJECT_TOO_BUSY"
- # The BE krpc port of the impalad these tests simulate rpc errors at.
- KRPC_PORT = 27002
-
# This query ends up calling TransmitData() more than 2048 times to ensure
# proper test coverage.
TEST_QUERY = "select count(*) from tpch_parquet.lineitem t1, tpch_parquet.lineitem t2 \
@@ -62,7 +82,7 @@ class TestRPCException(CustomClusterTestSuite):
# the error 'exception_string'.
def execute_test_query(self, exception_string):
impalad = self.cluster.impalads[2]
- assert impalad.service.krpc_port == self.KRPC_PORT
+ assert impalad.service.krpc_port == KRPC_PORT
# Re-run the query until the metrics show that we hit the debug action or we've run 10
# times. Each test in this file has at least a 50% chance of hitting the action per
# run, so there's at most a (1/2)^10 chance that this loop will fail spuriously.
@@ -78,15 +98,6 @@ class TestRPCException(CustomClusterTestSuite):
assert exception_string in str(e), "Query failed with unexpected exception."
assert self._get_num_fails(impalad) > 0, "Debug action wasn't hit after 10 iters."
- def _get_fail_action(rpc, error=None, port=KRPC_PORT, p=0.1):
- """Returns a debug action that causes rpcs with the name 'rpc' that are sent to the
- impalad at 'port' to FAIL with probability 'p' and return 'error' if specified."""
- debug_action = "IMPALA_SERVICE_POOL:127.0.0.1:{port}:{rpc}:FAIL@{probability}" \
- .format(rpc=rpc, probability=p, port=port)
- if error is not None:
- debug_action += "@" + error
- return debug_action
-
@pytest.mark.execute_serially
@CustomClusterTestSuite.with_args("--debug_actions=" +
_get_fail_action(rpc=TRANSMIT_DATA_RPC, error=REJECT_TOO_BUSY_MSG))
@@ -120,3 +131,29 @@ class TestRPCException(CustomClusterTestSuite):
"""Run a query where EndDataStream may fail with a "server too busy" or with a generic
error. The query should either succeed or fail with the given error."""
self.execute_test_query("Debug Action: IMPALA_SERVICE_POOL:FAIL@0.5")
+
+ @pytest.mark.execute_serially
+ @CustomClusterTestSuite.with_args("--debug_actions=" +
+ _get_rpc_debug_action(rpc=EXEC_RPC, action="SLEEP@1000000"))
+ def test_exec_error(self):
+ """Test that verifies that when one Exec() rpc fails, the others are immediately
+ cancelled and the query returns an error quickly."""
+ # Debug action to cause Exec() rpcs to fail. The Exec() rpc to one of the impalads
+ # will sleep for a long time before hitting this (due to the impalad debug_actions
+ # startup flag specified above), so one Exec() will fail quickly while one will fail
+ # only after a long wait.
+ self.client.set_configuration_option("DEBUG_ACTION", "QUERY_STATE_INIT:FAIL")
+
+ start_s = time.time()
+ try:
+ self.client.execute(self.TEST_QUERY)
+ assert False, "query was expected to fail"
+ except ImpalaBeeswaxException as e:
+ assert "Debug Action: QUERY_STATE_INIT:FAIL" in str(e)
+
+ # If we successfully cancelled all Exec() rpcs and returned to the client as soon as
+ # the fast Exec() failed, the time to run the query should be much less than the sleep
+ # time for the slow Exec() of 1000s.
+ elapsed_s = time.time() - start_s
+ assert elapsed_s < 100, "Query took longer than expected to fail: %ss" % elapsed_s
+ self.client.set_configuration_option("DEBUG_ACTION", "")
diff --git a/tests/failure/test_failpoints.py b/tests/failure/test_failpoints.py
index 6d0a7db..7d6978c 100644
--- a/tests/failure/test_failpoints.py
+++ b/tests/failure/test_failpoints.py
@@ -145,6 +145,11 @@ class TestFailpoints(ImpalaTestSuite):
query_options={'debug_action': debug_action})
assert "Error during scheduling" in str(result)
+ # Fail Exec() in the coordinator.
+ debug_action = 'EXEC_SERIALIZE_FRAGMENT_INFO:FAIL@1.0'
+ self.execute_query_expect_failure(self.client, query,
+ query_options={'debug_action': debug_action})
+
# Fail the Prepare() phase of all fragment instances.
debug_action = 'FIS_IN_PREPARE:FAIL@1.0'
self.execute_query_expect_failure(self.client, query,
[impala] 04/04: IMPALA-9226: Bump ORC version to 1.6.2-p7
Posted by tm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
tmarshall pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git
commit f22812144279a3f722fcace5925cfb2f52efb598
Author: norbert.luksa <no...@cloudera.com>
AuthorDate: Tue Feb 25 09:36:18 2020 +0100
IMPALA-9226: Bump ORC version to 1.6.2-p7
Bump ORC version to include patch for ORC-600 that
unblocks IMPALA-9226.
Tests:
- Run scanner tests for orc/def/block.
Change-Id: I444bfac4111135e5b05eee1ff7c8cf6a32ff5b65
Reviewed-on: http://gerrit.cloudera.org:8080/15287
Reviewed-by: Gabor Kaszab <ga...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
bin/impala-config.sh | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/bin/impala-config.sh b/bin/impala-config.sh
index 3d08e27..86636fc 100755
--- a/bin/impala-config.sh
+++ b/bin/impala-config.sh
@@ -68,7 +68,7 @@ fi
# moving to a different build of the toolchain, e.g. when a version is bumped or a
# compile option is changed. The build id can be found in the output of the toolchain
# build jobs, it is constructed from the build number and toolchain git hash prefix.
-export IMPALA_TOOLCHAIN_BUILD_ID=144-6c12209540
+export IMPALA_TOOLCHAIN_BUILD_ID=150-22cf7d2029
# Versions of toolchain dependencies.
# -----------------------------------
export IMPALA_AVRO_VERSION=1.7.4-p5
@@ -129,7 +129,7 @@ export IMPALA_OPENLDAP_VERSION=2.4.47
unset IMPALA_OPENLDAP_URL
export IMPALA_OPENSSL_VERSION=1.0.2l
unset IMPALA_OPENSSL_URL
-export IMPALA_ORC_VERSION=1.6.2-p6
+export IMPALA_ORC_VERSION=1.6.2-p7
unset IMPALA_ORC_URL
export IMPALA_PROTOBUF_VERSION=3.5.1
unset IMPALA_PROTOBUF_URL
[impala] 02/04: IMPALA-8852: Skip short-circuit config check for
dedicated coordinator
Posted by tm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
tmarshall pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git
commit 777d0d203f138183d65885b523b619421b487714
Author: Tamas Mate <tm...@cloudera.com>
AuthorDate: Thu Feb 6 14:21:10 2020 +0100
IMPALA-8852: Skip short-circuit config check for dedicated coordinator
ImpalaD should not abort when running as dedicated coodinator and DataNode is
not available on the host. This change adds a condition to skip the short-
circuit socket path directory checks when ImpalaD is started with
'is_executor=false' flag.
Testing:
- Added test to JniFrontendTest.java to verify the short-circuit directory
check is skipped if ImpalaD is started as dedicated coordinator mode.
- Manually tested the appearance of the warning message with:
start-impala-cluster.py --num_coordinators 1 --use_exclusive_coordinators true
Change-Id: I373d4037f4cee203322a398b77b75810ba708bb5
Reviewed-on: http://gerrit.cloudera.org:8080/15173
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
be/src/util/backend-gflag-util.cc | 2 +
common/thrift/BackendGflags.thrift | 22 ++++---
.../org/apache/impala/service/BackendConfig.java | 4 ++
.../org/apache/impala/service/JniFrontend.java | 8 ++-
.../org/apache/impala/service/JniFrontendTest.java | 73 +++++++++++++++++++++-
5 files changed, 94 insertions(+), 15 deletions(-)
diff --git a/be/src/util/backend-gflag-util.cc b/be/src/util/backend-gflag-util.cc
index d04e344..f3e3755 100644
--- a/be/src/util/backend-gflag-util.cc
+++ b/be/src/util/backend-gflag-util.cc
@@ -77,6 +77,7 @@ DECLARE_bool(recursively_list_partitions);
DECLARE_string(query_event_hook_classes);
DECLARE_int32(query_event_hook_nthreads);
DECLARE_bool(is_executor);
+DECLARE_bool(is_coordinator);
DECLARE_bool(use_dedicated_coordinator_estimates);
DECLARE_string(blacklisted_dbs);
DECLARE_bool(unlock_zorder_sort);
@@ -165,6 +166,7 @@ Status GetThriftBackendGflags(JNIEnv* jni_env, jbyteArray* cfg_bytes) {
cfg.__set_query_event_hook_classes(FLAGS_query_event_hook_classes);
cfg.__set_query_event_hook_nthreads(FLAGS_query_event_hook_nthreads);
cfg.__set_is_executor(FLAGS_is_executor);
+ cfg.__set_is_coordinator(FLAGS_is_coordinator);
cfg.__set_use_dedicated_coordinator_estimates(
FLAGS_use_dedicated_coordinator_estimates);
cfg.__set_blacklisted_dbs(FLAGS_blacklisted_dbs);
diff --git a/common/thrift/BackendGflags.thrift b/common/thrift/BackendGflags.thrift
index 2498ecd..90fad1a 100644
--- a/common/thrift/BackendGflags.thrift
+++ b/common/thrift/BackendGflags.thrift
@@ -134,23 +134,25 @@ struct TBackendGflags {
55: required bool is_executor
- 56: required bool use_dedicated_coordinator_estimates
+ 56: required bool is_coordinator
- 57: required string blacklisted_dbs
+ 57: required bool use_dedicated_coordinator_estimates
- 58: required string blacklisted_tables
+ 58: required string blacklisted_dbs
- 59: required bool unlock_zorder_sort
+ 59: required string blacklisted_tables
- 60: required string min_privilege_set_for_show_stmts
+ 60: required bool unlock_zorder_sort
- 61: required bool mt_dop_auto_fallback
+ 61: required string min_privilege_set_for_show_stmts
- 62: required i32 num_expected_executors
+ 62: required bool mt_dop_auto_fallback
- 63: required i32 num_check_authorization_threads
+ 63: required i32 num_expected_executors
- 64: required bool use_customized_user_groups_mapper_for_ranger
+ 64: required i32 num_check_authorization_threads
- 65: required bool enable_column_masking
+ 65: required bool use_customized_user_groups_mapper_for_ranger
+
+ 66: required bool enable_column_masking
}
diff --git a/fe/src/main/java/org/apache/impala/service/BackendConfig.java b/fe/src/main/java/org/apache/impala/service/BackendConfig.java
index ac7f66b..c3957b9 100644
--- a/fe/src/main/java/org/apache/impala/service/BackendConfig.java
+++ b/fe/src/main/java/org/apache/impala/service/BackendConfig.java
@@ -230,4 +230,8 @@ public class BackendConfig {
KerberosName.setRules(defaultRule);
}
}
+
+ public boolean isDedicatedCoordinator() {
+ return (backendCfg_.is_executor == false) && (backendCfg_.is_coordinator == true);
+ }
}
diff --git a/fe/src/main/java/org/apache/impala/service/JniFrontend.java b/fe/src/main/java/org/apache/impala/service/JniFrontend.java
index f550956..2d47268 100644
--- a/fe/src/main/java/org/apache/impala/service/JniFrontend.java
+++ b/fe/src/main/java/org/apache/impala/service/JniFrontend.java
@@ -718,7 +718,8 @@ public class JniFrontend {
* Returns an error message if short circuit reads are enabled but misconfigured.
* Otherwise, returns an empty string,
*/
- private String checkShortCircuitRead(Configuration conf) {
+ @VisibleForTesting
+ protected static String checkShortCircuitRead(Configuration conf) {
if (!conf.getBoolean(DFSConfigKeys.DFS_CLIENT_READ_SHORTCIRCUIT_KEY,
DFSConfigKeys.DFS_CLIENT_READ_SHORTCIRCUIT_DEFAULT)) {
LOG.info("Short-circuit reads are not enabled.");
@@ -741,7 +742,10 @@ public class JniFrontend {
// The socket path parent directory must be readable and executable.
File socketFile = new File(domainSocketPath);
File socketDir = socketFile.getParentFile();
- if (socketDir == null || !socketDir.canRead() || !socketDir.canExecute()) {
+ if (BackendConfig.INSTANCE.isDedicatedCoordinator()) {
+ LOG.warn("Dedicated coordinator instance will not read local data via "
+ + "short-circuit reads, socket path directory checks are skipped.");
+ } else if (socketDir == null || !socketDir.canRead() || !socketDir.canExecute()) {
errorCause.append(prefix);
errorCause.append("Impala cannot read or execute the parent directory of ");
errorCause.append(DFSConfigKeys.DFS_DOMAIN_SOCKET_PATH_KEY);
diff --git a/fe/src/test/java/org/apache/impala/service/JniFrontendTest.java b/fe/src/test/java/org/apache/impala/service/JniFrontendTest.java
index b4f8dd8..26752d9 100644
--- a/fe/src/test/java/org/apache/impala/service/JniFrontendTest.java
+++ b/fe/src/test/java/org/apache/impala/service/JniFrontendTest.java
@@ -17,19 +17,45 @@
package org.apache.impala.service;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+
+import java.io.File;
+import java.util.Random;
+
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.CommonConfigurationKeys;
+import org.apache.hadoop.hdfs.DFSConfigKeys;
import org.apache.hadoop.security.JniBasedUnixGroupsMappingWithFallback;
import org.apache.hadoop.security.JniBasedUnixGroupsNetgroupMappingWithFallback;
import org.apache.hadoop.security.ShellBasedUnixGroupsMapping;
import org.apache.hadoop.security.ShellBasedUnixGroupsNetgroupMapping;
import org.apache.impala.common.ImpalaException;
+import org.apache.impala.thrift.TBackendGflags;
+import org.junit.AfterClass;
+import org.junit.BeforeClass;
import org.junit.Test;
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-
public class JniFrontendTest {
+ private static TBackendGflags origFlags;
+
+ @BeforeClass
+ public static void setup() {
+ // The original BackendConfig need to be mocked, we are saving the values here, so
+ // they can be restored and not break other tests
+ if (BackendConfig.INSTANCE == null) {
+ BackendConfig.create(new TBackendGflags());
+ }
+ origFlags = BackendConfig.INSTANCE.getBackendCfg();
+ }
+
+ @AfterClass
+ public static void teardown() {
+ BackendConfig.create(origFlags);
+ }
+
@Test
public void testCheckGroupsMappingProvider() throws ImpalaException {
Configuration conf = new Configuration();
@@ -55,4 +81,45 @@ public class JniFrontendTest {
ShellBasedUnixGroupsNetgroupMapping.class.getName(),
JniBasedUnixGroupsNetgroupMappingWithFallback.class.getName()));
}
+
+ /**
+ * This test verifies whether short-circuit socket path parent directory configurations
+ * are skipped for coordinator-only mode instances and checked for executors. A socket
+ * directory is created in order to mock the file access.
+ */
+ @Test
+ public void testCheckShortCircuitConfigs() {
+ String tmpDir = System.getProperty("java.io.tmpdir", "/tmp");
+ File socketDir = new File(tmpDir + "/socketTest",
+ "socks." + (System.currentTimeMillis() + "." + (new Random().nextInt())));
+ socketDir.mkdirs();
+ socketDir.getParentFile().setExecutable(false);
+
+ Configuration conf = mock(Configuration.class);
+ when(conf.getBoolean(DFSConfigKeys.DFS_CLIENT_READ_SHORTCIRCUIT_KEY,
+ DFSConfigKeys.DFS_CLIENT_READ_SHORTCIRCUIT_DEFAULT)).thenReturn(true);
+ when(conf.getTrimmed(DFSConfigKeys.DFS_DOMAIN_SOCKET_PATH_KEY,
+ DFSConfigKeys.DFS_DOMAIN_SOCKET_PATH_DEFAULT))
+ .thenReturn(socketDir.getAbsolutePath());
+ when(conf.getBoolean(DFSConfigKeys.DFS_CLIENT_USE_LEGACY_BLOCKREADERLOCAL,
+ DFSConfigKeys.DFS_CLIENT_USE_LEGACY_BLOCKREADERLOCAL_DEFAULT)).thenReturn(false);
+ BackendConfig.INSTANCE = mock(BackendConfig.class);
+
+ when(BackendConfig.INSTANCE.isDedicatedCoordinator()).thenReturn(true);
+ String actualErrorMessage = JniFrontend.checkShortCircuitRead(conf);
+ assertEquals("", actualErrorMessage);
+
+ when(BackendConfig.INSTANCE.isDedicatedCoordinator()).thenReturn(false);
+ actualErrorMessage = JniFrontend.checkShortCircuitRead(conf);
+ assertEquals("Invalid short-circuit reads configuration:\n"
+ + " - Impala cannot read or execute the parent directory of "
+ + DFSConfigKeys.DFS_DOMAIN_SOCKET_PATH_KEY + "\n",
+ actualErrorMessage);
+
+ if (socketDir != null) {
+ socketDir.getParentFile().setExecutable(true);
+ socketDir.delete();
+ socketDir.getParentFile().delete();
+ }
+ }
}
\ No newline at end of file
[impala] 01/04: IMPALA-9075: Add support for reading zstd text files
Posted by tm...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
tmarshall pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/impala.git
commit 571131fdc11acecf4c2003668dbccde0667efe07
Author: xiaomeng <xi...@cloudera.com>
AuthorDate: Tue Dec 10 14:39:45 2019 -0800
IMPALA-9075: Add support for reading zstd text files
In this patch, we add support for reading zstd encoded text files.
This includes:
1. support reading zstd file written by Hive which uses streaming.
2. support reading zstd file compressed by standard zstd library which
uses block.
To support decompressing both formats, a function ProcessBlockStreaming
is added in zstd decompressor.
Testing done:
Added two backend tests:
1. streaming decompress test.
2. large data test for both block and streaming decompress.
Added two end to end tests:
1. hive and impala integration. For four compression codecs, write in
hive and read from impala.
2. zstd library and impala integration. Copy a zstd lib compressed file
to HDFS, and read from impala.
Change-Id: I2adce9fe00190558525fa5cd3d50cf5e0f0b0aa4
Reviewed-on: http://gerrit.cloudera.org:8080/15023
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
be/src/exec/hdfs-text-scanner.cc | 1 +
be/src/exec/hdfs-text-scanner.h | 1 +
be/src/util/compress.h | 2 +-
be/src/util/decompress-test.cc | 37 +-
be/src/util/decompress.cc | 50 +-
be/src/util/decompress.h | 20 +-
bin/rat_exclude_files.txt | 2 +
testdata/data/text_large_zstd.txt | 10000000 ++++++++++++++++
testdata/data/text_large_zstd.zst | Bin 0 -> 3070087 bytes
.../custom_cluster/test_hive_text_codec_interop.py | 100 +
tests/query_test/test_compressed_formats.py | 71 +-
11 files changed, 10000275 insertions(+), 9 deletions(-)
diff --git a/be/src/exec/hdfs-text-scanner.cc b/be/src/exec/hdfs-text-scanner.cc
index ad43cda..03ac83e 100644
--- a/be/src/exec/hdfs-text-scanner.cc
+++ b/be/src/exec/hdfs-text-scanner.cc
@@ -89,6 +89,7 @@ Status HdfsTextScanner::IssueInitialRanges(HdfsScanNodeBase* scan_node,
case THdfsCompression::GZIP:
case THdfsCompression::SNAPPY:
case THdfsCompression::SNAPPY_BLOCKED:
+ case THdfsCompression::ZSTD:
case THdfsCompression::BZIP2:
case THdfsCompression::DEFLATE:
for (int j = 0; j < files[i]->splits.size(); ++j) {
diff --git a/be/src/exec/hdfs-text-scanner.h b/be/src/exec/hdfs-text-scanner.h
index 3ef4904..d507df1 100644
--- a/be/src/exec/hdfs-text-scanner.h
+++ b/be/src/exec/hdfs-text-scanner.h
@@ -73,6 +73,7 @@ class HdfsTextScanner : public HdfsScanner {
case THdfsCompression::GZIP:
case THdfsCompression::SNAPPY:
case THdfsCompression::SNAPPY_BLOCKED:
+ case THdfsCompression::ZSTD:
case THdfsCompression::BZIP2:
case THdfsCompression::DEFLATE:
return true;
diff --git a/be/src/util/compress.h b/be/src/util/compress.h
index c854a84..a9d3bbd 100644
--- a/be/src/util/compress.h
+++ b/be/src/util/compress.h
@@ -146,7 +146,7 @@ class ZstandardCompressor : public Codec {
virtual Status ProcessBlock(bool output_preallocated, int64_t input_length,
const uint8_t* input, int64_t* output_length,
uint8_t** output) override WARN_UNUSED_RESULT;
- virtual std::string file_extension() const override { return "zstd"; }
+ virtual std::string file_extension() const override { return "zst"; }
private:
int clevel_;
diff --git a/be/src/util/decompress-test.cc b/be/src/util/decompress-test.cc
index e3a22ec..f24eb7c 100644
--- a/be/src/util/decompress-test.cc
+++ b/be/src/util/decompress-test.cc
@@ -102,10 +102,10 @@ class DecompressorTest : public ::testing::Test {
decompressor->Close();
}
- void RunTestStreaming(THdfsCompression::type format) {
+ void RunTestStreaming(THdfsCompression::type format, int compression_level = 0) {
scoped_ptr<Codec> compressor;
scoped_ptr<Codec> decompressor;
- Codec::CodecInfo codec_info(format);
+ Codec::CodecInfo codec_info(format, compression_level);
EXPECT_OK(Codec::CreateCompressor(&mem_pool_, true, codec_info, &compressor));
EXPECT_OK(Codec::CreateDecompressor(&mem_pool_, true, format, &decompressor));
@@ -251,7 +251,17 @@ class DecompressorTest : public ::testing::Test {
int64_t input_len, uint8_t* input) {
uint8_t* compressed = NULL;
int64_t compressed_length = 0;
- Compress(compressor, input_len, input, &compressed_length, &compressed, false);
+ if (compressor->file_extension() == "zst") {
+ // Zstd compressor requires allocating memory first
+ if (input_len == 0)
+ compressed_length = 0;
+ else
+ compressed_length = compressor->MaxOutputLen(input_len, input);
+ compressed = mem_pool_.Allocate(compressed_length);
+ Compress(compressor, input_len, input, &compressed_length, &compressed, true);
+ } else {
+ Compress(compressor, input_len, input, &compressed_length, &compressed, false);
+ }
// If compressed_len is 0, there is nothing to decompress so should not expect
// "stream_end == true" either.
// Note the gzip compressor will generate some compressed data even if input == NULL
@@ -489,6 +499,27 @@ TEST_F(DecompressorTest, ZSTD) {
// zstd supports compression levels from 1 up to ZSTD_maxCLevel()
const int clevel = uniform_int_distribution<int>(1, ZSTD_maxCLevel())(rng);
RunTest(THdfsCompression::ZSTD, clevel);
+ RunTestStreaming(THdfsCompression::ZSTD, clevel);
+}
+
+TEST_F(DecompressorTest, ZSTDHuge) {
+ // As output buffer size is about 8M, we want to use an input buffer larger than that
+ // to test continuous stream reading
+ // Generate a big random payload, 100M length.
+ int payload_len = 100 * 1000 * 1000;
+ unique_ptr<uint8_t[]> payload(new uint8_t[payload_len]);
+ for (int i = 0; i < payload_len; ++i) payload[i] = rand();
+ scoped_ptr<Codec> compressor;
+ scoped_ptr<Codec> decompressor;
+
+ THdfsCompression::type format = THdfsCompression::ZSTD;
+ Codec::CodecInfo codec_info(format, ZSTD_CLEVEL_DEFAULT);
+ EXPECT_OK(Codec::CreateCompressor(&mem_pool_, true, codec_info, &compressor));
+ EXPECT_OK(Codec::CreateDecompressor(&mem_pool_, true, format, &decompressor));
+ CompressAndDecompressNoOutputAllocated(
+ compressor.get(), decompressor.get(), payload_len, payload.get());
+ CompressAndStreamingDecompress(
+ compressor.get(), decompressor.get(), payload_len, payload.get());
}
TEST_F(DecompressorTest, LZ4HadoopCompat) {
diff --git a/be/src/util/decompress.cc b/be/src/util/decompress.cc
index 3b81a6b..8d93409 100644
--- a/be/src/util/decompress.cc
+++ b/be/src/util/decompress.cc
@@ -614,7 +614,13 @@ Status Lz4Decompressor::ProcessBlock(bool output_preallocated, int64_t input_len
}
ZstandardDecompressor::ZstandardDecompressor(MemPool* mem_pool, bool reuse_buffer)
- : Codec(mem_pool, reuse_buffer) {}
+ : Codec(mem_pool, reuse_buffer, true) {}
+
+ZstandardDecompressor::~ZstandardDecompressor() {
+ if (stream_ != NULL) {
+ static_cast<void>(ZSTD_freeDCtx(stream_));
+ }
+}
int64_t ZstandardDecompressor::MaxOutputLen(int64_t input_len, const uint8_t* input) {
return -1;
@@ -634,6 +640,48 @@ Status ZstandardDecompressor::ProcessBlock(bool output_preallocated, int64_t inp
return Status::OK();
}
+Status ZstandardDecompressor::ProcessBlockStreaming(int64_t input_length,
+ const uint8_t* input, int64_t* input_bytes_read, int64_t* output_length,
+ uint8_t** output, bool* stream_end) {
+ if (!reuse_buffer_ || out_buffer_ == nullptr) {
+ buffer_length_ = STREAM_OUT_BUF_SIZE;
+ out_buffer_ = memory_pool_->TryAllocate(buffer_length_);
+ if (UNLIKELY(out_buffer_ == nullptr)) {
+ string details =
+ Substitute(DECOMPRESSOR_MEM_LIMIT_EXCEEDED, "Zstd", buffer_length_);
+ return memory_pool_->mem_tracker()->MemLimitExceeded(
+ nullptr, details, buffer_length_);
+ }
+ }
+ if (stream_ == NULL) {
+ stream_ = ZSTD_createDCtx();
+ if (stream_ == NULL) {
+ return Status(
+ TErrorCode::COMPRESSED_FILE_DECOMPRESSOR_ERROR, "Zstd", "ZSTD_createDCtx()");
+ }
+ }
+ *input_bytes_read = 0;
+ *output = out_buffer_;
+ *output_length = 0;
+
+ *stream_end = false;
+
+ ZSTD_inBuffer input_buffer{input, static_cast<size_t>(input_length), 0};
+ ZSTD_outBuffer output_buffer{*output, static_cast<size_t>(buffer_length_), 0};
+ while (input_buffer.pos < input_buffer.size && output_buffer.pos < output_buffer.size) {
+ size_t ret = ZSTD_decompressStream(stream_, &output_buffer, &input_buffer);
+ if (ZSTD_isError(ret)) {
+ *output_length = 0;
+ return Status(TErrorCode::ZSTD_ERROR, "ZSTD_decompressStream",
+ ZSTD_getErrorString(ZSTD_getErrorCode(ret)));
+ }
+ if (input_buffer.pos == input_buffer.size) *stream_end = true;
+ }
+ *input_bytes_read = input_buffer.pos;
+ *output_length = output_buffer.pos;
+ return Status::OK();
+}
+
Lz4BlockDecompressor::Lz4BlockDecompressor(MemPool* mem_pool, bool reuse_buffer)
: Codec(mem_pool, reuse_buffer) {
}
diff --git a/be/src/util/decompress.h b/be/src/util/decompress.h
index ee02b60..8227293 100644
--- a/be/src/util/decompress.h
+++ b/be/src/util/decompress.h
@@ -21,8 +21,9 @@
#include <string>
// We need zlib.h here to declare stream_ below.
-#include <zlib.h>
#include <bzlib.h>
+#include <zlib.h>
+#include <zstd.h>
#include "common/status.h"
#include "gutil/strings/substitute.h"
@@ -135,17 +136,30 @@ class SnappyBlockDecompressor : public Codec {
virtual std::string file_extension() const override { return "snappy"; }
};
+/// Zstandard is a real-time compression algorithm, providing high compression ratios.
+/// It offers a very wide range of compression/speed trade-off. This decompressor
+/// supports both block and streaming, while block decompress requires output buffer be
+/// pre-allocated.
class ZstandardDecompressor : public Codec {
public:
ZstandardDecompressor(MemPool* mem_pool, bool reuse_buffer);
- virtual ~ZstandardDecompressor() {}
+ virtual ~ZstandardDecompressor();
virtual int64_t MaxOutputLen(
int64_t input_len, const uint8_t* input = nullptr) override;
virtual Status ProcessBlock(bool output_preallocated, int64_t input_length,
const uint8_t* input, int64_t* output_length,
uint8_t** output) override WARN_UNUSED_RESULT;
- virtual std::string file_extension() const override { return "zstd"; }
+ /// File extension to use for this compression codec.
+ /// Except parquet which uses ".parq" as the file extension.
+ virtual std::string file_extension() const override { return "zst"; }
+ virtual Status ProcessBlockStreaming(int64_t input_length, const uint8_t* input,
+ int64_t* input_bytes_read, int64_t* output_length, uint8_t** output,
+ bool* stream_end) override WARN_UNUSED_RESULT;
+
+ private:
+ /// Allocate one context per thread, and re-use for many time decompression.
+ ZSTD_DCtx* stream_ = NULL;
};
/// Hadoop's block compression scheme on top of LZ4.
diff --git a/bin/rat_exclude_files.txt b/bin/rat_exclude_files.txt
index b992ad1..06a53fb 100644
--- a/bin/rat_exclude_files.txt
+++ b/bin/rat_exclude_files.txt
@@ -137,6 +137,8 @@ testdata/data/decimal_rtf_tbl.txt
testdata/data/overflow.txt
testdata/data/text-comma-backslash-newline.txt
testdata/data/text-dollar-hash-pipe.txt
+testdata/data/text_large_zstd.txt
+testdata/data/text_large_zstd.zst
testdata/data/widerow.txt
testdata/data/local_tbl/00000.txt
testdata/data/hudi_parquet/*
diff --git a/testdata/data/text_large_zstd.txt b/testdata/data/text_large_zstd.txt
new file mode 100644
index 0000000..8e95b81
--- /dev/null
+++ b/testdata/data/text_large_zstd.txt
@@ -0,0 +1,10000000 @@
+0
+1
+2
+3
+4
+5
+6
+7
+8
+9
+10
+11
+12
+13
+14
+15
+16
+17
+18
+19
+20
+21
+22
+23
+24
+25
+26
+27
+28
+29
+30
+31
+32
+33
+34
+35
+36
+37
+38
+39
+40
+41
+42
+43
+44
+45
+46
+47
+48
+49
+50
+51
+52
+53
+54
+55
+56
+57
+58
+59
+60
+61
+62
+63
+64
+65
+66
+67
+68
+69
+70
+71
+72
+73
+74
+75
+76
+77
+78
+79
+80
+81
+82
+83
+84
+85
+86
+87
+88
+89
+90
+91
+92
+93
+94
+95
+96
+97
+98
+99
+100
+101
+102
+103
+104
+105
+106
+107
+108
+109
+110
+111
+112
+113
+114
+115
+116
+117
+118
+119
+120
+121
+122
+123
+124
+125
+126
+127
+128
+129
+130
+131
+132
+133
+134
+135
+136
+137
+138
+139
+140
+141
+142
+143
+144
+145
+146
+147
+148
+149
+150
+151
+152
+153
+154
+155
+156
+157
+158
+159
+160
+161
+162
+163
+164
+165
+166
+167
+168
+169
+170
+171
+172
+173
+174
+175
+176
+177
+178
+179
+180
+181
+182
+183
+184
+185
+186
+187
+188
+189
+190
+191
+192
+193
+194
+195
+196
+197
+198
+199
+200
+201
+202
+203
+204
+205
+206
+207
+208
+209
+210
+211
+212
+213
+214
+215
+216
+217
+218
+219
+220
+221
+222
+223
+224
+225
+226
+227
+228
+229
+230
+231
+232
+233
+234
+235
+236
+237
+238
+239
+240
+241
+242
+243
+244
+245
+246
+247
+248
+249
+250
+251
+252
+253
+254
+255
+256
+257
+258
+259
+260
+261
+262
+263
+264
+265
+266
+267
+268
+269
+270
+271
+272
+273
+274
+275
+276
+277
+278
+279
+280
+281
+282
+283
+284
+285
+286
+287
+288
+289
+290
+291
+292
+293
+294
+295
+296
+297
+298
+299
+300
+301
+302
+303
+304
+305
+306
+307
+308
+309
+310
+311
+312
+313
+314
+315
+316
+317
+318
+319
+320
+321
+322
+323
+324
+325
+326
+327
+328
+329
+330
+331
+332
+333
+334
+335
+336
+337
+338
+339
+340
+341
+342
+343
+344
+345
+346
+347
+348
+349
+350
+351
+352
+353
+354
+355
+356
+357
+358
+359
+360
+361
+362
+363
+364
+365
+366
+367
+368
+369
+370
+371
+372
+373
+374
+375
+376
+377
+378
+379
+380
+381
+382
+383
+384
+385
+386
+387
+388
+389
+390
+391
+392
+393
+394
+395
+396
+397
+398
+399
+400
+401
+402
+403
+404
+405
+406
+407
+408
+409
+410
+411
+412
+413
+414
+415
+416
+417
+418
+419
+420
+421
+422
+423
+424
+425
+426
+427
+428
+429
+430
+431
+432
+433
+434
+435
+436
+437
+438
+439
+440
+441
+442
+443
+444
+445
+446
+447
+448
+449
+450
+451
+452
+453
+454
+455
+456
+457
+458
+459
+460
+461
+462
+463
+464
+465
+466
+467
+468
+469
+470
+471
+472
+473
+474
+475
+476
+477
+478
+479
+480
+481
+482
+483
+484
+485
+486
+487
+488
+489
+490
+491
+492
+493
+494
+495
+496
+497
+498
+499
+500
+501
+502
+503
+504
+505
+506
+507
+508
+509
+510
+511
+512
+513
+514
+515
+516
+517
+518
+519
+520
+521
+522
+523
+524
+525
+526
+527
+528
+529
+530
+531
+532
+533
+534
+535
+536
+537
+538
+539
+540
+541
+542
+543
+544
+545
+546
+547
+548
+549
+550
+551
+552
+553
+554
+555
+556
+557
+558
+559
+560
+561
+562
+563
+564
+565
+566
+567
+568
+569
+570
+571
+572
+573
+574
+575
+576
+577
+578
+579
+580
+581
+582
+583
+584
+585
+586
+587
+588
+589
+590
+591
+592
+593
+594
+595
+596
+597
+598
+599
+600
+601
+602
+603
+604
+605
+606
+607
+608
+609
+610
+611
+612
+613
+614
+615
+616
+617
+618
+619
+620
+621
+622
+623
+624
+625
+626
+627
+628
+629
+630
+631
+632
+633
+634
+635
+636
+637
+638
+639
+640
+641
+642
+643
+644
+645
+646
+647
+648
+649
+650
+651
+652
+653
+654
+655
+656
+657
+658
+659
+660
+661
+662
+663
+664
+665
+666
+667
+668
+669
+670
+671
+672
+673
+674
+675
+676
+677
+678
+679
+680
+681
+682
+683
+684
+685
+686
+687
+688
+689
+690
+691
+692
+693
+694
+695
+696
+697
+698
+699
+700
+701
+702
+703
+704
+705
+706
+707
+708
+709
+710
+711
+712
+713
+714
+715
+716
+717
+718
+719
+720
+721
+722
+723
+724
+725
+726
+727
+728
+729
+730
+731
+732
+733
+734
+735
+736
+737
+738
+739
+740
+741
+742
+743
+744
+745
+746
+747
+748
+749
+750
+751
+752
+753
+754
+755
+756
+757
+758
+759
+760
+761
+762
+763
+764
+765
+766
+767
+768
+769
+770
+771
+772
+773
+774
+775
+776
+777
+778
+779
+780
+781
+782
+783
+784
+785
+786
+787
+788
+789
+790
+791
+792
+793
+794
+795
+796
+797
+798
+799
+800
+801
+802
+803
+804
+805
+806
+807
+808
+809
+810
+811
+812
+813
+814
+815
+816
+817
+818
+819
+820
+821
+822
+823
+824
+825
+826
+827
+828
+829
+830
+831
+832
+833
+834
+835
+836
+837
+838
+839
+840
+841
+842
+843
+844
+845
+846
+847
+848
+849
+850
+851
+852
+853
+854
+855
+856
+857
+858
+859
+860
+861
+862
+863
+864
+865
+866
+867
+868
+869
+870
+871
+872
+873
+874
+875
+876
+877
+878
+879
+880
+881
+882
+883
+884
+885
+886
+887
+888
+889
+890
+891
+892
+893
+894
+895
+896
+897
+898
+899
+900
+901
+902
+903
+904
+905
+906
+907
+908
+909
+910
+911
+912
+913
+914
+915
+916
+917
+918
+919
+920
+921
+922
+923
+924
+925
+926
+927
+928
+929
+930
+931
+932
+933
+934
+935
+936
+937
+938
+939
+940
+941
+942
+943
+944
+945
+946
+947
+948
+949
+950
+951
+952
+953
+954
+955
+956
+957
+958
+959
+960
+961
+962
+963
+964
+965
+966
+967
+968
+969
+970
+971
+972
+973
+974
+975
+976
+977
+978
+979
+980
+981
+982
+983
+984
+985
+986
+987
+988
+989
+990
+991
+992
+993
+994
+995
+996
+997
+998
+999
+1000
+1001
+1002
+1003
+1004
+1005
+1006
+1007
+1008
+1009
+1010
+1011
+1012
+1013
+1014
+1015
+1016
+1017
+1018
+1019
+1020
+1021
+1022
+1023
+1024
+1025
+1026
+1027
+1028
+1029
+1030
+1031
+1032
+1033
+1034
+1035
+1036
+1037
+1038
+1039
+1040
+1041
+1042
+1043
+1044
+1045
+1046
+1047
+1048
+1049
+1050
+1051
+1052
+1053
+1054
+1055
+1056
+1057
+1058
+1059
+1060
+1061
+1062
+1063
+1064
+1065
+1066
+1067
+1068
+1069
+1070
+1071
+1072
+1073
+1074
+1075
+1076
+1077
+1078
+1079
+1080
+1081
+1082
+1083
+1084
+1085
+1086
+1087
+1088
+1089
+1090
+1091
+1092
+1093
+1094
+1095
+1096
+1097
+1098
+1099
+1100
+1101
+1102
+1103
+1104
+1105
+1106
+1107
+1108
+1109
+1110
+1111
+1112
+1113
+1114
+1115
+1116
+1117
+1118
+1119
+1120
+1121
+1122
+1123
+1124
+1125
+1126
+1127
+1128
+1129
+1130
+1131
+1132
+1133
+1134
+1135
+1136
+1137
+1138
+1139
+1140
+1141
+1142
+1143
+1144
+1145
+1146
+1147
+1148
+1149
+1150
+1151
+1152
+1153
+1154
+1155
+1156
+1157
+1158
+1159
+1160
+1161
+1162
+1163
+1164
+1165
+1166
+1167
+1168
+1169
+1170
+1171
+1172
+1173
+1174
+1175
+1176
+1177
+1178
+1179
+1180
+1181
+1182
+1183
+1184
+1185
+1186
+1187
+1188
+1189
+1190
+1191
+1192
+1193
+1194
+1195
+1196
+1197
+1198
+1199
+1200
+1201
+1202
+1203
+1204
+1205
+1206
+1207
+1208
+1209
+1210
+1211
+1212
+1213
+1214
+1215
+1216
+1217
+1218
+1219
+1220
+1221
+1222
+1223
+1224
+1225
+1226
+1227
+1228
+1229
+1230
+1231
+1232
+1233
+1234
+1235
+1236
+1237
+1238
+1239
+1240
+1241
+1242
+1243
+1244
+1245
+1246
+1247
+1248
+1249
+1250
+1251
+1252
+1253
+1254
+1255
+1256
+1257
+1258
+1259
+1260
+1261
+1262
+1263
+1264
+1265
+1266
+1267
+1268
+1269
+1270
+1271
+1272
+1273
+1274
+1275
+1276
+1277
+1278
+1279
+1280
+1281
+1282
+1283
+1284
+1285
+1286
+1287
+1288
+1289
+1290
+1291
+1292
+1293
+1294
+1295
+1296
+1297
+1298
+1299
+1300
+1301
+1302
+1303
+1304
+1305
+1306
+1307
+1308
+1309
+1310
+1311
+1312
+1313
+1314
+1315
+1316
+1317
+1318
+1319
+1320
+1321
+1322
+1323
+1324
+1325
+1326
+1327
+1328
+1329
+1330
+1331
+1332
+1333
+1334
+1335
+1336
+1337
+1338
+1339
+1340
+1341
+1342
+1343
+1344
+1345
+1346
+1347
+1348
+1349
+1350
+1351
+1352
+1353
+1354
+1355
+1356
+1357
+1358
+1359
+1360
+1361
+1362
+1363
+1364
+1365
+1366
+1367
+1368
+1369
+1370
+1371
+1372
+1373
+1374
+1375
+1376
+1377
+1378
+1379
+1380
+1381
+1382
+1383
+1384
+1385
+1386
+1387
+1388
+1389
+1390
+1391
+1392
+1393
+1394
+1395
+1396
+1397
+1398
+1399
+1400
+1401
+1402
+1403
+1404
+1405
+1406
+1407
+1408
+1409
+1410
+1411
+1412
+1413
+1414
+1415
+1416
+1417
+1418
+1419
+1420
+1421
+1422
+1423
+1424
+1425
+1426
+1427
+1428
+1429
+1430
+1431
+1432
+1433
+1434
+1435
+1436
+1437
+1438
+1439
+1440
+1441
+1442
+1443
+1444
+1445
+1446
+1447
+1448
+1449
+1450
+1451
+1452
+1453
+1454
+1455
+1456
+1457
+1458
+1459
+1460
+1461
+1462
+1463
+1464
+1465
+1466
+1467
+1468
+1469
+1470
+1471
+1472
+1473
+1474
+1475
+1476
+1477
+1478
+1479
+1480
+1481
+1482
+1483
+1484
+1485
+1486
+1487
+1488
+1489
+1490
+1491
+1492
+1493
+1494
+1495
+1496
+1497
+1498
+1499
+1500
+1501
+1502
+1503
+1504
+1505
+1506
+1507
+1508
+1509
+1510
+1511
+1512
+1513
+1514
+1515
+1516
+1517
+1518
+1519
+1520
+1521
+1522
+1523
+1524
+1525
+1526
+1527
+1528
+1529
+1530
+1531
+1532
+1533
+1534
+1535
+1536
+1537
+1538
+1539
+1540
+1541
+1542
+1543
+1544
+1545
+1546
+1547
+1548
+1549
+1550
+1551
+1552
+1553
+1554
+1555
+1556
+1557
+1558
+1559
+1560
+1561
+1562
+1563
+1564
+1565
+1566
+1567
+1568
+1569
+1570
+1571
+1572
+1573
+1574
+1575
+1576
+1577
+1578
+1579
+1580
+1581
+1582
+1583
+1584
+1585
+1586
+1587
+1588
+1589
+1590
+1591
+1592
+1593
+1594
+1595
+1596
+1597
+1598
+1599
+1600
+1601
+1602
+1603
+1604
+1605
+1606
+1607
+1608
+1609
+1610
+1611
+1612
+1613
+1614
+1615
+1616
+1617
+1618
+1619
+1620
+1621
+1622
+1623
+1624
+1625
+1626
+1627
+1628
+1629
+1630
+1631
+1632
+1633
+1634
+1635
+1636
+1637
+1638
+1639
+1640
+1641
+1642
+1643
+1644
+1645
+1646
+1647
+1648
+1649
+1650
+1651
+1652
+1653
+1654
+1655
+1656
+1657
+1658
+1659
+1660
+1661
+1662
+1663
+1664
+1665
+1666
+1667
+1668
+1669
+1670
+1671
+1672
+1673
+1674
+1675
+1676
+1677
+1678
+1679
+1680
+1681
+1682
+1683
+1684
+1685
+1686
+1687
+1688
+1689
+1690
+1691
+1692
+1693
+1694
+1695
+1696
+1697
+1698
+1699
+1700
+1701
+1702
+1703
+1704
+1705
+1706
+1707
+1708
+1709
+1710
+1711
+1712
+1713
+1714
+1715
+1716
+1717
+1718
+1719
+1720
+1721
+1722
+1723
+1724
+1725
+1726
+1727
+1728
+1729
+1730
+1731
+1732
+1733
+1734
+1735
+1736
+1737
+1738
+1739
+1740
+1741
+1742
+1743
+1744
+1745
+1746
+1747
+1748
+1749
+1750
+1751
+1752
+1753
+1754
+1755
+1756
+1757
+1758
+1759
+1760
+1761
+1762
+1763
+1764
+1765
+1766
+1767
+1768
+1769
+1770
+1771
+1772
+1773
+1774
+1775
+1776
+1777
+1778
+1779
+1780
+1781
+1782
+1783
+1784
+1785
+1786
+1787
+1788
+1789
+1790
+1791
+1792
+1793
+1794
+1795
+1796
+1797
+1798
+1799
+1800
+1801
+1802
+1803
+1804
+1805
+1806
+1807
+1808
+1809
+1810
+1811
+1812
+1813
+1814
+1815
+1816
+1817
+1818
+1819
+1820
+1821
+1822
+1823
+1824
+1825
+1826
+1827
+1828
+1829
+1830
+1831
+1832
+1833
+1834
+1835
+1836
+1837
+1838
+1839
+1840
+1841
+1842
+1843
+1844
+1845
+1846
+1847
+1848
+1849
+1850
+1851
+1852
+1853
+1854
+1855
+1856
+1857
+1858
+1859
+1860
+1861
+1862
+1863
+1864
+1865
+1866
+1867
+1868
+1869
+1870
+1871
+1872
+1873
+1874
+1875
+1876
+1877
+1878
+1879
+1880
+1881
+1882
+1883
+1884
+1885
+1886
+1887
+1888
+1889
+1890
+1891
+1892
+1893
+1894
+1895
+1896
+1897
+1898
+1899
+1900
+1901
+1902
+1903
+1904
+1905
+1906
+1907
+1908
+1909
+1910
+1911
+1912
+1913
+1914
+1915
+1916
+1917
+1918
+1919
+1920
+1921
+1922
+1923
+1924
+1925
+1926
+1927
+1928
+1929
+1930
+1931
+1932
+1933
+1934
+1935
+1936
+1937
+1938
+1939
+1940
+1941
+1942
+1943
+1944
+1945
+1946
+1947
+1948
+1949
+1950
+1951
+1952
+1953
+1954
+1955
+1956
+1957
+1958
+1959
+1960
+1961
+1962
+1963
+1964
+1965
+1966
+1967
+1968
+1969
+1970
+1971
+1972
+1973
+1974
+1975
+1976
+1977
+1978
+1979
+1980
+1981
+1982
+1983
+1984
+1985
+1986
+1987
+1988
+1989
+1990
+1991
+1992
+1993
+1994
+1995
+1996
+1997
+1998
+1999
+2000
+2001
+2002
+2003
+2004
+2005
+2006
+2007
+2008
+2009
+2010
+2011
+2012
+2013
+2014
+2015
+2016
+2017
+2018
+2019
+2020
+2021
+2022
+2023
+2024
+2025
+2026
+2027
+2028
+2029
+2030
+2031
+2032
+2033
+2034
+2035
+2036
+2037
+2038
+2039
+2040
+2041
+2042
+2043
+2044
+2045
+2046
+2047
+2048
+2049
+2050
+2051
+2052
+2053
+2054
+2055
+2056
+2057
+2058
+2059
+2060
+2061
+2062
+2063
+2064
+2065
+2066
+2067
+2068
+2069
+2070
+2071
+2072
+2073
+2074
+2075
+2076
+2077
+2078
+2079
+2080
+2081
+2082
+2083
+2084
+2085
+2086
+2087
+2088
+2089
+2090
+2091
+2092
+2093
+2094
+2095
+2096
+2097
+2098
+2099
+2100
+2101
+2102
+2103
+2104
+2105
+2106
+2107
+2108
+2109
+2110
+2111
+2112
+2113
+2114
+2115
+2116
+2117
+2118
+2119
+2120
+2121
+2122
+2123
+2124
+2125
+2126
+2127
+2128
+2129
+2130
+2131
+2132
+2133
+2134
+2135
+2136
+2137
+2138
+2139
+2140
+2141
+2142
+2143
+2144
+2145
+2146
+2147
+2148
+2149
+2150
+2151
+2152
+2153
+2154
+2155
+2156
+2157
+2158
+2159
+2160
+2161
+2162
+2163
+2164
+2165
+2166
+2167
+2168
+2169
+2170
+2171
+2172
+2173
+2174
+2175
+2176
+2177
+2178
+2179
+2180
+2181
+2182
+2183
+2184
+2185
+2186
+2187
+2188
+2189
+2190
+2191
+2192
+2193
+2194
+2195
+2196
+2197
+2198
+2199
+2200
+2201
+2202
+2203
+2204
+2205
+2206
+2207
+2208
+2209
+2210
+2211
+2212
+2213
+2214
+2215
+2216
+2217
+2218
+2219
+2220
+2221
+2222
+2223
+2224
+2225
+2226
+2227
+2228
+2229
+2230
+2231
+2232
+2233
+2234
+2235
+2236
+2237
+2238
+2239
+2240
+2241
+2242
+2243
+2244
+2245
+2246
+2247
+2248
+2249
+2250
+2251
+2252
+2253
+2254
+2255
+2256
+2257
+2258
+2259
+2260
+2261
+2262
+2263
+2264
+2265
+2266
+2267
+2268
+2269
+2270
+2271
+2272
+2273
+2274
+2275
+2276
+2277
+2278
+2279
+2280
+2281
+2282
+2283
+2284
+2285
+2286
+2287
+2288
+2289
+2290
+2291
+2292
+2293
+2294
+2295
+2296
+2297
+2298
+2299
+2300
+2301
+2302
+2303
+2304
+2305
+2306
+2307
+2308
+2309
+2310
+2311
+2312
+2313
+2314
+2315
+2316
+2317
+2318
+2319
+2320
+2321
+2322
+2323
+2324
+2325
+2326
+2327
+2328
+2329
+2330
+2331
+2332
+2333
+2334
+2335
+2336
+2337
+2338
+2339
+2340
+2341
+2342
+2343
+2344
+2345
+2346
+2347
+2348
+2349
+2350
+2351
+2352
+2353
+2354
+2355
+2356
+2357
+2358
+2359
+2360
+2361
+2362
+2363
+2364
+2365
+2366
+2367
+2368
+2369
+2370
+2371
+2372
+2373
+2374
+2375
+2376
+2377
+2378
+2379
+2380
+2381
+2382
+2383
+2384
+2385
+2386
+2387
+2388
+2389
+2390
+2391
+2392
+2393
+2394
+2395
+2396
+2397
+2398
+2399
+2400
+2401
+2402
+2403
+2404
+2405
+2406
+2407
+2408
+2409
+2410
+2411
+2412
+2413
+2414
+2415
+2416
+2417
+2418
+2419
+2420
+2421
+2422
+2423
+2424
+2425
+2426
+2427
+2428
+2429
+2430
+2431
+2432
+2433
+2434
+2435
+2436
+2437
+2438
+2439
+2440
+2441
+2442
+2443
+2444
+2445
+2446
+2447
+2448
+2449
+2450
+2451
+2452
+2453
+2454
+2455
+2456
+2457
+2458
+2459
+2460
+2461
+2462
+2463
+2464
+2465
+2466
+2467
+2468
+2469
+2470
+2471
+2472
+2473
+2474
+2475
+2476
+2477
+2478
+2479
+2480
+2481
+2482
+2483
+2484
+2485
+2486
+2487
+2488
+2489
+2490
+2491
+2492
+2493
+2494
+2495
+2496
+2497
+2498
+2499
+2500
+2501
+2502
+2503
+2504
+2505
+2506
+2507
+2508
+2509
+2510
+2511
+2512
+2513
+2514
+2515
+2516
+2517
+2518
+2519
+2520
+2521
+2522
+2523
+2524
+2525
+2526
+2527
+2528
+2529
+2530
+2531
+2532
+2533
+2534
+2535
+2536
+2537
+2538
+2539
+2540
+2541
+2542
+2543
+2544
+2545
+2546
+2547
+2548
+2549
+2550
+2551
+2552
+2553
+2554
+2555
+2556
+2557
+2558
+2559
+2560
+2561
+2562
+2563
+2564
+2565
+2566
+2567
+2568
+2569
+2570
+2571
+2572
+2573
+2574
+2575
+2576
+2577
+2578
+2579
+2580
+2581
+2582
+2583
+2584
+2585
+2586
+2587
+2588
+2589
+2590
+2591
+2592
+2593
+2594
+2595
+2596
+2597
+2598
+2599
+2600
+2601
+2602
+2603
+2604
+2605
+2606
+2607
+2608
+2609
+2610
+2611
+2612
+2613
+2614
+2615
+2616
+2617
+2618
+2619
+2620
+2621
+2622
+2623
+2624
+2625
+2626
+2627
+2628
+2629
+2630
+2631
+2632
+2633
+2634
+2635
+2636
+2637
+2638
+2639
+2640
+2641
+2642
+2643
+2644
+2645
+2646
+2647
+2648
+2649
+2650
+2651
+2652
+2653
+2654
+2655
+2656
+2657
+2658
+2659
+2660
+2661
+2662
+2663
+2664
+2665
+2666
+2667
+2668
+2669
+2670
+2671
+2672
+2673
+2674
+2675
+2676
+2677
+2678
+2679
+2680
+2681
+2682
+2683
+2684
+2685
+2686
+2687
+2688
+2689
+2690
+2691
+2692
+2693
+2694
+2695
+2696
+2697
+2698
+2699
+2700
+2701
+2702
+2703
+2704
+2705
+2706
+2707
+2708
+2709
+2710
+2711
+2712
+2713
+2714
+2715
+2716
+2717
+2718
+2719
+2720
+2721
+2722
+2723
+2724
+2725
+2726
+2727
+2728
+2729
+2730
+2731
+2732
+2733
+2734
+2735
+2736
+2737
+2738
+2739
+2740
+2741
+2742
+2743
+2744
+2745
+2746
+2747
+2748
+2749
+2750
+2751
+2752
+2753
+2754
+2755
+2756
+2757
+2758
+2759
+2760
+2761
+2762
+2763
+2764
+2765
+2766
+2767
+2768
+2769
+2770
+2771
+2772
+2773
+2774
+2775
+2776
+2777
+2778
+2779
+2780
+2781
+2782
+2783
+2784
+2785
+2786
+2787
+2788
+2789
+2790
+2791
+2792
+2793
+2794
+2795
+2796
+2797
+2798
+2799
+2800
+2801
+2802
+2803
+2804
+2805
+2806
+2807
+2808
+2809
+2810
+2811
+2812
+2813
+2814
+2815
+2816
+2817
+2818
+2819
+2820
+2821
+2822
+2823
+2824
+2825
+2826
+2827
+2828
+2829
+2830
+2831
+2832
+2833
+2834
+2835
+2836
+2837
+2838
+2839
+2840
+2841
+2842
+2843
+2844
+2845
+2846
+2847
+2848
+2849
+2850
+2851
+2852
+2853
+2854
+2855
+2856
+2857
+2858
+2859
+2860
+2861
+2862
+2863
+2864
+2865
+2866
+2867
+2868
+2869
+2870
+2871
+2872
+2873
+2874
+2875
+2876
+2877
+2878
+2879
+2880
+2881
+2882
+2883
+2884
+2885
+2886
+2887
+2888
+2889
+2890
+2891
+2892
+2893
+2894
+2895
+2896
+2897
+2898
+2899
+2900
+2901
+2902
+2903
+2904
+2905
+2906
+2907
+2908
+2909
+2910
+2911
+2912
+2913
+2914
+2915
+2916
+2917
+2918
+2919
+2920
+2921
+2922
+2923
+2924
+2925
+2926
+2927
+2928
+2929
+2930
+2931
+2932
+2933
+2934
+2935
+2936
+2937
+2938
+2939
+2940
+2941
+2942
+2943
+2944
+2945
+2946
+2947
+2948
+2949
+2950
+2951
+2952
+2953
+2954
+2955
+2956
+2957
+2958
+2959
+2960
+2961
+2962
+2963
+2964
+2965
+2966
+2967
+2968
+2969
+2970
+2971
+2972
+2973
+2974
+2975
+2976
+2977
+2978
+2979
+2980
+2981
+2982
+2983
+2984
+2985
+2986
+2987
+2988
+2989
+2990
+2991
+2992
+2993
+2994
+2995
+2996
+2997
+2998
+2999
+3000
+3001
+3002
+3003
+3004
+3005
+3006
+3007
+3008
+3009
+3010
+3011
+3012
+3013
+3014
+3015
+3016
+3017
+3018
+3019
+3020
+3021
+3022
+3023
+3024
+3025
+3026
+3027
+3028
+3029
+3030
+3031
+3032
+3033
+3034
+3035
+3036
+3037
+3038
+3039
+3040
+3041
+3042
+3043
+3044
+3045
+3046
+3047
+3048
+3049
+3050
+3051
+3052
+3053
+3054
+3055
+3056
+3057
+3058
+3059
+3060
+3061
+3062
+3063
+3064
+3065
+3066
+3067
+3068
+3069
+3070
+3071
+3072
+3073
+3074
+3075
+3076
+3077
+3078
+3079
+3080
+3081
+3082
+3083
+3084
+3085
+3086
+3087
+3088
+3089
+3090
+3091
+3092
+3093
+3094
+3095
+3096
+3097
+3098
+3099
+3100
+3101
+3102
+3103
+3104
+3105
+3106
+3107
+3108
+3109
+3110
+3111
+3112
+3113
+3114
+3115
+3116
+3117
+3118
+3119
+3120
+3121
+3122
+3123
+3124
+3125
+3126
+3127
+3128
+3129
+3130
+3131
+3132
+3133
+3134
+3135
+3136
+3137
+3138
+3139
+3140
+3141
+3142
+3143
+3144
+3145
+3146
+3147
+3148
+3149
+3150
+3151
+3152
+3153
+3154
+3155
+3156
+3157
+3158
+3159
+3160
+3161
+3162
+3163
+3164
+3165
+3166
+3167
+3168
+3169
+3170
+3171
+3172
+3173
+3174
+3175
+3176
+3177
+3178
+3179
+3180
+3181
+3182
+3183
+3184
+3185
+3186
+3187
+3188
+3189
+3190
+3191
+3192
+3193
+3194
+3195
+3196
+3197
+3198
+3199
+3200
+3201
+3202
+3203
+3204
+3205
+3206
+3207
+3208
+3209
+3210
+3211
+3212
+3213
+3214
+3215
+3216
+3217
+3218
+3219
+3220
+3221
+3222
+3223
+3224
+3225
+3226
+3227
+3228
+3229
+3230
+3231
+3232
+3233
+3234
+3235
+3236
+3237
+3238
+3239
+3240
+3241
+3242
+3243
+3244
+3245
+3246
+3247
+3248
+3249
+3250
+3251
+3252
+3253
+3254
+3255
+3256
+3257
+3258
+3259
+3260
+3261
+3262
+3263
+3264
+3265
+3266
+3267
+3268
+3269
+3270
+3271
+3272
+3273
+3274
+3275
+3276
+3277
+3278
+3279
+3280
+3281
+3282
+3283
+3284
+3285
+3286
+3287
+3288
+3289
+3290
+3291
+3292
+3293
+3294
+3295
+3296
+3297
+3298
+3299
+3300
+3301
+3302
+3303
+3304
+3305
+3306
+3307
+3308
+3309
+3310
+3311
+3312
+3313
+3314
+3315
+3316
+3317
+3318
+3319
+3320
+3321
+3322
+3323
+3324
+3325
+3326
+3327
+3328
+3329
+3330
+3331
+3332
+3333
+3334
+3335
+3336
+3337
+3338
+3339
+3340
+3341
+3342
+3343
+3344
+3345
+3346
+3347
+3348
+3349
+3350
+3351
+3352
+3353
+3354
+3355
+3356
+3357
+3358
+3359
+3360
+3361
+3362
+3363
+3364
+3365
+3366
+3367
+3368
+3369
+3370
+3371
+3372
+3373
+3374
+3375
+3376
+3377
+3378
+3379
+3380
+3381
+3382
+3383
+3384
+3385
+3386
+3387
+3388
+3389
+3390
+3391
+3392
+3393
+3394
+3395
+3396
+3397
+3398
+3399
+3400
+3401
+3402
+3403
+3404
+3405
+3406
+3407
+3408
+3409
+3410
+3411
+3412
+3413
+3414
+3415
+3416
+3417
+3418
+3419
+3420
+3421
+3422
+3423
+3424
+3425
+3426
+3427
+3428
+3429
+3430
+3431
+3432
+3433
+3434
+3435
+3436
+3437
+3438
+3439
+3440
+3441
+3442
+3443
+3444
+3445
+3446
+3447
+3448
+3449
+3450
+3451
+3452
+3453
+3454
+3455
+3456
+3457
+3458
+3459
+3460
+3461
+3462
+3463
+3464
+3465
+3466
+3467
+3468
+3469
+3470
+3471
+3472
+3473
+3474
+3475
+3476
+3477
+3478
+3479
+3480
+3481
+3482
+3483
+3484
+3485
+3486
+3487
+3488
+3489
+3490
+3491
+3492
+3493
+3494
+3495
+3496
+3497
+3498
+3499
+3500
+3501
+3502
+3503
+3504
+3505
+3506
+3507
+3508
+3509
+3510
+3511
+3512
+3513
+3514
+3515
+3516
+3517
+3518
+3519
+3520
+3521
+3522
+3523
+3524
+3525
+3526
+3527
+3528
+3529
+3530
+3531
+3532
+3533
+3534
+3535
+3536
+3537
+3538
+3539
+3540
+3541
+3542
+3543
+3544
+3545
+3546
+3547
+3548
+3549
+3550
+3551
+3552
+3553
+3554
+3555
+3556
+3557
+3558
+3559
+3560
+3561
+3562
+3563
+3564
+3565
+3566
+3567
+3568
+3569
+3570
+3571
+3572
+3573
+3574
+3575
+3576
+3577
+3578
+3579
+3580
+3581
+3582
+3583
+3584
+3585
+3586
+3587
+3588
+3589
+3590
+3591
+3592
+3593
+3594
+3595
+3596
+3597
+3598
+3599
+3600
+3601
+3602
+3603
+3604
+3605
+3606
+3607
+3608
+3609
+3610
+3611
+3612
+3613
+3614
+3615
+3616
+3617
+3618
+3619
+3620
+3621
+3622
+3623
+3624
+3625
+3626
+3627
+3628
+3629
+3630
+3631
+3632
+3633
+3634
+3635
+3636
+3637
+3638
+3639
+3640
+3641
+3642
+3643
+3644
+3645
+3646
+3647
+3648
+3649
+3650
+3651
+3652
+3653
+3654
+3655
+3656
+3657
+3658
+3659
+3660
+3661
+3662
+3663
+3664
+3665
+3666
+3667
+3668
+3669
+3670
+3671
+3672
+3673
+3674
+3675
+3676
+3677
+3678
+3679
+3680
+3681
+3682
+3683
+3684
+3685
+3686
+3687
+3688
+3689
+3690
+3691
+3692
+3693
+3694
+3695
+3696
+3697
+3698
+3699
+3700
+3701
+3702
+3703
+3704
+3705
+3706
+3707
+3708
+3709
+3710
+3711
+3712
+3713
+3714
+3715
+3716
+3717
+3718
+3719
+3720
+3721
+3722
+3723
+3724
+3725
+3726
+3727
+3728
+3729
+3730
+3731
+3732
+3733
+3734
+3735
+3736
+3737
+3738
+3739
+3740
+3741
+3742
+3743
+3744
+3745
+3746
+3747
+3748
+3749
+3750
+3751
+3752
+3753
+3754
+3755
+3756
+3757
+3758
+3759
+3760
+3761
+3762
+3763
+3764
+3765
+3766
+3767
+3768
+3769
+3770
+3771
+3772
+3773
+3774
+3775
+3776
+3777
+3778
+3779
+3780
+3781
+3782
+3783
+3784
+3785
+3786
+3787
+3788
+3789
+3790
+3791
+3792
+3793
+3794
+3795
+3796
+3797
+3798
+3799
+3800
+3801
+3802
+3803
+3804
+3805
+3806
+3807
+3808
+3809
+3810
+3811
+3812
+3813
+3814
+3815
+3816
+3817
+3818
+3819
+3820
+3821
+3822
+3823
+3824
+3825
+3826
+3827
+3828
+3829
+3830
+3831
+3832
+3833
+3834
+3835
+3836
+3837
+3838
+3839
+3840
+3841
+3842
+3843
+3844
+3845
+3846
+3847
+3848
+3849
+3850
+3851
+3852
+3853
+3854
+3855
+3856
+3857
+3858
+3859
+3860
+3861
+3862
+3863
+3864
+3865
+3866
+3867
+3868
+3869
+3870
+3871
+3872
+3873
+3874
+3875
+3876
+3877
+3878
+3879
+3880
+3881
+3882
+3883
+3884
+3885
+3886
+3887
+3888
+3889
+3890
+3891
+3892
+3893
+3894
+3895
+3896
+3897
+3898
+3899
+3900
+3901
+3902
+3903
+3904
+3905
+3906
+3907
+3908
+3909
+3910
+3911
+3912
+3913
+3914
+3915
+3916
+3917
+3918
+3919
+3920
+3921
+3922
+3923
+3924
+3925
+3926
+3927
+3928
+3929
+3930
+3931
+3932
+3933
+3934
+3935
+3936
+3937
+3938
+3939
+3940
+3941
+3942
+3943
+3944
+3945
+3946
+3947
+3948
+3949
+3950
+3951
+3952
+3953
+3954
+3955
+3956
+3957
+3958
+3959
+3960
+3961
+3962
+3963
+3964
+3965
+3966
+3967
+3968
+3969
+3970
+3971
+3972
+3973
+3974
+3975
+3976
+3977
+3978
+3979
+3980
+3981
+3982
+3983
+3984
+3985
+3986
+3987
+3988
+3989
+3990
+3991
+3992
+3993
+3994
+3995
+3996
+3997
+3998
+3999
+4000
+4001
+4002
+4003
+4004
+4005
+4006
+4007
+4008
+4009
+4010
+4011
+4012
+4013
+4014
+4015
+4016
+4017
+4018
+4019
+4020
+4021
+4022
+4023
+4024
+4025
+4026
+4027
+4028
+4029
+4030
+4031
+4032
+4033
+4034
+4035
+4036
+4037
+4038
+4039
+4040
+4041
+4042
+4043
+4044
+4045
+4046
+4047
+4048
+4049
+4050
+4051
+4052
+4053
+4054
+4055
+4056
+4057
+4058
+4059
+4060
+4061
+4062
+4063
+4064
+4065
+4066
+4067
+4068
+4069
+4070
+4071
+4072
+4073
+4074
+4075
+4076
+4077
+4078
+4079
+4080
+4081
+4082
+4083
+4084
+4085
+4086
+4087
+4088
+4089
+4090
+4091
+4092
+4093
+4094
+4095
+4096
+4097
+4098
+4099
+4100
+4101
+4102
+4103
+4104
+4105
+4106
+4107
+4108
+4109
+4110
+4111
+4112
+4113
+4114
+4115
+4116
+4117
+4118
+4119
+4120
+4121
+4122
+4123
+4124
+4125
+4126
+4127
+4128
+4129
+4130
+4131
+4132
+4133
+4134
+4135
+4136
+4137
+4138
+4139
+4140
+4141
+4142
+4143
+4144
+4145
+4146
+4147
+4148
+4149
+4150
+4151
+4152
+4153
+4154
+4155
+4156
+4157
+4158
+4159
+4160
+4161
+4162
+4163
+4164
+4165
+4166
+4167
+4168
+4169
+4170
+4171
+4172
+4173
+4174
+4175
+4176
+4177
+4178
+4179
+4180
+4181
+4182
+4183
+4184
+4185
+4186
+4187
+4188
+4189
+4190
+4191
+4192
+4193
+4194
+4195
+4196
+4197
+4198
+4199
+4200
+4201
+4202
+4203
+4204
+4205
+4206
+4207
+4208
+4209
+4210
+4211
+4212
+4213
+4214
+4215
+4216
+4217
+4218
+4219
+4220
+4221
+4222
+4223
+4224
+4225
+4226
+4227
+4228
+4229
+4230
+4231
+4232
+4233
+4234
+4235
+4236
+4237
+4238
+4239
+4240
+4241
+4242
+4243
+4244
+4245
+4246
+4247
+4248
+4249
+4250
+4251
+4252
+4253
+4254
+4255
+4256
+4257
+4258
+4259
+4260
+4261
+4262
+4263
+4264
+4265
+4266
+4267
+4268
+4269
+4270
+4271
+4272
+4273
+4274
+4275
+4276
+4277
+4278
+4279
+4280
+4281
+4282
+4283
+4284
+4285
+4286
+4287
+4288
+4289
+4290
+4291
+4292
+4293
+4294
+4295
+4296
+4297
+4298
+4299
+4300
+4301
+4302
+4303
+4304
+4305
+4306
+4307
+4308
+4309
+4310
+4311
+4312
+4313
+4314
+4315
+4316
+4317
+4318
+4319
+4320
+4321
+4322
+4323
+4324
+4325
+4326
+4327
+4328
+4329
+4330
+4331
+4332
+4333
+4334
+4335
+4336
+4337
+4338
+4339
+4340
+4341
+4342
+4343
+4344
+4345
+4346
+4347
+4348
+4349
+4350
+4351
+4352
+4353
+4354
+4355
+4356
+4357
+4358
+4359
+4360
+4361
+4362
+4363
+4364
+4365
+4366
+4367
+4368
+4369
+4370
+4371
+4372
+4373
+4374
+4375
+4376
+4377
+4378
+4379
+4380
+4381
+4382
+4383
+4384
+4385
+4386
+4387
+4388
+4389
+4390
+4391
+4392
+4393
+4394
+4395
+4396
+4397
+4398
+4399
+4400
+4401
+4402
+4403
+4404
+4405
+4406
+4407
+4408
+4409
+4410
+4411
+4412
+4413
+4414
+4415
+4416
+4417
+4418
+4419
+4420
+4421
+4422
+4423
+4424
+4425
+4426
+4427
+4428
+4429
+4430
+4431
+4432
+4433
+4434
+4435
+4436
+4437
+4438
+4439
+4440
+4441
+4442
+4443
+4444
+4445
+4446
+4447
+4448
+4449
+4450
+4451
+4452
+4453
+4454
+4455
+4456
+4457
+4458
+4459
+4460
+4461
+4462
+4463
+4464
+4465
+4466
+4467
+4468
+4469
+4470
+4471
+4472
+4473
+4474
+4475
+4476
+4477
+4478
+4479
+4480
+4481
+4482
+4483
+4484
+4485
+4486
+4487
+4488
+4489
+4490
+4491
+4492
+4493
+4494
+4495
+4496
+4497
+4498
+4499
+4500
+4501
+4502
+4503
+4504
+4505
+4506
+4507
+4508
+4509
+4510
+4511
+4512
+4513
+4514
+4515
+4516
+4517
+4518
+4519
+4520
+4521
+4522
+4523
+4524
+4525
+4526
+4527
+4528
+4529
+4530
+4531
+4532
+4533
+4534
+4535
+4536
+4537
+4538
+4539
+4540
+4541
+4542
+4543
+4544
+4545
+4546
+4547
+4548
+4549
+4550
+4551
+4552
+4553
+4554
+4555
+4556
+4557
+4558
+4559
+4560
+4561
+4562
+4563
+4564
+4565
+4566
+4567
+4568
+4569
+4570
+4571
+4572
+4573
+4574
+4575
+4576
+4577
+4578
+4579
+4580
+4581
+4582
+4583
+4584
+4585
+4586
+4587
+4588
+4589
+4590
+4591
+4592
+4593
+4594
+4595
+4596
+4597
+4598
+4599
+4600
+4601
+4602
+4603
+4604
+4605
+4606
+4607
+4608
+4609
+4610
+4611
+4612
+4613
+4614
+4615
+4616
+4617
+4618
+4619
+4620
+4621
+4622
+4623
+4624
+4625
+4626
+4627
+4628
+4629
+4630
+4631
+4632
+4633
+4634
+4635
+4636
+4637
+4638
+4639
+4640
+4641
+4642
+4643
+4644
+4645
+4646
+4647
+4648
+4649
+4650
+4651
+4652
+4653
+4654
+4655
+4656
+4657
+4658
+4659
+4660
+4661
+4662
+4663
+4664
+4665
+4666
+4667
+4668
+4669
+4670
+4671
+4672
+4673
+4674
+4675
+4676
+4677
+4678
+4679
+4680
+4681
+4682
+4683
+4684
+4685
+4686
+4687
+4688
+4689
+4690
+4691
+4692
+4693
+4694
+4695
+4696
+4697
+4698
+4699
+4700
+4701
+4702
+4703
+4704
+4705
+4706
+4707
+4708
+4709
+4710
+4711
+4712
+4713
+4714
+4715
+4716
+4717
+4718
+4719
+4720
+4721
+4722
+4723
+4724
+4725
+4726
+4727
+4728
+4729
+4730
+4731
+4732
+4733
+4734
+4735
+4736
+4737
+4738
+4739
+4740
+4741
+4742
+4743
+4744
+4745
+4746
+4747
+4748
+4749
+4750
+4751
+4752
+4753
+4754
+4755
+4756
+4757
+4758
+4759
+4760
+4761
+4762
+4763
+4764
+4765
+4766
+4767
+4768
+4769
+4770
+4771
+4772
+4773
+4774
+4775
+4776
+4777
+4778
+4779
+4780
+4781
+4782
+4783
+4784
+4785
+4786
+4787
+4788
+4789
+4790
+4791
+4792
+4793
+4794
+4795
+4796
+4797
+4798
+4799
+4800
+4801
+4802
+4803
+4804
+4805
+4806
+4807
+4808
+4809
+4810
+4811
+4812
+4813
+4814
+4815
+4816
+4817
+4818
+4819
+4820
+4821
+4822
+4823
+4824
+4825
+4826
+4827
+4828
+4829
+4830
+4831
+4832
+4833
+4834
+4835
+4836
+4837
+4838
+4839
+4840
+4841
+4842
+4843
+4844
+4845
+4846
+4847
+4848
+4849
+4850
+4851
+4852
+4853
+4854
+4855
+4856
+4857
+4858
+4859
+4860
+4861
+4862
+4863
+4864
+4865
+4866
+4867
+4868
+4869
+4870
+4871
+4872
+4873
+4874
+4875
+4876
+4877
+4878
+4879
+4880
+4881
+4882
+4883
+4884
+4885
+4886
+4887
+4888
+4889
+4890
+4891
+4892
+4893
+4894
+4895
+4896
+4897
+4898
+4899
+4900
+4901
+4902
+4903
+4904
+4905
+4906
+4907
+4908
+4909
+4910
+4911
+4912
+4913
+4914
+4915
+4916
+4917
+4918
+4919
+4920
+4921
+4922
+4923
+4924
+4925
+4926
+4927
+4928
+4929
+4930
+4931
+4932
+4933
+4934
+4935
+4936
+4937
+4938
+4939
+4940
+4941
+4942
+4943
+4944
+4945
+4946
+4947
+4948
+4949
+4950
+4951
+4952
+4953
+4954
+4955
+4956
+4957
+4958
+4959
+4960
+4961
+4962
+4963
+4964
+4965
+4966
+4967
+4968
+4969
+4970
+4971
+4972
+4973
+4974
+4975
+4976
+4977
+4978
+4979
+4980
+4981
+4982
+4983
+4984
+4985
+4986
+4987
+4988
+4989
+4990
+4991
+4992
+4993
+4994
+4995
+4996
+4997
+4998
+4999
+5000
+5001
+5002
+5003
+5004
+5005
+5006
+5007
+5008
+5009
+5010
+5011
+5012
+5013
+5014
+5015
+5016
+5017
+5018
+5019
+5020
+5021
+5022
+5023
+5024
+5025
+5026
+5027
+5028
+5029
+5030
+5031
+5032
+5033
+5034
+5035
+5036
+5037
+5038
+5039
+5040
+5041
+5042
+5043
+5044
+5045
+5046
+5047
+5048
+5049
+5050
+5051
+5052
+5053
+5054
+5055
+5056
+5057
+5058
+5059
+5060
+5061
+5062
+5063
+5064
+5065
+5066
+5067
+5068
+5069
+5070
+5071
+5072
+5073
+5074
+5075
+5076
+5077
+5078
+5079
+5080
+5081
+5082
+5083
+5084
+5085
+5086
+5087
+5088
+5089
+5090
+5091
+5092
+5093
+5094
+5095
+5096
+5097
+5098
+5099
+5100
+5101
+5102
+5103
+5104
+5105
+5106
+5107
+5108
+5109
+5110
+5111
+5112
+5113
+5114
+5115
+5116
+5117
+5118
+5119
+5120
+5121
+5122
+5123
+5124
+5125
+5126
+5127
+5128
+5129
+5130
+5131
+5132
+5133
+5134
+5135
+5136
+5137
+5138
+5139
+5140
+5141
+5142
+5143
+5144
+5145
+5146
+5147
+5148
+5149
+5150
+5151
+5152
+5153
+5154
+5155
+5156
+5157
+5158
+5159
+5160
+5161
+5162
+5163
+5164
+5165
+5166
+5167
+5168
+5169
+5170
+5171
+5172
+5173
+5174
+5175
+5176
+5177
+5178
+5179
+5180
+5181
+5182
+5183
+5184
+5185
+5186
+5187
+5188
+5189
+5190
+5191
+5192
+5193
+5194
+5195
+5196
+5197
+5198
+5199
+5200
+5201
+5202
+5203
+5204
+5205
+5206
+5207
+5208
+5209
+5210
+5211
+5212
+5213
+5214
+5215
+5216
+5217
+5218
+5219
+5220
+5221
+5222
+5223
+5224
+5225
+5226
+5227
+5228
+5229
+5230
+5231
+5232
+5233
+5234
+5235
+5236
+5237
+5238
+5239
+5240
+5241
+5242
+5243
+5244
+5245
+5246
+5247
+5248
+5249
+5250
+5251
+5252
+5253
+5254
+5255
+5256
+5257
+5258
+5259
+5260
+5261
+5262
+5263
+5264
+5265
+5266
+5267
+5268
+5269
+5270
+5271
+5272
+5273
+5274
+5275
+5276
+5277
+5278
+5279
+5280
+5281
+5282
+5283
+5284
+5285
+5286
+5287
+5288
+5289
+5290
+5291
+5292
+5293
+5294
+5295
+5296
+5297
+5298
+5299
+5300
+5301
+5302
+5303
+5304
+5305
+5306
+5307
+5308
+5309
+5310
+5311
+5312
+5313
+5314
+5315
+5316
+5317
+5318
+5319
+5320
+5321
+5322
+5323
+5324
+5325
+5326
+5327
+5328
+5329
+5330
+5331
+5332
+5333
+5334
+5335
+5336
+5337
+5338
+5339
+5340
+5341
+5342
+5343
+5344
+5345
+5346
+5347
+5348
+5349
+5350
+5351
+5352
+5353
+5354
+5355
+5356
+5357
+5358
+5359
+5360
+5361
+5362
+5363
+5364
+5365
+5366
+5367
+5368
+5369
+5370
+5371
+5372
+5373
+5374
+5375
+5376
+5377
+5378
+5379
+5380
+5381
+5382
+5383
+5384
+5385
+5386
+5387
+5388
+5389
+5390
+5391
+5392
+5393
+5394
+5395
+5396
+5397
+5398
+5399
+5400
+5401
+5402
+5403
+5404
+5405
+5406
+5407
+5408
+5409
+5410
+5411
+5412
+5413
+5414
+5415
+5416
+5417
+5418
+5419
+5420
+5421
+5422
+5423
+5424
+5425
+5426
+5427
+5428
+5429
+5430
+5431
+5432
+5433
+5434
+5435
+5436
+5437
+5438
+5439
+5440
+5441
+5442
+5443
+5444
+5445
+5446
+5447
+5448
+5449
+5450
+5451
+5452
+5453
+5454
+5455
+5456
+5457
+5458
+5459
+5460
+5461
+5462
+5463
+5464
+5465
+5466
+5467
+5468
+5469
+5470
+5471
+5472
+5473
+5474
+5475
+5476
+5477
+5478
+5479
+5480
+5481
+5482
+5483
+5484
+5485
+5486
+5487
+5488
+5489
+5490
+5491
+5492
+5493
+5494
+5495
+5496
+5497
+5498
+5499
+5500
+5501
+5502
+5503
+5504
+5505
+5506
+5507
+5508
+5509
+5510
+5511
+5512
+5513
+5514
+5515
+5516
+5517
+5518
+5519
+5520
+5521
+5522
+5523
+5524
+5525
+5526
+5527
+5528
+5529
+5530
+5531
+5532
+5533
+5534
+5535
+5536
+5537
+5538
+5539
+5540
+5541
+5542
+5543
+5544
+5545
+5546
+5547
+5548
+5549
+5550
+5551
+5552
+5553
+5554
+5555
+5556
+5557
+5558
+5559
+5560
+5561
+5562
+5563
+5564
+5565
+5566
+5567
+5568
+5569
+5570
+5571
+5572
+5573
+5574
+5575
+5576
+5577
+5578
+5579
+5580
+5581
+5582
+5583
+5584
+5585
+5586
+5587
+5588
+5589
+5590
+5591
+5592
+5593
+5594
+5595
+5596
+5597
+5598
+5599
+5600
+5601
+5602
+5603
+5604
+5605
+5606
+5607
+5608
+5609
+5610
+5611
+5612
+5613
+5614
+5615
+5616
+5617
+5618
+5619
+5620
+5621
+5622
+5623
+5624
+5625
+5626
+5627
+5628
+5629
+5630
+5631
+5632
+5633
+5634
+5635
+5636
+5637
+5638
+5639
+5640
+5641
+5642
+5643
+5644
+5645
+5646
+5647
+5648
+5649
+5650
+5651
+5652
+5653
+5654
+5655
+5656
+5657
+5658
+5659
+5660
+5661
+5662
+5663
+5664
+5665
+5666
+5667
+5668
+5669
+5670
+5671
+5672
+5673
+5674
+5675
+5676
+5677
+5678
+5679
+5680
+5681
+5682
+5683
+5684
+5685
+5686
+5687
+5688
+5689
+5690
+5691
+5692
+5693
+5694
+5695
+5696
+5697
+5698
+5699
+5700
+5701
+5702
+5703
+5704
+5705
+5706
+5707
+5708
+5709
+5710
+5711
+5712
+5713
+5714
+5715
+5716
+5717
+5718
+5719
+5720
+5721
+5722
+5723
+5724
+5725
+5726
+5727
+5728
+5729
+5730
+5731
+5732
+5733
+5734
+5735
+5736
+5737
+5738
+5739
+5740
+5741
+5742
+5743
+5744
+5745
+5746
+5747
+5748
+5749
+5750
+5751
+5752
+5753
+5754
+5755
+5756
+5757
+5758
+5759
+5760
+5761
+5762
+5763
+5764
+5765
+5766
+5767
+5768
+5769
+5770
+5771
+5772
+5773
+5774
+5775
+5776
+5777
+5778
+5779
+5780
+5781
+5782
+5783
+5784
+5785
+5786
+5787
+5788
+5789
+5790
+5791
+5792
+5793
+5794
+5795
+5796
+5797
+5798
+5799
+5800
+5801
+5802
+5803
+5804
+5805
+5806
+5807
+5808
+5809
+5810
+5811
+5812
+5813
+5814
+5815
+5816
+5817
+5818
+5819
+5820
+5821
+5822
+5823
+5824
+5825
+5826
+5827
+5828
+5829
+5830
+5831
+5832
+5833
+5834
+5835
+5836
+5837
+5838
+5839
+5840
+5841
+5842
+5843
+5844
+5845
+5846
+5847
+5848
+5849
+5850
+5851
+5852
+5853
+5854
+5855
+5856
+5857
+5858
+5859
+5860
+5861
+5862
+5863
+5864
+5865
+5866
+5867
+5868
+5869
+5870
+5871
+5872
+5873
+5874
+5875
+5876
+5877
+5878
+5879
+5880
+5881
+5882
+5883
+5884
+5885
+5886
+5887
+5888
+5889
+5890
+5891
+5892
+5893
+5894
+5895
+5896
+5897
+5898
+5899
+5900
+5901
+5902
+5903
+5904
+5905
+5906
+5907
+5908
+5909
+5910
+5911
+5912
+5913
+5914
+5915
+5916
+5917
+5918
+5919
+5920
+5921
+5922
+5923
+5924
+5925
+5926
+5927
+5928
+5929
+5930
+5931
+5932
+5933
+5934
+5935
+5936
+5937
+5938
+5939
+5940
+5941
+5942
+5943
+5944
+5945
+5946
+5947
+5948
+5949
+5950
+5951
+5952
+5953
+5954
+5955
+5956
+5957
+5958
+5959
+5960
+5961
+5962
+5963
+5964
+5965
+5966
+5967
+5968
+5969
+5970
+5971
+5972
+5973
+5974
+5975
+5976
+5977
+5978
+5979
+5980
+5981
+5982
+5983
+5984
+5985
+5986
+5987
+5988
+5989
+5990
+5991
+5992
+5993
+5994
+5995
+5996
+5997
+5998
+5999
+6000
+6001
+6002
+6003
+6004
+6005
+6006
+6007
+6008
+6009
+6010
+6011
+6012
+6013
+6014
+6015
+6016
+6017
+6018
+6019
+6020
+6021
+6022
+6023
+6024
+6025
+6026
+6027
+6028
+6029
+6030
+6031
+6032
+6033
+6034
+6035
+6036
+6037
+6038
+6039
+6040
+6041
+6042
+6043
+6044
+6045
+6046
+6047
+6048
+6049
+6050
+6051
+6052
+6053
+6054
+6055
+6056
+6057
+6058
+6059
+6060
+6061
+6062
+6063
+6064
+6065
+6066
+6067
+6068
+6069
+6070
+6071
+6072
+6073
+6074
+6075
+6076
+6077
+6078
+6079
+6080
+6081
+6082
+6083
+6084
+6085
+6086
+6087
+6088
+6089
+6090
+6091
+6092
+6093
+6094
+6095
+6096
+6097
+6098
+6099
+6100
+6101
+6102
+6103
+6104
+6105
+6106
+6107
+6108
+6109
+6110
+6111
+6112
+6113
+6114
+6115
+6116
+6117
+6118
+6119
+6120
+6121
+6122
+6123
+6124
+6125
+6126
+6127
+6128
+6129
+6130
+6131
+6132
+6133
+6134
+6135
+6136
+6137
+6138
+6139
+6140
+6141
+6142
+6143
+6144
+6145
+6146
+6147
+6148
+6149
+6150
+6151
+6152
+6153
+6154
+6155
+6156
+6157
+6158
+6159
+6160
+6161
+6162
+6163
+6164
+6165
+6166
+6167
+6168
+6169
+6170
+6171
+6172
+6173
+6174
+6175
+6176
+6177
+6178
+6179
+6180
+6181
+6182
+6183
+6184
+6185
+6186
+6187
+6188
+6189
+6190
+6191
+6192
+6193
+6194
+6195
+6196
+6197
+6198
+6199
+6200
+6201
+6202
+6203
+6204
+6205
+6206
+6207
+6208
+6209
+6210
+6211
+6212
+6213
+6214
+6215
+6216
+6217
+6218
+6219
+6220
+6221
+6222
+6223
+6224
+6225
+6226
+6227
+6228
+6229
+6230
+6231
+6232
+6233
+6234
+6235
+6236
+6237
+6238
+6239
+6240
+6241
+6242
+6243
+6244
+6245
+6246
+6247
+6248
+6249
+6250
+6251
+6252
+6253
+6254
+6255
+6256
+6257
+6258
+6259
+6260
+6261
+6262
+6263
+6264
+6265
+6266
+6267
+6268
+6269
+6270
+6271
+6272
+6273
+6274
+6275
+6276
+6277
+6278
+6279
+6280
+6281
+6282
+6283
+6284
+6285
+6286
+6287
+6288
+6289
+6290
+6291
+6292
+6293
+6294
+6295
+6296
+6297
+6298
+6299
+6300
+6301
+6302
+6303
+6304
+6305
+6306
+6307
+6308
+6309
+6310
+6311
+6312
+6313
+6314
+6315
+6316
+6317
+6318
+6319
+6320
+6321
+6322
+6323
+6324
+6325
+6326
+6327
+6328
+6329
+6330
+6331
+6332
+6333
+6334
+6335
+6336
+6337
+6338
+6339
+6340
+6341
+6342
+6343
+6344
+6345
+6346
+6347
+6348
+6349
+6350
+6351
+6352
+6353
+6354
+6355
+6356
+6357
+6358
+6359
+6360
+6361
+6362
+6363
+6364
+6365
+6366
+6367
+6368
+6369
+6370
+6371
+6372
+6373
+6374
+6375
+6376
+6377
+6378
+6379
+6380
+6381
+6382
+6383
+6384
+6385
+6386
+6387
+6388
+6389
+6390
+6391
+6392
+6393
+6394
+6395
+6396
+6397
+6398
+6399
+6400
+6401
+6402
+6403
+6404
+6405
+6406
+6407
+6408
+6409
+6410
+6411
+6412
+6413
+6414
+6415
+6416
+6417
+6418
+6419
+6420
+6421
+6422
+6423
+6424
+6425
+6426
+6427
+6428
+6429
+6430
+6431
+6432
+6433
+6434
+6435
+6436
+6437
+6438
+6439
+6440
+6441
+6442
+6443
+6444
+6445
+6446
+6447
+6448
+6449
+6450
+6451
+6452
+6453
+6454
+6455
+6456
+6457
+6458
+6459
+6460
+6461
+6462
+6463
+6464
+6465
+6466
+6467
+6468
+6469
+6470
+6471
+6472
+6473
+6474
+6475
+6476
+6477
+6478
+6479
+6480
+6481
+6482
+6483
+6484
+6485
+6486
+6487
+6488
+6489
+6490
+6491
+6492
+6493
+6494
+6495
+6496
+6497
+6498
+6499
+6500
+6501
+6502
+6503
+6504
+6505
+6506
+6507
+6508
+6509
+6510
+6511
+6512
+6513
+6514
+6515
+6516
+6517
+6518
+6519
+6520
+6521
+6522
+6523
+6524
+6525
+6526
+6527
+6528
+6529
+6530
+6531
+6532
+6533
+6534
+6535
+6536
+6537
+6538
+6539
+6540
+6541
+6542
+6543
+6544
+6545
+6546
+6547
+6548
+6549
+6550
+6551
+6552
+6553
+6554
+6555
+6556
+6557
+6558
+6559
+6560
+6561
+6562
+6563
+6564
+6565
+6566
+6567
+6568
+6569
+6570
+6571
+6572
+6573
+6574
+6575
+6576
+6577
+6578
+6579
+6580
+6581
+6582
+6583
+6584
+6585
+6586
+6587
+6588
+6589
+6590
+6591
+6592
+6593
+6594
+6595
+6596
+6597
+6598
+6599
+6600
+6601
+6602
+6603
+6604
+6605
+6606
+6607
+6608
+6609
+6610
+6611
+6612
+6613
+6614
+6615
+6616
+6617
+6618
+6619
+6620
+6621
+6622
+6623
+6624
+6625
+6626
+6627
+6628
+6629
+6630
+6631
+6632
+6633
+6634
+6635
+6636
+6637
+6638
+6639
+6640
+6641
+6642
+6643
+6644
+6645
+6646
+6647
+6648
+6649
+6650
+6651
+6652
+6653
+6654
+6655
+6656
+6657
+6658
+6659
+6660
+6661
+6662
+6663
+6664
+6665
+6666
+6667
+6668
+6669
+6670
+6671
+6672
+6673
+6674
+6675
+6676
+6677
+6678
+6679
+6680
+6681
+6682
+6683
+6684
+6685
+6686
+6687
+6688
+6689
+6690
+6691
+6692
+6693
+6694
+6695
+6696
+6697
+6698
+6699
+6700
+6701
+6702
+6703
+6704
+6705
+6706
+6707
+6708
+6709
+6710
+6711
+6712
+6713
+6714
+6715
+6716
+6717
+6718
+6719
+6720
+6721
+6722
+6723
+6724
+6725
+6726
+6727
+6728
+6729
+6730
+6731
+6732
+6733
+6734
+6735
+6736
+6737
+6738
+6739
+6740
+6741
+6742
+6743
+6744
+6745
+6746
+6747
+6748
+6749
+6750
+6751
+6752
+6753
+6754
+6755
+6756
+6757
+6758
+6759
+6760
+6761
+6762
+6763
+6764
+6765
+6766
+6767
+6768
+6769
+6770
+6771
+6772
+6773
+6774
+6775
+6776
+6777
+6778
+6779
+6780
+6781
+6782
+6783
+6784
+6785
+6786
+6787
+6788
+6789
+6790
+6791
+6792
+6793
+6794
+6795
+6796
+6797
+6798
+6799
+6800
+6801
+6802
+6803
+6804
+6805
+6806
+6807
+6808
+6809
+6810
+6811
+6812
+6813
+6814
+6815
+6816
+6817
+6818
+6819
+6820
+6821
+6822
+6823
+6824
+6825
+6826
+6827
+6828
+6829
+6830
+6831
+6832
+6833
+6834
+6835
+6836
+6837
+6838
+6839
+6840
+6841
+6842
+6843
+6844
+6845
+6846
+6847
+6848
+6849
+6850
+6851
+6852
+6853
+6854
+6855
+6856
+6857
+6858
+6859
+6860
+6861
+6862
+6863
+6864
+6865
+6866
+6867
+6868
+6869
+6870
+6871
+6872
+6873
+6874
+6875
+6876
+6877
+6878
+6879
+6880
+6881
+6882
+6883
+6884
+6885
+6886
+6887
+6888
+6889
+6890
+6891
+6892
+6893
+6894
+6895
+6896
+6897
+6898
+6899
+6900
+6901
+6902
+6903
+6904
+6905
+6906
+6907
+6908
+6909
+6910
+6911
+6912
+6913
+6914
+6915
+6916
+6917
+6918
+6919
+6920
+6921
+6922
+6923
+6924
+6925
+6926
+6927
+6928
+6929
+6930
+6931
+6932
+6933
+6934
+6935
+6936
+6937
+6938
+6939
+6940
+6941
+6942
+6943
+6944
+6945
+6946
+6947
+6948
+6949
+6950
+6951
+6952
+6953
+6954
+6955
+6956
+6957
+6958
+6959
+6960
+6961
+6962
+6963
+6964
+6965
+6966
+6967
+6968
+6969
+6970
+6971
+6972
+6973
+6974
+6975
+6976
+6977
+6978
+6979
+6980
+6981
+6982
+6983
+6984
+6985
+6986
+6987
+6988
+6989
+6990
+6991
+6992
+6993
+6994
+6995
+6996
+6997
+6998
+6999
+7000
+7001
+7002
+7003
+7004
+7005
+7006
+7007
+7008
+7009
+7010
+7011
+7012
+7013
+7014
+7015
+7016
+7017
+7018
+7019
+7020
+7021
+7022
+7023
+7024
+7025
+7026
+7027
+7028
+7029
+7030
+7031
+7032
+7033
+7034
+7035
+7036
+7037
+7038
+7039
+7040
+7041
+7042
+7043
+7044
+7045
+7046
+7047
+7048
+7049
+7050
+7051
+7052
+7053
+7054
+7055
+7056
+7057
+7058
+7059
+7060
+7061
+7062
+7063
+7064
+7065
+7066
+7067
+7068
+7069
+7070
+7071
+7072
+7073
+7074
+7075
+7076
+7077
+7078
+7079
+7080
+7081
+7082
+7083
+7084
+7085
+7086
+7087
+7088
+7089
+7090
+7091
+7092
+7093
+7094
+7095
+7096
+7097
+7098
+7099
+7100
+7101
+7102
+7103
+7104
+7105
+7106
+7107
+7108
+7109
+7110
+7111
+7112
+7113
+7114
+7115
+7116
+7117
+7118
+7119
+7120
+7121
+7122
+7123
+7124
+7125
+7126
+7127
+7128
+7129
+7130
+7131
+7132
+7133
+7134
+7135
+7136
+7137
+7138
+7139
+7140
+7141
+7142
+7143
+7144
+7145
+7146
+7147
+7148
+7149
+7150
+7151
+7152
+7153
+7154
+7155
+7156
+7157
+7158
+7159
+7160
+7161
+7162
+7163
+7164
+7165
+7166
+7167
+7168
+7169
+7170
+7171
+7172
+7173
+7174
+7175
+7176
+7177
+7178
+7179
+7180
+7181
+7182
+7183
+7184
+7185
+7186
+7187
+7188
+7189
+7190
+7191
+7192
+7193
+7194
+7195
+7196
+7197
+7198
+7199
+7200
+7201
+7202
+7203
+7204
+7205
+7206
+7207
+7208
+7209
+7210
+7211
+7212
+7213
+7214
+7215
+7216
+7217
+7218
+7219
+7220
+7221
+7222
+7223
+7224
+7225
+7226
+7227
+7228
+7229
+7230
+7231
+7232
+7233
+7234
+7235
+7236
+7237
+7238
+7239
+7240
+7241
+7242
+7243
+7244
+7245
+7246
+7247
+7248
+7249
+7250
+7251
+7252
+7253
+7254
+7255
+7256
+7257
+7258
+7259
+7260
+7261
+7262
+7263
+7264
+7265
+7266
+7267
+7268
+7269
+7270
+7271
+7272
+7273
+7274
+7275
+7276
+7277
+7278
+7279
+7280
+7281
+7282
+7283
+7284
+7285
+7286
+7287
+7288
+7289
+7290
+7291
+7292
+7293
+7294
+7295
+7296
+7297
+7298
+7299
+7300
+7301
+7302
+7303
+7304
+7305
+7306
+7307
+7308
+7309
+7310
+7311
+7312
+7313
+7314
+7315
+7316
+7317
+7318
+7319
+7320
+7321
+7322
+7323
+7324
+7325
+7326
+7327
+7328
+7329
+7330
+7331
+7332
+7333
+7334
+7335
+7336
+7337
+7338
+7339
+7340
+7341
+7342
+7343
+7344
+7345
+7346
+7347
+7348
+7349
+7350
+7351
+7352
+7353
+7354
+7355
+7356
+7357
+7358
+7359
+7360
+7361
+7362
+7363
+7364
+7365
+7366
+7367
+7368
+7369
+7370
+7371
+7372
+7373
+7374
+7375
+7376
+7377
+7378
+7379
+7380
+7381
+7382
+7383
+7384
+7385
+7386
+7387
+7388
+7389
+7390
+7391
+7392
+7393
+7394
+7395
+7396
+7397
+7398
+7399
+7400
+7401
+7402
+7403
+7404
+7405
+7406
+7407
+7408
+7409
+7410
+7411
+7412
+7413
+7414
+7415
+7416
+7417
+7418
+7419
+7420
+7421
+7422
+7423
+7424
+7425
+7426
+7427
+7428
+7429
+7430
+7431
+7432
+7433
+7434
+7435
+7436
+7437
+7438
+7439
+7440
+7441
+7442
+7443
+7444
+7445
+7446
+7447
+7448
+7449
+7450
+7451
+7452
+7453
+7454
+7455
+7456
+7457
+7458
+7459
+7460
+7461
+7462
+7463
+7464
+7465
+7466
+7467
+7468
+7469
+7470
+7471
+7472
+7473
+7474
+7475
+7476
+7477
+7478
+7479
+7480
+7481
+7482
+7483
+7484
+7485
+7486
+7487
+7488
+7489
+7490
+7491
+7492
+7493
+7494
+7495
+7496
+7497
+7498
+7499
+7500
+7501
+7502
+7503
+7504
+7505
+7506
+7507
+7508
+7509
+7510
+7511
+7512
+7513
+7514
+7515
+7516
+7517
+7518
+7519
+7520
+7521
+7522
+7523
+7524
+7525
+7526
+7527
+7528
+7529
+7530
+7531
+7532
+7533
+7534
+7535
+7536
+7537
+7538
+7539
+7540
+7541
+7542
+7543
+7544
+7545
+7546
+7547
+7548
+7549
+7550
+7551
+7552
+7553
+7554
+7555
+7556
+7557
+7558
+7559
+7560
+7561
+7562
+7563
+7564
+7565
+7566
+7567
+7568
+7569
+7570
+7571
+7572
+7573
+7574
+7575
+7576
+7577
+7578
+7579
+7580
+7581
+7582
+7583
+7584
+7585
+7586
+7587
+7588
+7589
+7590
+7591
+7592
+7593
+7594
+7595
+7596
+7597
+7598
+7599
+7600
+7601
+7602
+7603
+7604
+7605
+7606
+7607
+7608
+7609
+7610
+7611
+7612
+7613
+7614
+7615
+7616
+7617
+7618
+7619
+7620
+7621
+7622
+7623
+7624
+7625
+7626
+7627
+7628
+7629
+7630
+7631
+7632
+7633
+7634
+7635
+7636
+7637
+7638
+7639
+7640
+7641
+7642
+7643
+7644
+7645
+7646
+7647
+7648
+7649
+7650
+7651
+7652
+7653
+7654
+7655
+7656
+7657
+7658
+7659
+7660
+7661
+7662
+7663
+7664
+7665
+7666
+7667
+7668
+7669
+7670
+7671
+7672
+7673
+7674
+7675
+7676
+7677
+7678
+7679
+7680
+7681
+7682
+7683
+7684
+7685
+7686
+7687
+7688
+7689
+7690
+7691
+7692
+7693
+7694
+7695
+7696
+7697
+7698
+7699
+7700
+7701
+7702
+7703
+7704
+7705
+7706
+7707
+7708
+7709
+7710
+7711
+7712
+7713
+7714
+7715
+7716
+7717
+7718
+7719
+7720
+7721
+7722
+7723
+7724
+7725
+7726
+7727
+7728
+7729
+7730
+7731
+7732
+7733
+7734
+7735
+7736
+7737
+7738
+7739
+7740
+7741
+7742
+7743
+7744
+7745
+7746
+7747
+7748
+7749
+7750
+7751
+7752
+7753
+7754
+7755
+7756
+7757
+7758
+7759
+7760
+7761
+7762
+7763
+7764
+7765
+7766
+7767
+7768
+7769
+7770
+7771
+7772
+7773
+7774
+7775
+7776
+7777
+7778
+7779
+7780
+7781
+7782
+7783
+7784
+7785
+7786
+7787
+7788
+7789
+7790
+7791
+7792
+7793
+7794
+7795
+7796
+7797
+7798
+7799
+7800
+7801
+7802
+7803
+7804
+7805
+7806
+7807
+7808
+7809
+7810
+7811
+7812
+7813
+7814
+7815
+7816
+7817
+7818
+7819
+7820
+7821
+7822
+7823
+7824
+7825
+7826
+7827
+7828
+7829
+7830
+7831
+7832
+7833
+7834
+7835
+7836
+7837
+7838
+7839
+7840
+7841
+7842
+7843
+7844
+7845
+7846
+7847
+7848
+7849
+7850
+7851
+7852
+7853
+7854
+7855
+7856
+7857
+7858
+7859
+7860
+7861
+7862
+7863
+7864
+7865
+7866
+7867
+7868
+7869
+7870
+7871
+7872
+7873
+7874
+7875
+7876
+7877
+7878
+7879
+7880
+7881
+7882
+7883
+7884
+7885
+7886
+7887
+7888
+7889
+7890
+7891
+7892
+7893
+7894
+7895
+7896
+7897
+7898
+7899
+7900
+7901
+7902
+7903
+7904
+7905
+7906
+7907
+7908
+7909
+7910
+7911
+7912
+7913
+7914
+7915
+7916
+7917
+7918
+7919
+7920
+7921
+7922
+7923
+7924
+7925
+7926
+7927
+7928
+7929
+7930
+7931
+7932
+7933
+7934
+7935
+7936
+7937
+7938
+7939
+7940
+7941
+7942
+7943
+7944
+7945
+7946
+7947
+7948
+7949
+7950
+7951
+7952
+7953
+7954
+7955
+7956
+7957
+7958
+7959
+7960
+7961
+7962
+7963
+7964
+7965
+7966
+7967
+7968
+7969
+7970
+7971
+7972
+7973
+7974
+7975
+7976
+7977
+7978
+7979
+7980
+7981
+7982
+7983
+7984
+7985
+7986
+7987
+7988
+7989
+7990
+7991
+7992
+7993
+7994
+7995
+7996
+7997
+7998
+7999
+8000
+8001
+8002
+8003
+8004
+8005
+8006
+8007
+8008
+8009
+8010
+8011
+8012
+8013
+8014
+8015
+8016
+8017
+8018
+8019
+8020
+8021
+8022
+8023
+8024
+8025
+8026
+8027
+8028
+8029
+8030
+8031
+8032
+8033
+8034
+8035
+8036
+8037
+8038
+8039
+8040
+8041
+8042
+8043
+8044
+8045
+8046
+8047
+8048
+8049
+8050
+8051
+8052
+8053
+8054
+8055
+8056
+8057
+8058
+8059
+8060
+8061
+8062
+8063
+8064
+8065
+8066
+8067
+8068
+8069
+8070
+8071
+8072
+8073
+8074
+8075
+8076
+8077
+8078
+8079
+8080
+8081
+8082
+8083
+8084
+8085
+8086
+8087
+8088
+8089
+8090
+8091
+8092
+8093
+8094
+8095
+8096
+8097
+8098
+8099
+8100
+8101
+8102
+8103
+8104
+8105
+8106
+8107
+8108
+8109
+8110
+8111
+8112
+8113
+8114
+8115
+8116
+8117
+8118
+8119
+8120
+8121
+8122
+8123
+8124
+8125
+8126
+8127
+8128
+8129
+8130
+8131
+8132
+8133
+8134
+8135
+8136
+8137
+8138
+8139
+8140
+8141
+8142
+8143
+8144
+8145
+8146
+8147
+8148
+8149
+8150
+8151
+8152
+8153
+8154
+8155
+8156
+8157
+8158
+8159
+8160
+8161
+8162
+8163
+8164
+8165
+8166
+8167
+8168
+8169
+8170
+8171
+8172
+8173
+8174
+8175
+8176
+8177
+8178
+8179
+8180
+8181
+8182
+8183
+8184
+8185
+8186
+8187
+8188
+8189
+8190
+8191
+8192
+8193
+8194
+8195
+8196
+8197
+8198
+8199
+8200
+8201
+8202
+8203
+8204
+8205
+8206
+8207
+8208
+8209
+8210
+8211
+8212
+8213
+8214
+8215
+8216
+8217
+8218
+8219
+8220
+8221
+8222
+8223
+8224
+8225
+8226
+8227
+8228
+8229
+8230
+8231
+8232
+8233
+8234
+8235
+8236
+8237
+8238
+8239
+8240
+8241
+8242
+8243
+8244
+8245
+8246
+8247
+8248
+8249
+8250
+8251
+8252
+8253
+8254
+8255
+8256
+8257
+8258
+8259
+8260
+8261
+8262
+8263
+8264
+8265
+8266
+8267
+8268
+8269
+8270
+8271
+8272
+8273
+8274
+8275
+8276
+8277
+8278
+8279
+8280
+8281
+8282
+8283
+8284
+8285
+8286
+8287
+8288
+8289
+8290
+8291
+8292
+8293
+8294
+8295
+8296
+8297
+8298
+8299
+8300
+8301
+8302
+8303
+8304
+8305
+8306
+8307
+8308
+8309
+8310
+8311
+8312
+8313
+8314
+8315
+8316
+8317
+8318
+8319
+8320
+8321
+8322
+8323
+8324
+8325
+8326
+8327
+8328
+8329
+8330
+8331
+8332
+8333
+8334
+8335
+8336
+8337
+8338
+8339
+8340
+8341
+8342
+8343
+8344
+8345
+8346
+8347
+8348
+8349
+8350
+8351
+8352
+8353
+8354
+8355
+8356
+8357
+8358
+8359
+8360
+8361
+8362
+8363
+8364
+8365
+8366
+8367
+8368
+8369
+8370
+8371
+8372
+8373
+8374
+8375
+8376
+8377
+8378
+8379
+8380
+8381
+8382
+8383
+8384
+8385
+8386
+8387
+8388
+8389
+8390
+8391
+8392
+8393
+8394
+8395
+8396
+8397
+8398
+8399
+8400
+8401
+8402
+8403
+8404
+8405
+8406
+8407
+8408
+8409
+8410
+8411
+8412
+8413
+8414
+8415
+8416
+8417
+8418
+8419
+8420
+8421
+8422
+8423
+8424
+8425
+8426
+8427
+8428
+8429
+8430
+8431
+8432
+8433
+8434
+8435
+8436
+8437
+8438
+8439
+8440
+8441
+8442
+8443
+8444
+8445
+8446
+8447
+8448
+8449
+8450
+8451
+8452
+8453
+8454
+8455
+8456
+8457
+8458
+8459
+8460
+8461
+8462
+8463
+8464
+8465
+8466
+8467
+8468
+8469
+8470
+8471
+8472
+8473
+8474
+8475
+8476
+8477
+8478
+8479
+8480
+8481
+8482
+8483
+8484
+8485
+8486
+8487
+8488
+8489
+8490
+8491
+8492
+8493
+8494
+8495
+8496
+8497
+8498
+8499
+8500
+8501
+8502
+8503
+8504
+8505
+8506
+8507
+8508
+8509
+8510
+8511
+8512
+8513
+8514
+8515
+8516
+8517
+8518
+8519
+8520
+8521
+8522
+8523
+8524
+8525
+8526
+8527
+8528
+8529
+8530
+8531
+8532
+8533
+8534
+8535
+8536
+8537
+8538
+8539
+8540
+8541
+8542
+8543
+8544
+8545
+8546
+8547
+8548
+8549
+8550
+8551
+8552
+8553
+8554
+8555
+8556
+8557
+8558
+8559
+8560
+8561
+8562
+8563
+8564
+8565
+8566
+8567
+8568
+8569
+8570
+8571
+8572
+8573
+8574
+8575
+8576
+8577
+8578
+8579
+8580
+8581
+8582
+8583
+8584
+8585
+8586
+8587
+8588
+8589
+8590
+8591
+8592
+8593
+8594
+8595
+8596
+8597
+8598
+8599
+8600
+8601
+8602
+8603
+8604
+8605
+8606
+8607
+8608
+8609
+8610
+8611
+8612
+8613
+8614
+8615
+8616
+8617
+8618
+8619
+8620
+8621
+8622
+8623
+8624
+8625
+8626
+8627
+8628
+8629
+8630
+8631
+8632
+8633
+8634
+8635
+8636
+8637
+8638
+8639
+8640
+8641
+8642
+8643
+8644
+8645
+8646
+8647
+8648
+8649
+8650
+8651
+8652
+8653
+8654
+8655
+8656
+8657
+8658
+8659
+8660
+8661
+8662
+8663
+8664
+8665
+8666
+8667
+8668
+8669
+8670
+8671
+8672
+8673
+8674
+8675
+8676
+8677
+8678
+8679
+8680
+8681
+8682
+8683
+8684
+8685
+8686
+8687
+8688
+8689
+8690
+8691
+8692
+8693
+8694
+8695
+8696
+8697
+8698
+8699
+8700
+8701
+8702
+8703
+8704
+8705
+8706
+8707
+8708
+8709
+8710
+8711
+8712
+8713
+8714
+8715
+8716
+8717
+8718
+8719
+8720
+8721
+8722
+8723
+8724
+8725
+8726
+8727
+8728
+8729
+8730
+8731
+8732
+8733
+8734
+8735
+8736
+8737
+8738
+8739
+8740
+8741
+8742
+8743
+8744
+8745
+8746
+8747
+8748
+8749
+8750
+8751
+8752
+8753
+8754
+8755
+8756
+8757
+8758
+8759
+8760
+8761
+8762
+8763
+8764
+8765
+8766
+8767
+8768
+8769
+8770
+8771
+8772
+8773
+8774
+8775
+8776
+8777
+8778
+8779
+8780
+8781
+8782
+8783
+8784
+8785
+8786
+8787
+8788
+8789
+8790
+8791
+8792
+8793
+8794
+8795
+8796
+8797
+8798
+8799
+8800
+8801
+8802
+8803
+8804
+8805
+8806
+8807
+8808
+8809
+8810
+8811
+8812
+8813
+8814
+8815
+8816
+8817
+8818
+8819
+8820
+8821
+8822
+8823
+8824
+8825
+8826
+8827
+8828
+8829
+8830
+8831
+8832
+8833
+8834
+8835
+8836
+8837
+8838
+8839
+8840
+8841
+8842
+8843
+8844
+8845
+8846
+8847
+8848
+8849
+8850
+8851
+8852
+8853
+8854
+8855
+8856
+8857
+8858
+8859
+8860
+8861
+8862
+8863
+8864
+8865
+8866
+8867
+8868
+8869
+8870
+8871
+8872
+8873
+8874
+8875
+8876
+8877
+8878
+8879
+8880
+8881
+8882
+8883
+8884
+8885
+8886
+8887
+8888
+8889
+8890
+8891
+8892
+8893
+8894
+8895
+8896
+8897
+8898
+8899
+8900
+8901
+8902
+8903
+8904
+8905
+8906
+8907
+8908
+8909
+8910
+8911
+8912
+8913
+8914
+8915
+8916
+8917
+8918
+8919
+8920
+8921
+8922
+8923
+8924
+8925
+8926
+8927
+8928
+8929
+8930
+8931
+8932
+8933
+8934
+8935
+8936
+8937
+8938
+8939
+8940
+8941
+8942
+8943
+8944
+8945
+8946
+8947
+8948
+8949
+8950
+8951
+8952
+8953
+8954
+8955
+8956
+8957
+8958
+8959
+8960
+8961
+8962
+8963
+8964
+8965
+8966
+8967
+8968
+8969
+8970
+8971
+8972
+8973
+8974
+8975
+8976
+8977
+8978
+8979
+8980
+8981
+8982
+8983
+8984
+8985
+8986
+8987
+8988
+8989
+8990
+8991
+8992
+8993
+8994
+8995
+8996
+8997
+8998
+8999
+9000
+9001
+9002
+9003
+9004
+9005
+9006
+9007
+9008
+9009
+9010
+9011
+9012
+9013
+9014
+9015
+9016
+9017
+9018
+9019
+9020
+9021
+9022
+9023
+9024
+9025
+9026
+9027
+9028
+9029
+9030
+9031
+9032
+9033
+9034
+9035
+9036
+9037
+9038
+9039
+9040
+9041
+9042
+9043
+9044
+9045
+9046
+9047
+9048
+9049
+9050
+9051
+9052
+9053
+9054
+9055
+9056
+9057
+9058
+9059
+9060
+9061
+9062
+9063
+9064
+9065
+9066
+9067
+9068
+9069
+9070
+9071
+9072
+9073
+9074
+9075
+9076
+9077
+9078
+9079
+9080
+9081
+9082
+9083
+9084
+9085
+9086
+9087
+9088
+9089
+9090
+9091
+9092
+9093
+9094
+9095
+9096
+9097
+9098
+9099
+9100
+9101
+9102
+9103
+9104
+9105
+9106
+9107
+9108
+9109
+9110
+9111
+9112
+9113
+9114
+9115
+9116
+9117
+9118
+9119
+9120
+9121
+9122
+9123
+9124
+9125
+9126
+9127
+9128
+9129
+9130
+9131
+9132
+9133
+9134
+9135
+9136
+9137
+9138
+9139
+9140
+9141
+9142
+9143
+9144
+9145
+9146
+9147
+9148
+9149
+9150
+9151
+9152
+9153
+9154
+9155
+9156
+9157
+9158
+9159
+9160
+9161
+9162
+9163
+9164
+9165
+9166
+9167
+9168
+9169
+9170
+9171
+9172
+9173
+9174
+9175
+9176
+9177
+9178
+9179
+9180
+9181
+9182
+9183
+9184
+9185
+9186
+9187
+9188
+9189
+9190
+9191
+9192
+9193
+9194
+9195
+9196
+9197
+9198
+9199
+9200
+9201
+9202
+9203
+9204
+9205
+9206
+9207
+9208
+9209
+9210
+9211
+9212
+9213
+9214
+9215
+9216
+9217
+9218
+9219
+9220
+9221
+9222
+9223
+9224
+9225
+9226
+9227
+9228
+9229
+9230
+9231
+9232
+9233
+9234
+9235
+9236
+9237
+9238
+9239
+9240
+9241
+9242
+9243
+9244
+9245
+9246
+9247
+9248
+9249
+9250
+9251
+9252
+9253
+9254
+9255
+9256
+9257
+9258
+9259
+9260
+9261
+9262
+9263
+9264
+9265
+9266
+9267
+9268
+9269
+9270
+9271
+9272
+9273
+9274
+9275
+9276
+9277
+9278
+9279
+9280
+9281
+9282
+9283
+9284
+9285
+9286
+9287
+9288
+9289
+9290
+9291
+9292
+9293
+9294
+9295
+9296
+9297
+9298
+9299
+9300
+9301
+9302
+9303
+9304
+9305
+9306
+9307
+9308
+9309
+9310
+9311
+9312
+9313
+9314
+9315
+9316
+9317
+9318
+9319
+9320
+9321
+9322
+9323
+9324
+9325
+9326
+9327
+9328
+9329
+9330
+9331
+9332
+9333
+9334
+9335
+9336
+9337
+9338
+9339
+9340
+9341
+9342
+9343
+9344
+9345
+9346
+9347
+9348
+9349
+9350
+9351
+9352
+9353
+9354
+9355
+9356
+9357
+9358
+9359
+9360
+9361
+9362
+9363
+9364
+9365
+9366
+9367
+9368
+9369
+9370
+9371
+9372
+9373
+9374
+9375
+9376
+9377
+9378
+9379
+9380
+9381
+9382
+9383
+9384
+9385
+9386
+9387
+9388
+9389
+9390
+9391
+9392
+9393
+9394
+9395
+9396
+9397
+9398
+9399
+9400
+9401
+9402
+9403
+9404
+9405
+9406
+9407
+9408
+9409
+9410
+9411
+9412
+9413
+9414
+9415
+9416
+9417
+9418
+9419
+9420
+9421
+9422
+9423
+9424
+9425
+9426
+9427
+9428
+9429
+9430
+9431
+9432
+9433
+9434
+9435
+9436
+9437
+9438
+9439
+9440
+9441
+9442
+9443
+9444
+9445
+9446
+9447
+9448
+9449
+9450
+9451
+9452
+9453
+9454
+9455
+9456
+9457
+9458
+9459
+9460
+9461
+9462
+9463
+9464
+9465
+9466
+9467
+9468
+9469
+9470
+9471
+9472
+9473
+9474
+9475
+9476
+9477
+9478
+9479
+9480
+9481
+9482
+9483
+9484
+9485
+9486
+9487
+9488
+9489
+9490
+9491
+9492
+9493
+9494
+9495
+9496
+9497
+9498
+9499
+9500
+9501
+9502
+9503
+9504
+9505
+9506
+9507
+9508
+9509
+9510
+9511
+9512
+9513
+9514
+9515
+9516
+9517
+9518
+9519
+9520
+9521
+9522
+9523
+9524
+9525
+9526
+9527
+9528
+9529
+9530
+9531
+9532
+9533
+9534
+9535
+9536
+9537
+9538
+9539
+9540
+9541
+9542
+9543
+9544
+9545
+9546
+9547
+9548
+9549
+9550
+9551
+9552
+9553
+9554
+9555
+9556
+9557
+9558
+9559
+9560
+9561
+9562
+9563
+9564
+9565
+9566
+9567
+9568
+9569
+9570
+9571
+9572
+9573
+9574
+9575
+9576
+9577
+9578
+9579
+9580
+9581
+9582
+9583
+9584
+9585
+9586
+9587
+9588
+9589
+9590
+9591
+9592
+9593
+9594
+9595
+9596
+9597
+9598
+9599
+9600
+9601
+9602
+9603
+9604
+9605
+9606
+9607
+9608
+9609
+9610
+9611
+9612
+9613
+9614
+9615
+9616
+9617
+9618
+9619
+9620
+9621
+9622
+9623
+9624
+9625
+9626
+9627
+9628
+9629
+9630
+9631
+9632
+9633
+9634
+9635
+9636
+9637
+9638
+9639
+9640
+9641
+9642
+9643
+9644
+9645
+9646
+9647
+9648
+9649
+9650
+9651
+9652
+9653
+9654
+9655
+9656
+9657
+9658
+9659
+9660
+9661
+9662
+9663
+9664
+9665
+9666
+9667
+9668
+9669
+9670
+9671
+9672
+9673
+9674
+9675
+9676
+9677
+9678
+9679
+9680
+9681
+9682
+9683
+9684
+9685
+9686
+9687
+9688
+9689
+9690
+9691
+9692
+9693
+9694
+9695
+9696
+9697
+9698
+9699
+9700
+9701
+9702
+9703
+9704
+9705
+9706
+9707
+9708
+9709
+9710
+9711
+9712
+9713
+9714
+9715
+9716
+9717
+9718
+9719
+9720
+9721
... 9990486 lines suppressed ...